I can never keep all the variations straight, I need a Wiki reference

    every time to get the name right :-).
    These are all minor variations of B+Trees.  The B* variation keeps

    nodes 2/3rds full instead of half full.  It is an optimization which

    is intended to maintain higher fill ratios to make better use of system

    caches.
    A Dancing tree ... hehehehe.  Looks like Hans invented that one.  I'm

    not sure it even counts as a variation of a B+Tree.  It doesn't apply

    to HAMMER at all because HAMMER makes no modifications to the B-Tree

    whatsoever on the front-end.  When you create, delete, rename, write,

    etc...  when you do those operations HAMMER caches them in a

    virtualization layer in memory and doesn't make any modifications to

    its on-media data structures (or their in-memory representations) at

    all until the meta-data is synced to disk.
    HAMMER doesn't have to make real-time on-media modifications for any

    meta-data change for ANY operation.  Not a single one.  Not rename, not

    hard or soft links, not truncations, nothing.
    HAMMER uses a modified B+Tree for its on-disk representation, which is

    a B-Tree with only keys at internal nodes and only records at the leafs.

    This was done to reduce structural bloat, allow for a leaf->leaf

    linking optimization in the future, and for other reasons.  The Wiki

    definition isn't quite right.  The leaf->leaf links are optional (and

    HAMMER doesn't implement them, though I've left room to do so).  It's

    still a B+Tree if you don't have them.
    HAMMER's custom modification is to formalize both a left AND a right

    bounding element.  So a HAMMER B+Tree looks like this:
	B B B B B B	<---- internal node  (e.g. 6 elements w/ 5 leaf ptrs)

	 L L L L L	<---- leaf nodes
    Whereas a normal B+Tree looks like this (note the missing right bound):
	B B B B B  	<---- internal node

	 L L L L L	<---- leaf nodes
    Note that HAMMER uses a ...
[ message continues ]

But the case when you have to backtrack should be easily detected (when

the sought element is greater than the right-most bound), right? And

with a radix of 64 that would on average only happen on every 64'th

lookup. I'm not arguing the effectiveness of your implementation, just

checking my understanding of B+trees.
--

Erik Wikström

Neat. Thanks for the lengthy write-up.
--

Dan