B-trees

[Perry S. Kivolowitz]

In article <212 at ut-dillo.UUCP>, darin at ut-dillo.UUCP (Darin Adler) writes:
> B-trees are a more general case of the type of tree that a binary tree
> is.  They allow any given number of children per node.  They are, by...

First: Why are B-Trees called B-Trees?

Some people say B (as in Baer, the inventor) or B as in Boeing (where 
Baer was when he did his work).

Next: Are B-Trees binary?

No. For a given B-Tree, a node may between n and 2n elements. No node
(except the root) may have less than n. No node (including the root) may
have more than 2n. 

During an insertion, if the node being inserted in would grow to 2n + 1
elements, the node is split into two nodes one of n elements the other
of n elements. The middle element is graduated to the original nodes
parent (where a similar process will occurr).

During deletion, if the node being deleted from should shrink to less than
n elements is is combined with a neighbor to produce two nodes each having
greater than n elements.

And: What's so neat about B-Trees.

They are always balanced insuring logarithmic operations. The logarithmic
time is dependent of course on the choice. N is usually chosen so as to make
an integer number of records fit reasonably in an integer number of blocks.

Also, you are always assured that space utilization is greater than 50
percent while leaving as much as percent space for expansion.

Are there other types of B-Tree?

yes, B+ and B* Trees. B* trees change in minimum number of elements per
non root node fro 2n/3 elements giving you 2/3 space utilization.
Oh yeah, why is space utilization important? Becuase the better you
use the space you have the less deep the tree.

B+ Trees are different in that they seperate indices from data. You
have an index set, and a data set. All leave nodes are at the same level
and contain ONLY data (perfect for indexed and sequential operations)
while b-trees can stuff records (index and data) anywhere in the tree.

(the above is what happens when you write a b+ tree based data base system
in two weeks four years ago).
			any one wanna buy it for the amiga? :-)

						Perry S. Kivolowitz
						ihnp4!ptsfa!well!perry