Homepage: https://sourceforge.net/projects/cl-btree/
License: MIT
cl-btree has relatively high code coverage with unit tests but it is still considered unstable because of low usage rate.
Usage
There is two types of B-trees implemented. Default type uses 32-bit unsigned integers as keys and values. The other type uses string as keys and values. The string B-tree can store anything readable as keys and values. The size of key strings or values is not fixed. String B-tree uses simply prin1 to write and read to read keys and values from cl-swap-file block stream.
Here is a sample session for using string B-tree:
(let ((btree (b-tree:open "/tmp/b-tree-test.db" :type :string :block-size 64 :if-exists :append)))
(b-tree:insert btree 'my-key "This is a test value.")
(b-tree:search btree 'my-key)
(b-tree:close btree))
cl-btree uses cl-swap-file for storing disk blocks on to file.
Installation
Download it from https://sourceforge.net/projects/cl-btree/files/
cl-btree no longer depends on cl-unit-test.
Quick assessment (2021-04-11)
- Depends on cl-swap-file and cl-binary-file—but they're called cl-swap-file-0.6 and cl-binary-file-0.4, so ASDF fails there.
- cl-swap-file-0.6 depends on trivial-garbage but forgets to use it, so the attempt to make a weak hash table isn't portable.
- cl-binary-file implements a kind of bivalent stream (via trivial-gray-streams) but it doesn't work right under CCL.
- Each system includes the lisp-unit module, so there are a bunch of warnings about duplicate definitions.
Further assessment (2022-12-12)
- Needs other minor fixes, e.g. tests being in the wrong package.
- Version 0.12 will compile under CCL, a lot of warnings aside.
- The test with 32-bit integer keys will pass:
? (in-package :b-tree-tests)
#<Package "B-TREE-TESTS">
? (run-integer-performance)
Inserting keys...
(LET ((BTREE
(B-TREE:OPEN DB-FILE
:MINIMUM-DEGREE
MINIMUM-DEGREE
:BLOCK-SIZE
BLOCK-SIZE
:IF-EXISTS
:APPEND))
(KEY NIL)
(VALUE NIL))
(DOTIMES (I NUMBER-OF-KEYS)
(SETQ KEY (RANDOM (EXPT 2 32)) VALUE (RANDOM (EXPT 2 32)))
(PUSH (CONS KEY VALUE) KEYS/VALUES)
(B-TREE:INSERT BTREE KEY VALUE))
(B-TREE:CLOSE BTREE))
took 4,025,000 microseconds (4.025000 seconds) to run.
During that period, and with 4 available CPU cores,
0 microseconds (0.000000 seconds) were spent in user mode
15,625 microseconds (0.015625 seconds) were spent in system mode
218,320 bytes of memory allocated.
Searching keys...
(LET ((BTREE
(B-TREE:OPEN DB-FILE
:BLOCK-SIZE
BLOCK-SIZE
:IF-EXISTS
:APPEND)))
(DOLIST (KEY/VALUE KEYS/VALUES)
(ASSERT (= (B-TREE:SEARCH BTREE (CAR KEY/VALUE))
(CDR KEY/VALUE))))
(B-TREE:CLOSE BTREE))
took 195,000 microseconds (0.195000 seconds) to run.
During that period, and with 4 available CPU cores,
0 microseconds (0.000000 seconds) were spent in user mode
0 microseconds (0.000000 seconds) were spent in system mode
108,288 bytes of memory allocated.
Deleting keys...
(LET ((BTREE
(B-TREE:OPEN DB-FILE
:BLOCK-SIZE
BLOCK-SIZE
:IF-EXISTS
:APPEND)))
(DOLIST (KEY/VALUE KEYS/VALUES)
(ASSERT (= (B-TREE:SEARCH BTREE (CAR KEY/VALUE))
(CDR KEY/VALUE)))
(B-TREE:DELETE BTREE (CAR KEY/VALUE))
(ASSERT (NOT (B-TREE:SEARCH BTREE (CAR KEY/VALUE)))))
(B-TREE:CLOSE BTREE))
took 2,146,000 microseconds (2.146000 seconds) to run.
During that period, and with 4 available CPU cores,
0 microseconds (0.000000 seconds) were spent in user mode
15,625 microseconds (0.015625 seconds) were spent in system mode
241,872 bytes of memory allocated.- But the "string B-tree" construct depends on the file-stream being bivalent.
- SBCL has bivalent streams via the option :element-type :default, which is not a universal idiom.
- With CCL, only a tcp-stream is bivalent. So you get things like spurious newlines in the B-tree files.
Tags: StructuredStorage, Data Structure