Методы те же, но идея уже немного иная - а именно минимизировать число обращений к внешней памяти.
B-tree
Этот способ описан в многопутовые деревьях. Если например в качестве ключа использовать слова (string), то поиск будет выглядеть следующим образом. Получаем слово, идет в самую первую позицию файла, считываем все слова из блока, бежим в оперативной памяти по этому блоку, сравниваем нужные слова, если находим возвращаем, если нет, то определяем к какому узлу дерева идти дальше. Определяем узел и идем дальше к нужной странице на жестком диске
Существуют еще разновидности в виде B+деревьев и R-деревьев.
Индексирование
Вместо хранения строки целиком, (если брать row), хранится в оперативной памяти лишь информация об одном столбце, который указывает на номер блока на жестком диске. Т.е по сути лишь память экономится, храним в оп. памяти часть информации, а не всю row целиком. Но количество записей остается прежним. Тут происходит всего одно обращении к внешней памяти, но нужно где-то хранить сам индекс. Он не всегда может поместиться в оперативной памяти, поэтому возможно его придется хранить самого на диске. Сам индекс можно хранить в виде отсортированного списка, чтоб например воспользоваться бинарным поиском, но тогда в него будет тяжело вставлять элементы, т.к придется сдвигать целиком массив. Ну или можно хранить индекс в виде красно-черного дерева.
Хеширование
Получаем хеш от поля по которому ищем, и используя этот хеш обращаемся к конкретному блоку памяти по номеру. Тут нужна хорошая хэш-функция, желательно, чтобы блоки, которые мы читаем не заполнялись более чем наполовину. Опять же обращение к диску происходит всего как правило один раз. Но тут встает та же проблема с коллизиями, когда полные блоки будут заполняться, вставка и поиск будут обращаться сразу к нескольким блоками памяти, пока не найдут искомый элементы. Ресолвиться эти коллизии могут тем же способом, что и в обычном hashMap, т.е при "линейном пробировании" тупой перебор следующий блоков, при реализации метода цепочек создаются как бы специальные блоки переполнения. Если первичный блок окажется заполненным, новая информация будет вставляться в блок переполнения, на который наверное будет указывать первичный блок.
Доп. информация
1) citforum.ru/programming/theory/sorting/sorting2.shtml#5
2) «Системы баз данных: полный курс» авторства Ульмана, Уидома и Гарсиа-Молина
3) «Database Systems: The Complete book»
Комментариев нет:
Отправить комментарий