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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 4041CBB9C for ; Thu, 17 Nov 2005 19:03:55 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jAHI3s6l021514 for ; Thu, 17 Nov 2005 19:03:54 +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 TAA24423 for ; Thu, 17 Nov 2005 19:03:54 +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 jAHI3rWg032241 for ; Thu, 17 Nov 2005 19:03:53 +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 0E0478BA9; Thu, 17 Nov 2005 12:03:53 -0600 (CST) Date: Thu, 17 Nov 2005 12:08:35 -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: <1132248698.9668.44.camel@rosella> Message-ID: References: <20051116234238.GA5741@first.in-berlin.de> <1132215328.9775.110.camel@rosella> <1132248698.9668.44.camel@rosella> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Miltered: at concorde with ID 437CC60A.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 437CC609.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 indexing:01 wrote:01 wrote:01 balanced:03 root:03 leaf:04 leaf:04 brian:04 brian:04 long:05 fri:05 thu:05 thu:05 accesses:07 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 Fri, 18 Nov 2005, skaller wrote: > On Thu, 2005-11-17 at 09:09 -0600, Brian Hurt wrote: >> >> 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. > > I'm not sure what it is we disagree on. They don't ever need global rebalancing. Since levels are only added or removed at the top, the distance between the root and any leaf is the same as any other leaf, at all times. Brian