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

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

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

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

Спасибо.


datastore algorithm data-structures
person Amit    schedule 27.04.2013    source источник
comment
Возможно, вам лучше использовать msys или cygwin locate.   -  person dstromberg    schedule 27.04.2013

Ответы (2)


arrow_upward
0
arrow_downward

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

person sbru    schedule 27.04.2013

arrow_upward
0
arrow_downward

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

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

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

person richselian    schedule 28.04.2013