Re: HAMMER Update 13-June-2008 - HEADS UP: MEDIA CHANGED AGAIN

[Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>]

: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

    Yes, that is correct.  It isn't a big deal for lookups, but it can get
    really nasty for insertions.

    * For insertions you want your locking to go in one direction, not both
      directions, or you will wind up with potentially very serious deadlocks
      between writers.

      Normally the direction you want to go is down, so you can split nodes
      on your way down and the insert without deadlocking against other
      writers.

    * For insertions you are trying to locate the insertion point as you
      traverse the tree.  If you have to go down, and then backtrack, and
      find that the node doesn't exist and the insertion point really was
      supposed to be in the initial branch, then you have to go down a second
      time.

    Deletions have similar issues, but insertions are the algorithm killer.
    That's the main reason why I put in the right hand bound.

					-Matt
					Matthew Dillon 
					<dillon@backplane.com>