cl-bplustree – A Common Lisp implementation of an in-memory B+ tree.

cl-bplustree is an implementation of a in-memory B+ tree data structure in Common Lisp.

B+ trees main characteristics:

• All the data is in the leaves, internal nodes hold only keys used for traversal, pointers between the leaves are kept, so range-retrieval is easy and efficient.
• It is a generalization of a binary tree but instead of having only two pointers per node to other nodes it can have many more (this is called the order of the tree) because of this characteristic the tree has typically a large fanout and a small depth.

For more information about B+ trees, check Wikipedia.

Dependencies

None.

Usage

(bplustree-new (order &key key comparer))

Creates a new empty B+ tre of the given order and returns it.

The key parameter expects a function used to grab the key values (used for sorting) on whatever you are stuffing into the tree, the function will be called with one parameter (a record to be inserted into the tree for example) and it should return the value that will be used as a key. It defaults to #'identity.

The comparer parameter expects a function used when comparing keys against each other in the tree operations. This function has to take two parameters (keys of records) and return a value depending on the following conditions:

(< a b) → -1
(= a b) → 0
(> a b) → 1

The meaning of this of course is given by your particular keys and your particular applications, for string keys for example string<, string>, etc., could be used.

This parameter defaults to a function that implements the explained logic but for numerical keys. If your keys are numeric, you don’t need to supply a comparison function.

Example:

(defparameter *my-tree* (bplustree-new 4 :key (lambda (r) (parse-integer r))))

(bplustree-empty-p (tree))

Returns true if the tree is empty.

Example:

(bplustree-empty-p *my-tree*) -> T

(bplustree-insert (record tree &optional key))

Inserts the given record into the given tree, if the given key already exists in the tree, the value is updated. Returns the tree but is not needed to capture it and assign it,this call is not destructive on the tree itself, althought its internal elements are changed by it.

If key is omitted, calls the key function passed to bplustree-new on record. If key is included, uses that directly as the key. This enables using a B+ tree as a key/value store instead of a sorted set.

Examples:

(bplustree-insert "100" *my-tree*)
(bplustree-insert "100" *my-tree* 100)

(bplustree-insert-many (tree &rest items))

Inserts all the records given into the tree. Returns the tree.

Example:

(bplustree-insert-many *my-tree* "5" "10" "-1" "1337" "212" "32" "311" "52")

(bplustree-search (key tree))

Searches the value stored in the given key in the given tree.

Example:

(bplustree-search 311 *my-tree*) -> "311"

(bplustree-search-range (from to tree))

Searches the tree for all the records that exists between the given from and to keys and returns them in a list.

Example:

(bplustree-search-range 0 1000 *my-tree*) -> ("5" "10" "32" "52" "100" "212" "311")

(bplustree-search-next (key tree))

Returns the first key after the passed key. Passing NIL for the key returns the first key in the tree. The passed key need not be in the tree. Still returns the first key greater than that, which IS in the tree. Returns NIL when passed the last key.

The record corresponding to the key is returned as a second value. If the key was cached, T is returned as a third value.

Examples:

(bplustree-search-next nil *my-tree*) -> (values -1 "-1")
(bplustree-search-next -1 *my-tree*) -> (values 5 "-5" t)
(bplustree-search-next 1337 *my-tree*) -> nil

(bplustree-search-prev (key tree))

Returns the key before the passed key. Passing NIL for the key returns the last key in the tree. The passed key need not be in the tree. Still returns the first key less than that, which IS in the tree. Returns NIL when passed the first key.

The record corresponding to the key is returned as a second value. If the key was cached, T is returned as a third value.

Examples:

(bplustree-search-prev nil *my-tree*) -> (values 1337 "1337")
(bplustree-search-prev 1337 *my-tree*) -> (values 311 "311" t)
(bplustree-search-prev -1 *my-tree*) -> nil

(bplustree-delete (key tree))

Deletes the record stored in the given key in the tree. Returns the tree but is not needed to capture it and assign it, this call is not destructive on the tree itself, althought its internal elements are changed by it.

Example:

(bplustree-delete 32 *my-tree*)
(bplustree-search-range 0 1000 *my-tree*)
("5" "10" "52" "100" "212" "311")

(bplustree-traverse (tree fn))

Traverses all records in the tree in order from smallest to largest. As the B+ trees store data sorted already this operation is not expensive.

Example:

(bplustree-traverse *my-tree* 'print)
"-1"
"5"
"10"
"32"
"52"
"212"
"311"
"1337"

(bplustree-traverse-with-keys (tree fn))

Traverses all records in the tree in order from smallest to largest, calling fn on each with two args: the key and the value. As the B+ trees store data sorted already this operation is not expensive.

Example:

(bplustree-traverse-with-keys *my-tree* (lambda (k v) (print (list k v))))
(-1 "-1") 
(5 "5") 
(10 "10") 
(32 "32") 
(52 "52") 
(212 "212") 
(311 "311") 
(1337 "1337")

Final remarks

I hope this code is useful to you in any sense, either for learning, reading or maybe actual practical use, I will be very glad if you can even modify it to suit your needs. If you have suggestions please send them my way. Be sure to read COPYING file as well.