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.
Source for the btree package as of Wed Mar 27 2001. The latest release is v1.0 done on Wed Mar 27 2001.
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
2239.55608979
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.