Next: , Previous: BTree Cursors, Up: User Guide


4.8 BTree Indexing

One powerful feature of Elephant is the ability to add indexes to BTrees. An indexed btree is a subclass of the standard btree called indexed-btree. The indexed btree maintain a set of indices (instances of btree-index) which provide alternative ways of indexing into the values of the main btree.

Each index is itself a btree, but with the property that its values are matched to the keys of the main btree. That is if you have a btree with key-value pairs:

     ("henry" . #<name: Henry, age: 45>)
     ("larry" . #<name: Larry, age: 29>)

You can define an index that is populated by the age of the person object:

     (29 . "Larry")
     (45 . "Henry")

Now when you call (get-value 29 index) you get back #<name: Larry, age: 29>! Note also that these new pairs are ordered by age, the opposite of the alphabetic ordering of the names in the first two pairs. If you read through the tutorial, you may have guessed by now that this is the mechanism used to implement the class indexing capabilities previously described.

An index is created by using the add-index function. This function takes the indexed-btree you wish to index, an symbolic name for the index and a key-form which dictates how the index populates it's keys as a function of the main btree's keys and values. (It is a function of three arguments: the index itself, the key and the value).

A simple, contrived example is shown in the figure below:

[BTree Index Diagram]

Here we have a primary, indexed btree with a set of keys and values represented by symbols. We'll declare the function val to take a value symbol and extract it's number. The key-form in the mod5 * 2 index is:

     (lambda (k v)
       (if (= 0 (mod (val v) 5))
           (values t (* 2 (val v)))
           (values nil nil)))

When a key-value pair is written to the primary btree, the index is automatically updated through a call to the key-form. If the key-form above is called with key1 and value1, val will return 1 which fails the if test. The second values statement, (values nil nil) indicates that this pair is not to be indexed. If I pass key5 and value5 to this same key form, I get back 10 as the (val 'value5) is 5 and (= 0 (mod 5 5)) so the form returns (values t 10) meaning the index should add an index entry of 10 ((* 2 5)) associated with the key value key5.

So, of course, making the call (get-value 10 index-mod5) will return value5.

The second index in our little example calculates the number of bits in all odd numbered values. This illustrates an important property of the btree-index: it allows duplicate keys. Standard btree and indexed-btree classes are not allowed to have duplicate elements. The odd index allows us to ask simple questions like: “what are all the odd values with ids that fit into 4 bits?”.

To extract this set, we have to use cursor functions specifically designed for the index that iterate over duplicate values.