[boost] Re: Boost library inclusion: generic tree containers?

From: Justin Gottschlich (jgottschlich_at_[hidden])
Date: 2005-02-28 02:40:17

"David B. Held" <dheld_at_[hidden]> wrote in message 
news:cvu3uj$mrk$1_at_sea.gmane.org...

> It sounds to me like you are not considering the general case
> where a given node can have K keys and N children.  Now typically,
> K = 1, which is why I made it the default in the sample code.  That
> is what you are talking about.  But for a Btree, you often have
> K = N - 1.  That is, each node contains K "objects" or "keys",
> and N children.  Yes, you could provide a single iterator type
> that iterates over keys both *within* a node and *among* nodes,
> but it would be a fat iterator (at least algorithmically, if not
> structurally).  I think a better decomposition is to recognize that
> for trees with large aggregate nodes, the fundamental operations
> are to access the keys within the node, and access the children
> separately.
>
> To illustrate, let me offer an exaggeration.  Suppose we build a
> Btree for use in a disk-based container.  We could build it so that
> K = 64, N = 4.  That is, each node contains 64 "keys", but only
> 4 children.  There are numerous ways to distribute keys and children
> in such a configuration, and there is no a priori reason for an
> implementation to exclude the possibility of any given distribution.
> So such a tree would have a narrow branching factor, but fat nodes.
> That might better correspond to the size of disk sectors while
> not wasting too much space on a wide branching factor.

Ahh yes, I see what you're saying now - I wasn't understanding correctly. If 
you mentioned the B-tree example in your original post, I must have 
completely missed it, but your point in regards to a B-tree cleared it right 
up for me. I don't believe has been touched upon until your post, so 
doubly-thank you for bringing it up (if somebody else did bring it up 
already and I just missed it, sorry for being so blind =).

Thanks for the extra explanation Dave, =)
Justin