Алгоритм внешнего поиска

Если у меня есть очень большой отсортированный список, хранящийся во внешнем хранилище. Предполагая, что этот список нельзя перенести во внутреннюю память, каким будет хороший алгоритм поиска, который ищет ключ в этом списке в псевдокоде? какова будет временная сложность?, а также какие основные факторы следует учитывать при разработке этого алгоритма?


sorting sortedlist external-sorting
person ACE    schedule 06.05.2016    source источник
comment
Вы можете создать ключевые индексные файлы, а затем создать какой-то язык для предметной области... назовем его SQL для запроса данных в структурированной форме. Тогда вы могли бы тратить время на написание дополнительных материалов. Но подождите - это уже было сделано. Она называется базой данных.   -  person BitTickler    schedule 06.05.2016
comment
Во многих базах данных задействован файл, специфичный для ключа, но это только один ключ для каждых k записей, где k может быть примерно 64 (может быть меньше или больше), что приведет к поиску в пределах 64 записей, что тогда будет читать последовательно, с одним начальным произвольным доступом. Еще во времена мейнфреймов и ограниченной памяти использовались вложенные индексы, такие как индексы к индексам к записям.   -  person rcgldr    schedule 06.05.2016

Ответы (1)


arrow_upward
0
arrow_downward

Предположим, что ваше внешнее хранилище — это просто массив записей постоянного размера, хранящихся в файле, и ваш язык программирования позволяет карту памяти файла, вы можете использовать обычный алгоритм бинарного поиска.

Скажем, в C++ вы

  1. mmap файл принимает указатели void* на начало и конец файла mmap,
  2. укажите указатели на ваш тип записи
  3. а затем выполните поиск записи с помощью std::lower_bound(), который является одним из стандартные реализации бинарного поиска.

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

Это стандартная практика поиска в отсортированных файлах, и нет смысла ее переделывать (ну, насколько мне известно). Сложность алгоритма бинарного поиска во внешней памяти зависит от модели внешнего хранилища, стратегии буферизации/подкачки и т. д., но для вашего жесткого диска вы все равно можете предположить, что он находится в обычном O (log N). Я рекомендую вам поискать руководства по нестандартным алгоритмам и структурам данных. и библиотеки.

person datjko    schedule 07.05.2016