What are B-trees? (Re: programs for B-trees wanted, tinsert offered)

[Guido van Rossum]

Sorry, B-trees are something quite different from binary trees!!!
For a rather complete explanation of B-trees, see: D.E. Knuth,
The Art of Computer Programming, III (Sorting and Searching),
section 6.2.4.

In short, a B-tree has a variable number of branches per node,
with a minimum and a maximum number of branches which are conserved
during insertion and deletion by "borrowing" branches from or
merging with neighboring nodes (the root may underflow).
All leaves occur at the same level, and there is a guaranteed maximum of
order O(log N) for the level of a tree with N items (unlike binary trees,
which are frustrated, e.g., when items are inserted in monotonic order).

When certain relations between the min and max values hold,
(min = floor(max/2)), searching insertion and deletion can all be
done in O(log N) time.  A node with K pointers has K-1 keys.
Since leave nodes have no branches, the space for the pointers can be
used for keys, and the min/max values for leaves can be chosen larger.

(This is sales pitch, the main poin being the O(log N) properties.
Don't think you understand it now; read Knuth!)

--
	Guido van Rossum, "Stamp Out BASIC" Committee, CWI, Amsterdam
	guido @ mcvax