DragonFly kernel List (threaded) for 2008-06
Re: HAMMER Update 13-June-2008 - HEADS UP: MEDIA CHANGED AGAIN
: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.
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
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.