File search algorithms using indexing in linux

Question

I think of implementing a file search program using indexing in linux... I know that there are several other file search programs like beagled. but I am doing this for study purpose... I am struck with how to do indexing.. I have the following idea that I took from maemo-mapper application.. for example if u have file named "suresh" its index in the file system as files...

/home/$USERNAME/.file_search_index/s/u/r/e/s/h/list.txt.. This list.txt contains the location of all files with name = "suresh"... Pls suggest a better idea/algorithm to implement it... And If there is any material on various file search technique pls post it....

Answer 1

You haven't seen the locate command that comes with findutils? Like beagled, it's free software, so you can study the code.

The findutils package is always looking for contributors.

Information on the database format is at http://www.gnu.org/software/findutils/manual/html_node/find_html/Database-Formats.html

Answer 2

Beagle uses a very interesting approach with inotify. It starts, establishes a watch on the parent directory and starts another thread that does a recursive scan. As more directories are accessed, the parent sees them and adds more watches, while watching what it already knows about.

So, when its started, you're watching an entire tree quite cheaply (one watch per directory) and have the whole thing indexed. This also helps to ensure that no files are 'missed' during the scan.

So, that's most of your battle.. typically FS search programs hit their sluggish point when indexing, for instance 'updatedb'.

As for storing the index, I would not favor splitting it up in directories. You'd be in essence calling stat() on each character in a file name array. some-very-long-shared-object-name.so.0 for instance would be one call to stat() for every character in the name. You might try using a well designed SQLite3 database.

I'm working on something very similar, a program to provide slightly cheaper auditing means for PCI certification (credit card processor), without using kernel auditing hooks.