
Summary

Medusa is a system that indexes a the names and types of files on a
system and the contents of its text files.  The indexing process
happens once every 24 hours.  The programming that manages running the
index periodically, and swapping the new index files into use is the
index daemon. (indexer/medusa-file-index-daemon.c)

The code for the data structures that create and run searches on the
index is located in libmedusa-internal.  Currently, there are three
main indexes, and several auxiliary on-disk hash tables.

The first index, called the "uri list", is a mapping between uris on
the system and unique numerical ids. It is stored using medusa's
relational database. There are two attributes stored here: the
directory name and the file name.  The uri number is implicitly the
column where a file's information is stored in the database.

The file attribute index stores the attributes of each file, including
the file's mime type, size, username, group, and permissions.  These
are also stored in a relational database.

The text index keeps a reverse index, an offset index, and a word hash
table.  The offset translates a word into the places in the reverse
index relevant to the word.  The reverse index sorts all of the words
on disk by word, rather than location, and so it is a list of uri
numbers.  All of the information about what word any part of the
reverse index is referring to is stored in the offset index.  The
reverse index is the "location-file" and the offset index is the
"start-file" on disk.  The structure of the text index can best be
understood by describing the process of doing a disk-wide content
search, which is presented below.

1.  The word being searched for is translated into a numerical token
by the word hash table.  

2.  The numerical token is used as the index in the offset index.  For
example if the word "foo" is hashed to the index 23432, then the
offset information occurs at 23432nd in the offset file.  The offset
information gives the beginning and end of the relevant informaiton
about the word "foo" in the location file.

3.  The offset information is used to extract the relevant information
from the reverse index.  The "relevant information" is a list of uri
numbers.  

4.  The uri numbers are translated into uris, and then returned.


More About internals.

The medusa relational database system stores fixed width columns. This
makes getting to a particular row in the database very easy, and a
relational database is read on disk by doing an array lookup.

In order to store variable length data (like strings) in fixed length
fields, medusa keeps on disk hash tables, which translate strings into 
"tokens" which are integers between 0 and a maximum value.


MedusaMasterDB manages the three indexes, and creates them during the
indexing process, and parses queries and sends requests to the correct
database during querying.





