Download Latest Version cl-btree-0.12.tgz (38.6 kB) Get Updates
Name Modified Size InfoDownloads / Week
cl-btree_0.12.tgz 2011-03-20 38.6 kB
cl-btree-0.12.tgz 2011-03-20 38.6 kB
cl-btree_0.12.tgz.asc 2011-03-20 316 Bytes
cl-btree-0.12.tgz.asc 2011-03-20 316 Bytes
README 2011-03-20 5.1 kB
cl-btree_0.11.tgz 2011-03-13 36.2 kB
cl-btree-0.11.tgz 2011-03-13 36.3 kB
cl-btree_0.11.tgz.asc 2011-03-13 316 Bytes
cl-btree-0.11.tgz.asc 2011-03-13 316 Bytes
cl-btree_0.10.tgz 2011-03-12 35.7 kB
cl-btree-0.10.tgz 2011-03-12 35.8 kB
cl-btree_0.10.tgz.asc 2011-03-12 316 Bytes
cl-btree-0.10.tgz.asc 2011-03-12 316 Bytes
cl-btree-0.9.tgz 2011-02-04 27.5 kB
cl-btree_0.9.tgz 2011-02-04 27.4 kB
cl-btree-0.9.tgz.asc 2011-02-04 316 Bytes
cl-btree_0.9.tgz.asc 2011-02-04 316 Bytes
cl-btree-0.8.tgz 2011-02-03 27.0 kB
cl-btree_0.8.tgz 2011-02-03 26.9 kB
cl-btree-0.8.tgz.asc 2011-02-03 316 Bytes
cl-btree_0.8.tgz.asc 2011-02-03 316 Bytes
cl-btree-0.7.tgz 2011-01-28 24.4 kB
cl-btree_0.7.tgz 2011-01-28 24.3 kB
cl-btree-0.7.tgz.asc 2011-01-28 316 Bytes
cl-btree_0.7.tgz.asc 2011-01-28 316 Bytes
cl-btree-0.6.tgz 2011-01-28 24.5 kB
cl-btree_0.6.tgz 2011-01-28 24.5 kB
cl-btree-0.6.tgz.asc 2011-01-28 316 Bytes
cl-btree_0.6.tgz.asc 2011-01-28 316 Bytes
cl-btree-0.5.tgz 2011-01-16 21.6 kB
cl-btree-0.5.tgz.asc 2011-01-16 316 Bytes
cl-btree_0.5.tgz 2011-01-16 21.6 kB
cl-btree_0.5.tgz.asc 2011-01-16 316 Bytes
cl-btree_0.4.tgz 2011-01-06 22.2 kB
cl-btree-0.4.tgz 2011-01-06 21.8 kB
cl-btree-0.4.tgz.asc 2011-01-06 316 Bytes
cl-btree_0.4.tgz.asc 2011-01-06 316 Bytes
cl-btree-0.3.tgz 2011-01-02 15.6 kB
cl-btree-0.3.tgz.asc 2011-01-02 316 Bytes
Totals: 39 Items   541.6 kB 1
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 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 (, - cl-swap-file (, Installing can be done with asdf-install: (asdf-install:install 'cl-btree) USAGE Please refer to API documentation ( 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.
Source: README, updated 2011-03-20