From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 2A458BB9C for ; Thu, 17 Nov 2005 16:04:52 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jAHF4pdq013646 for ; Thu, 17 Nov 2005 16:04:51 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA20171 for ; Thu, 17 Nov 2005 16:04:51 +0100 (MET) Received: from conn.mc.mpls.visi.com (conn.mc.mpls.visi.com [208.42.156.2]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id jAHF4obx013631 for ; Thu, 17 Nov 2005 16:04:50 +0100 Received: from [192.168.42.2] (bhurt.dsl.visi.com [208.42.141.66]) by conn.mc.mpls.visi.com (Postfix) with ESMTP id 2E5F58BD0; Thu, 17 Nov 2005 09:04:47 -0600 (CST) Date: Thu, 17 Nov 2005 09:09:29 -0600 (CST) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: skaller Cc: Oliver Bandel , caml-list@inria.fr Subject: Re: [Caml-list] [1/2 OT] Indexing (and mergeable Index-algorithms) In-Reply-To: <1132215328.9775.110.camel@rosella> Message-ID: References: <20051116234238.GA5741@first.in-berlin.de> <1132215328.9775.110.camel@rosella> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Miltered: at nez-perce with ID 437C9C13.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 437C9C12.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 indexing:01 node:01 node:01 nodes:01 nodes:01 in-memory:01 binary:01 binary:01 algebra:01 inserting:01 variants:01 wrote:01 structures:01 structures:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 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