[Tux3] Btree unit tests in action

Daniel Phillips phillips at phunq.net
Tue Aug 19 00:59:33 PDT 2008

I got annoyed with not having proper unit tests for btrees and made it
happen.  I found a bug right away so that shows why unit tests are never
to be left for later.

Seeing the btrees running in a crucible, I was reminded of an old issue
I never had a good answer for with ddsnap: insertion of keys in sorted
order is a worst case in that split blocks tend never to get more than
half full.  An index block splits, the new key goes into the upper of
the two halfs and the lower block is likely has a completely filled in
range of logical addresses so will never again receive a new entry.

Only fifty percent utilization of index blocks is not very good, we
would like to see something more like 75% or 83% (b+tree) utilization.
Ideas welcome.



Tux3 mailing list
Tux3 at tux3.org

More information about the Tux3 mailing list