Как я могу выполнить поиск по справочной таблице, не загружая ее в память?
Теперь у меня есть файл, записывающий записи таблицы поиска. Если количество записей невелико, я могу просто загрузить этот файл в карту STL и выполнить поиск по моему коду. Но что, если есть много много записей? Если я сделаю это способом, описанным выше, это может привести к ошибке, такой как нехватка памяти. Я здесь, чтобы выслушать ваш совет …
Постскриптум Я просто хочу выполнить поиск без загрузки всех записей в память.
Может ли база данных ключ-значение решить эту проблему?
Решение
В конечном итоге вам придется загружать данные с жесткого диска, но если таблица огромна, она не уместится в памяти для линейного поиска, поэтому:
- подумайте, если вы можете разбить данные на набор файлов
- создайте индексную таблицу того, какой файл содержит какие записи (скажем, первые 100 записей находятся в «file1_100», вторая сотня находится в «file101_201» и т. д.)
- используя индексную таблицу из шага 2, найдите файл для загрузки
- загрузить файл и выполнить линейный поиск
Это действительно упрощенная схема для типичной системы управления базами данных, поэтому вы можете использовать такую, как MySQL, PostgreSQL, MsSQL, Oracle или любую другую.
Если это учебный проект, то после решения проблемы поиска рассмотрите возможность оптимизации линейных операций (путем переключения на что-то вроде бинарного поиска) и таблиц (реальные базы данных используют сбалансированные древовидные структуры, хеш-таблицы и т. П.).
Другие решения
Одним из методов будет реорганизация данных в файле в группы.
Например, давайте рассмотрим словарь полного языка. Как правило, словари слишком велики, чтобы полностью читать в память. Поэтому одна идея состоит в том, чтобы сгруппировать слова по первой букве.
В этом примере вы должны сначала прочитать в соответствующей группе на основе письма. Таким образом, если искомое слово начинается с «m», вы должны загрузить группу «m» в память.
Существуют и другие методы группировки, например длина слова (ключа). Также могут быть подгруппы. В этом примере вы можете разделить группу «m» на длину слова или на вторую букву.
После группировки вы можете захотеть записать данные обратно в другой файл, чтобы вам больше не нужно было изменять данные.
Существует много способов хранения групп в файле, например, с помощью маркера «section». Это было бы для другого вопроса, хотя.
Идеи здесь, в том числе от @ 047, состоят в том, чтобы структурировать данные для наиболее эффективного поиска с учетом ограничений памяти.