Re: [Caml-list] [1/2 OT] Indexing (and mergeable Index-algorithms)

[Brian Hurt <bhurt@spnz.org>]

On Thu, 17 Nov 2005, skaller wrote:

> Balanced BTree guarantees extremely small constant time lookup
> for all keys. (typically 3 or 4 accesses)
> Many updates are also fast constant time. However
> the Btrees are very expensive to rebalance, and occasionally
> an update requires a global rebalancing which brings the
> world to a complete stop for a very long time.

Not as I understand BTrees.  BTrees are generializations of 2,3,4 trees. 
Each "node" of the tree has between k/2 and k (for k > 3) children (except 
for the root node, which can have anywhere from 2 to k children).  When 
adding a new child to a given node, if the number of children exceeds k, 
then the node is split into two nodes, each with (k+1)/2 children (if k is 
even, one of the two nodes gets the extra).  The new sibling is then added 
to the parent of the original node.  When the root node is split, then a 
new level is added above the root node (note, changing the depth of the 
entire tree at the same time).  Likewise, when children are removed, if 
the node falls below k/2 children, it's merged with one of it's siblings. 
If the root node drops to only having 1 child, it's removed, and it's lone 
child becomes the new root, again changing the depth of the entire tree at 
once.

For in-memory data structures, Btrees are less efficient than standard 
balanced binary trees.  See, the problem is that you do a search on the 
BTree, you have to do a binary search on the children at each node.  So 
the cost of doing a search on a BTree with N elements is log base k of N 
nodes times log base 2 of k for the binary search in each node.  A little 
bit of algebra proves that this is equal to the log base 2 of N, the same 
cost as searching a binary tree (basically).  Worse yet, when inserting 
or deleting an object, the average cost is O(k)- you have to insert 
or remove elements into/from the middle of an array.  If k > log base 2 of 
N (likely), then the standard balanced binary tree will be faster on 
inserts and deletes.  Where BTrees shine is in disk based data structures. 
Here, the main bottleneck is reading data off the disk.  For N=2^32 and 
k=256, a standard balanced binary tree would require up to 64 disk reads, 
the BTree only 5.

> Some modern variants amortise the costs differently,
> typically reducing the worst case at the expense
> of the other operations. In particular, the very
> worst way to populate a BTree from a list is if
> the list is already sorted, however a smart algorithm
> can build an empty skeleton first and populate it
> in linear time (provided only you know
> how many keys there are). Obviously, the tree
> has to be offline until this operation is completed.

Actually, if the data is already sorted, creating the tree should be O(N) 
cost.  At each level, you're adding children to the same node.  You keep 
adding children until you hit a limit (I'd suggest 3k/4 as a good limit). 
When one node is full, you create a new node (adding it to the next layer 
up) and start adding elements to it.  When you're done adding children, if 
the current node you're adding to has less than k/2 nodes, it gets merged 
with it's previous sibling.  Proving that this is O(N) total cost is left 
as an exercise to the reader.

Brian