DragonFly kernel List (threaded) for 2008-06
DragonFly BSD
DragonFly kernel List (threaded) for 2008-06
[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]


From: Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>
Date: Tue, 17 Jun 2008 18:25:44 -0700 (PDT)

: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

    * 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

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

					Matthew Dillon 

[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]