Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk