cl-btree Files

CL-BTREE
Copyright (c) 2008 Sami Makinen

INTRODUCTION

B-Tree implemented in Common Lisp. Stores key/value pairs onto disk
based data structure. Current implementation has been tested with
SBCL. Project was originally at alien-consader.org but is now made
available at SourceForge.

cl-btree implements basic B-tree API with cursors but current
implementation does not support threading nor multiprocessing on the
same B-tree instance. Locking has to be managed externally. cl-btree
uses write ahead log to ensure modifying operations are guaranteed to
leave B-tree in consistent state even if system crashes in the middle
of operation. Still, the current implementation does not support
concept of transaction and each modifying operation is immediately
committed to the master file when operation finishes.

cl-btree supports both unique and non-unique B-trees. In non-unique
B-tree key's associated value is a list of values and inserting the
value to a B-tree pushes value to the list, keeping last inserted
value first.

cl-btree supports also in-memory B-trees which are useful for testing
purposes. In-memory B-trees can be created using binary-file's
binary-array-io-stream as a filespec for B-tree.
For example

  (let ((btree (b-tree:create (binary-file:make-binary-array-io-stream) :block-size 128)))
       ; use it
   ) ; gc'd here

Cursor implementation is still evolving and the current implementation
works properly only with unique B-tree. Iterating over non-unique
B-tree does not iterate key's associated value list value by value but
whole list as a value. This feature is rather annoying with
cursor-delete and cursor-put calls.

INSTALLING

cl-btree depends on following projects: 
  - cl-binary-file (http://cl-binary-file.sourceforge.net),
  - cl-swap-file (http://cl-swap-file.sourceforge.net),

Installing can be done with asdf-install:

  (asdf-install:install 'cl-btree)

USAGE

Please refer to API documentation (http://cl-btree.sourceforge.net/) for details.

A sample session:

(let ((btree (b-tree:open "simple.db" :type :string :minimum-degree 10 :if-does-not-exist :create :unique t)))
  (b-tree:insert btree 'cltl2 '((title "Common Lisp, the Language 2nd ed.") (year 1990) (author "Guy L. Steele") (publisher "Digital Press") (ISBN "1-55558-041-6")))
  (print (b-tree:search btree 'cltl2))
  (b-tree:close btree))

=> 

((TITLE "Common Lisp, the Language 2nd ed.") (YEAR 1990)
 (AUTHOR "Guy L. Steele") (PUBLISHER "Digital Press")
 (ISBN "1-55558-041-6"))

IMPLEMENTATION DETAILS

B-tree uses algorithm described in Introduction to Algorithms by
Corman, Leiserson, Rivest and Stein.  The disk block management is
handled by cl-swap-file which basically stores a created gray stream
to a serie of one or more disk blocks. Disk blocks are fixed size. The
deleted disk blocks are maintained in a list of disk
blocks. cl-swap-file manages also disk block caching.

cl-swap-file uses cl-wal which provides very simple write ahead log to
ensure B-tree is consistent in case of system failure.

Current implementation does not support threads nor multiple transactions
at the same time.

The B-tree with string values uses prin1 and read to store and get
values from B-tree. 

The B-tree node contains list of B-tree items and possibly B-tree node
references to a child nodes. Writing B-tree node stores node to a
write ahead log. B-tree node is splitted to as many disk nodes as the
size requires. When B-tree commits the changes the changed disk
blocks stored in write ahead log are written to actual master
file. The current implementation commits changes immediately after
insert and delete, so the concept of transactions is not supported.
The write ahead log is still needed to make insert or delete
happen atomically in case multiple disk blocks are modified
by the operation.

cl-btree provides debugging utility to view stored swap-file contents
and to validate B-tree structure.
 
TODO LIST

Write ahead log checkpointing (and not only this) is dummy, should be fixed
  - current implementation starts a new log file after checkpoint and deletes 
    old one (there is only one transaction active at a time),
  - add REDO checkpoint marks to log file,
  - fix write ahead log recovery process to support new checkpointing mechanism,
  - add mechanism to start a new log file and backup earlier,
  - add utility to delete unnecessary log files

B-tree should support transactions. 
  - initial implementation with still only one transaction active,
  - define transaction data structure, 
  - pass transaction id to write ahead log,
  - implement write ahead log recovery with transaction support,
  - implement checkpointing with transaction support.

B-tree should support threads
  - in other words multiple active transactions active at the same time
    with proper locking mechanism.
  - initial implementation could just lock whole B-tree for a update
    and give precedence for updates over reads.

B-tree performance
  - compare to others,
  - improve :-)


All help is appreciated!

REPORTING BUGS

Please use SourceForge's bug tracker or send e-mail.

  http://sourceforge.net/projects/cl-btree/