"David B. Held" <dheld@codelogicconsulting.com> wrote in message news:cvu3uj$mrk$1@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