These routines implement a B-Tree data structure. I developed most of this code using Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest. The code implements B-Tree and not B-Tree+. B-Tree+ allow you to do an in order traversal of the data without having to lock each node. Currently the code isn't reetrant, but I plan on making it so.

You can specify how large of a node size to use. Currently, the only data that is stored in the node is a void *, but I do plan on providing extensions to put arbitary sized data into the node.

Obtaining Releases and Release History

Source for the btree package as of Wed Mar 27 2001. The latest release is v1.0 done on Wed Mar 27 2001.

Usage and Details


Some numbers on performance:

hydrogen,ttype,/tmp/dl/btree,564$dmesg | egrep -i 'cpu|memory|origin'
CPU: AMD-K6(tm) 3D processor (400.93-MHz 586-class CPU)
  Origin = "AuthenticAMD"  Id = 0x58c  Stepping = 12
real memory  = 134152192 (131008K bytes)
avail memory = 126623744 (123656K bytes)
hydrogen,ttype,/tmp/dl/btree,552$./test 1000000 512
insert time: 6.684010
root: 0x8567800, keyoff: 4, nodeptroff: 256, nkeys: 63, t: 32, nbits: 8, textra:
 508, height: 4, numkeys: 1000000, numnodes: 22993
search time: 5.585903
delete time: 8.247143
hydrogen,ttype,/tmp/dl/btree,557$calc 5.585903/1000000*400930000

So, that's about 2240 cycles per search, about 11MB (22993 nodes * 512 bytes/node) for storage of all necessary data (plus 4MB for static storage of numbers to search for). The 2240 includes the loop in main.c.