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 radix of 64, ...
[ message continues ]

Neat. Thanks for the lengthy write-up.

-- 
Dan
[ 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
[ message continues ]