B-trees

[Darin Adler]

<>

Aside from sarcastic remarks about B-trees, someone wanted to know
what they were, an what relationship they had to binary trees.
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
definition, always balanced.  In addition, since the number of
children can be adjusted, the nodes can be made any size.  It is often
useful to make the size of a single node equal to the block size of
the mass storage device that the B-tree is stored on.  This will help
minimize the number of disk accesses.  (A similar thing can be done
with virtual memory, if you know the appropriate block size.)
-- 
Darin Adler
{gatech,harvard,ihnp4,seismo}!ut-sally!ut-dillo!darin