Какая структура данных использовать

Question

У меня есть миллионы файлов на локальных дисках (например: c, d, e) моей системы. Теперь для поиска файла мы можем использовать встроенные инструменты Windows или такие команды, как «find» в linux. Если я хочу создать свою собственную программу «найти», которая должна сначала сканировать все каталоги и хранить информацию либо в каком-то файле, либо в БД. Теперь, когда я хочу искать файл, нам сначала нужно загрузить информацию из БД или файла, а затем выполнить поиск.

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

Поскольку поиск основан на имени файла, я думал об использовании Hashmap, где ключ будет именем файла, а значение будет полным. Использование Trie сделает поиск медленнее. Другая идея - использовать Инвертированный индекс. Но не уверен, что когда-то лучше.

Спасибо.

Answer 1

Хэш-стол был бы очень хорош для этого, потому что он имеет O (1) для поиска (и вставляет и удаляет также). но проблема в том, что вы не можете использовать хеш-таблицу для «поиска в диапазоне». «Ранжированный поиск» будет выглядеть как «Найти все файлы, которые заканчиваются расширением cpp». Если это не проблема для вас, я бы предложил реализовать хеш-таблицу.

Answer 2

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

Я предлагаю вам попробовать некоторую структуру на основе диска, такую ​​как B-Tree или Hashmap внешней памяти. они оптимизированы для диска, и вы можете искать запись без загрузки всего набора данных.

Если вы не хотите самостоятельно создавать структуру поиска на основе дисков, попробуйте Google LevelDB Google.