Алгоритмы поиска файлов с использованием индексации в Linux

Question

Я думаю о реализации программы поиска файлов с использованием индексации в Linux ... Я знаю, что есть несколько других программ поиска файлов, таких как beagled. но я делаю это для учебной цели ... Я поражен тем, как сделать индексацию ... У меня есть следующая идея, которую я взял из приложения maemo-mapper .. например, если у вас есть файл с именем "suresh", его индекс в файловой системе как файлы ...

/ home / $ USERNAME / .file_search_index / s / u / r / e / s / h / list.txt .. Этот list.txt содержит расположение всех файлов с именем = "suresh" ... Просьба предложить лучшая идея / алгоритм для его реализации ... И если есть какие-либо материалы по различным методам поиска файлов, пожалуйста, напишите об этом ....

Answer 1

Вы не видели команду locate, которая поставляется с findutils ? Как и beagled, это бесплатное программное обеспечение, так что вы можете изучить код.

Пакет findutils всегда ищет участников.

Информация о формате базы данных: http://www.gnu.org/software/findutils/manual/html_node/find_html/Database-Formats.html

Answer 2

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

Итак, когда оно началось, вы просматриваете все дерево довольно дешево (один просмотр на каталог) и индексируете все это. Это также помогает гарантировать, что ни один файл не будет «пропущен» во время сканирования.

Итак, это большая часть вашей битвы. Обычно программы поиска FS достигают своей вялой точки при индексации, например, «updatedb».

Что касается хранения индекса, я бы не хотел разделять его по каталогам. По сути, вы будете вызывать stat () для каждого символа в массиве имен файлов. Например, some-очень-long-shared-object-name.so.0 будет одним вызовом stat () для каждого символа в имени. Вы можете попробовать использовать хорошо спроектированную базу данных SQLite3.

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