Next: Index Cursors, Previous: BTree Cursors, Up: User Guide
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:
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.