Allegro Btrees

AllegroCache is a high-performance, dynamic object caching database system. It is described on this page. One feature in AllegroCache is Btree support, which is now available for ACL programmers to use directly. Btrees are useful for applications where you need a simple and efficient way of storing on disk and retrieving vast numbers of key/value pairs and where you want to retrieve the keys in order (using an ordering you can specify if desired).

The general theory of Btrees is discussed in http://en.wikipedia.org/wiki/Btree, what we have implemented is closer to B trees. The most important feature is stores and accesses take on the order of Log(N) time, where N is the number of nodes in the btree. This means that store/access times are reasonable even for very, very large btrees.

The Allegro implementation of btrees has these properties in addition:

• The code is written completely in Lisp in order to get the best performance possible and the best integration into a Lisp program.
• Keys and values are simple vectors of type (unsigned-byte 8). (You can use other types if you write encoder/decoders to/from (unsigned-byte 8) vectors.)
• There is extensive support for caching disk blocks to avoid disk I/O.

Allegro CL also supports Btree cursors. A cursor is an object which points to a Btree entry, and which can be moved (using the functionality supplied) to point to other entries.

Documentation

The AllegroCache Btree documentation is here. Symbols naming Btree functionality are in the db.btree package.