Как выполнить поиск в таблице поиска без его загрузки в память?

Question

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

P.S. Я просто хочу выполнить поиск, не загружая все записи в память.

Может ли базовая база данных решить эту проблему?

Answer 1

Вы должны загрузить данные с жесткого диска в конечном счете, но уверен, что если таблица огромна не помещается в память, чтобы сделать линейный поиск через него, так:

1. думает, что если вы можете разделить данные на набор файлов
2. сделать индексную таблицу того, какой файл содержит какие записи (например, первые 100 записей находятся в «file1_100», вторая ста в «file101_201» и так далее)
3. с использованием индексной таблицы с шага 2 найдите файл для загрузки
4. загрузите файл и выполните линейный поиск

Это действительно упрощенная схема типичной системы управления базами данных, поэтому вы можете использовать ее как MySQL, PostgreSQL, MsSQL, Oracle или любой из них. Если это учебный проект, то после того, как вы закончите поиск, рассмотрите возможность оптимизации линейных операций (путем переключения на что-то вроде бинарного поиска) и таблиц (реальные базы данных используют сбалансированные древовидные структуры, хеш-таблицы и т. Д.).

Answer 2

Одним из способов было бы реорганизовать данные в файле в группы.

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

В этом примере вы должны сначала прочитать в соответствующей группе на основе буквы. Поэтому, если искомое слово начинается с «m», вы загрузите группу «m» в память.

Существуют и другие методы группировки, такие как длина слова (ключа). Также могут быть подгруппы. В этом примере вы можете разделить группу «m» на длину слова или вторую букву.

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

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

Идеи здесь, в том числе от @ 047, состоят в том, чтобы структурировать данные для наиболее эффективного поиска, предоставляя ограничения памяти.