3 Dec
2011
3 Dec
'11
9:34 p.m.
* Question #1: why augmenting on B+ trees? The augmenting idea can be as easily built on top of RB-trees, which are the weapon of choice for implementing associative containers. Unless proved otherwise, RB-trees are assumed to be faster than B+ trees for in-memory structures (which your own tests hint at, cf. "insert N random elements" table.)
Could a B+ tree library be a basis for implementing disk-backed B+ trees? I think that would be useful. In a clever implementation the memory-backed and disk-backed B+ tree might even be the same class, with the difference factored out into a policy template parameter. Regards, Nate