4.3 Structure files

  Qddb builds a collection of structure files on each stabilization. The files are used internally by Qddb and should not usually be edited (although you can, of course!). Each file has a specific purpose related to searching.

• Database: The stable data. Tuples are separated from each other by a blank line. Each non-empty attribute is on its own line, with an attribute identifer followed by the value.
• Database.key: One line for each stable tuple in the form: (offset length), referring to Database. This file is used mostly for displaying the entire relation quickly and in stabilization.
• HashTable: Each line is the header for a bucket of the hash table. A header has the form: (number-of-collisions hashval offset length). The offset and length refer to the file Index. This file is used in full-word searches, which employ hashing. If you have enabled ``cached hashing'' (see Section 6.1), the format has a fixed width and no missing lines, facilitating random access.
• Index: Each (possibly very long) line holds the partial contents of one bucket of the hash table. It begins with the word (or key). The rest of the line is a list of pointers to tuples called a KeyList. Each member of the KeyList is of the form: (offset length attribute instance). The offset and length point to a tuple in the Database file. The attribute and instance parts specify where in the tuple the key is found.
• KeyIndex: A sorted list of all words (keys) in the Database file. Each line is of the format: (key offset length). The offset and length point into the Index file to the part of the word's hash bucket that holds the KeyList for that word. This file assists in searches based on word ranges and on regular expressions.
• NumericIndex: This file has the same format as KeyIndex, but it contains only words that happen to be numbers. This file assists in searches based on numbers or numeric ranges.
• RedAttrIndex: A list of all full attribute identifiers that occur in Database. These are used to generate a shorter representation (in base 36) that can be used to significantly reduce the size of Database and Index.

Behind the scenes, the stabilizer program qstall invokes qstab, qkeys, and qindex to perform various phases of stabilization. Qstab rebuilds the Database file by removing any invalid tuples and merging in all files from the Changes and Additions directories. Qkeys builds the Database.key file by parsing the Database file. Finally, qindex builds the other structure files.