This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

[1/2 OT] Indexing (and mergeable Index-algorithms)
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2005-11-17 (15:04) From: Brian Hurt Subject: Re: [Caml-list] [1/2 OT] Indexing (and mergeable Index-algorithms)
```

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

```