Корректная структура данных для использования для (это конкретное) истекающий кэш?

Я должен читать из набора данных, который является очень большим, высоко связанный, данные справедливо локализуются, и чтения являются довольно дорогими. Конкретно:

1. Наборы данных 2gigs - 30gigs в размере, таким образом, я должен отобразить разделы файла в память для чтения. Это очень дорого по сравнению с остальной частью работы, которую я делаю в алгоритме. От профилирования я нашел, что примерно 60% времени потрачены, читая память, таким образом, это - правильное место, чтобы начать оптимизировать.
2. При работе на часть этого набора данных я должен следовать, ссылки в нем (вообразите это как то, чтобы быть подобным связанному списку), и в то время как тем чтениям не гарантируют в какой-либо степени последовательному, они справедливо локализуются. Это означает:
3. Скажем, например, мы воздействуем на 2 megs памяти за один раз. При чтении 2 megs данных в память примерно 40% чтений, которые я должен буду впоследствии сделать, будут в тех же самых 2 megs памяти. Примерно 20% чтений будут чисто произвольным доступом в остальной части данных, и другие 40% очень вероятно связываются назад в 2meg сегмент, который указал на этого.

От знания проблемы и от профилирования, я полагаю, что представление кэша к программе поможет значительно. То, что я хочу сделать, создают кэш, который содержит блоки N X megs памяти (N и X настраивающийся, таким образом, я могу настроить ее), который я могу проверить сначала, прежде, чем иметь необходимость отобразить другой раздел памяти. Кроме того, чем дольше что-то было в кэше, тем менее вероятно случается так, что мы запросим, что память в ближайшей перспективе, и таким образом, самые старые данные должны будут истечь.

В конце концов, это, мой вопрос очень прост: Какая структура данных была бы лучшей для реализации кэша этой природы?

У меня должны быть очень быстрые поиски, чтобы видеть, находится ли данный адрес в кэше. С каждой "мисс" кэша я захочу истечь самый старый член его и добавить нового участника. Однако я планирую попытаться настроить его (путем изменения суммы, это кэшируется), таким образом, что 70% или больше чтений являются хитами.

Мои существующие взгляды состоят в том, чтобы использовать любого дерево AVL (LOG2 n для ищут/вставляют/удаляют), было бы самым безопасным (никакие вырожденные случаи). Моя другая опция является редкой хеш-таблицей, таким образом, что поиски были бы O (1) в лучшем случае. В теории это могло ухудшиться в O (n), но на практике я мог поддержать коллизии на низком уровне. Беспокойство здесь было бы то, сколько времени оно берет, чтобы найти и удалить самую старую запись в хеш-таблице.

У кого-либо есть какие-либо мысли или предложения на том, какая структура данных была бы лучшей здесь, и почему?