Messages in this thread | | | From | Daniel Phillips <> | Subject | Re: Ext2 directory index: ALS paper and benchmarks | Date | Thu, 6 Dec 2001 18:22:34 +0100 |
| |
On December 6, 2001 02:44 pm, Hans Reiser wrote: > Daniel Phillips wrote: > >On December 6, 2001 04:56 am, Hans Reiser wrote: > >>>On December 6, 2001 04:41 am, you wrote: > >>> > >>>>ReiserFS is an Htree by your definition in your paper, yes? > >>>> > >>>You've got a hash-keyed b*tree over there. The htree is fixed depth. > >>> > >>B*trees are fixed depth. B-tree usually means height-balanced. > > > >I was relying on definitions like this: > > > > B*-tree > > > > (data structure) > > > > Definition: A B-tree in which nodes are kept 2/3 full by redistributing > > keys to fill two child nodes, then splitting them into three nodes. > > This is the strangest definition I have read. Where'd you get it?
This came from:
http://www.nist.gov/dads/HTML/bstartree.html
Here's another, referring to Knuth's original description:
http://www.cise.ufl.edu/~jhammer/classes/b_star.html
> >To tell the truth, I haven't read your code that closely, sorry, but I got > >the impression that you're doing rotations for balancing no? If not then > > What are rotations?
Re-rooting a (sub)tree to balance it. <Pulls Knuth down from shelf> For a BTree, rotating means shifting keys between siblings rather than re-parenting. (The latter would change the path lengths and the result wouldn't be a BTree.)
So getting back to your earlier remark, when examined under a bright light, an HTree looks quite a lot like a BTree, the principal difference being the hash and consequent collision handling. An HTree is therefore a BTree with wrinkles.
<reads more> But wait, you store references to objects along with keys, I don't. So where does that leave us?
By the way, how do you handle collisions? I see it has something to do with generation numbers, but I haven't fully decoded the algorithm.
Fully understanding your code is going to take some time. This would go faster if I could find the papers mentioned in the comments, can you point me at those?
-- Daniel
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |