Dr. Dobb's Sourcebook May/June 1997

D-tree Indexing

In a D-tree index, each entry points to multiple tuples in the table. For example, if an index is created like Figure 2(a), and the table is populated as in Figure 2(b), then the D-tree will contain the word list in Figure 2(c) with the exception that case doesn't count.

The references from the index to the table tuples would, assuming the tuples are numbered 1 through 3, look like Figure 3. This list is represented as an ordered list, but in reality, it would be implemented as a B-tree.

A multiword input search string requires an index scan for each word. Since this is a B-tree, we have a worst case performance of m.log(n), where m is the number of words and n is the total number of words indexed. The value of n is greater than the tuple count but less than the number of words in all the documents. In the above example the tuple count is 3, there are 16 words in total and the index containing just 10 entries.

Thanks to Paul Brown for submitting the original tech note on D-trees to the Informix Knowledgebase.

-- C.T.