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 6D8C5BB9C for ; Thu, 17 Nov 2005 18:31:54 +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 jAHHVr83029194 for ; Thu, 17 Nov 2005 18:31:53 +0100 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA23713 for ; Thu, 17 Nov 2005 18:31:53 +0100 (MET) Received: from smtp1.adl2.internode.on.net (smtp1.adl2.internode.on.net [203.16.214.181]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jAHHVpZo018188 for ; Thu, 17 Nov 2005 18:31:52 +0100 Received: from rosella (ppp7-104.lns1.syd7.internode.on.net [59.167.7.104]) by smtp1.adl2.internode.on.net (8.12.9/8.12.6) with ESMTP id jAHHVctj045965; Fri, 18 Nov 2005 04:01:39 +1030 (CST) (envelope-from skaller@users.sourceforge.net) Subject: Re: [Caml-list] [1/2 OT] Indexing (and mergeable Index-algorithms) From: skaller To: Brian Hurt Cc: Oliver Bandel , caml-list@inria.fr In-Reply-To: References: <20051116234238.GA5741@first.in-berlin.de> <1132215328.9775.110.camel@rosella> Content-Type: text/plain Date: Fri, 18 Nov 2005 04:31:38 +1100 Message-Id: <1132248698.9668.44.camel@rosella> Mime-Version: 1.0 X-Mailer: Evolution 2.4.1 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 437CBE89.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 437CBE87.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 sourceforge:01 balanced:03 brian:04 long:05 thu:05 thu:05 accesses:07 lookup:07 disagree:07 john:08 felix:08 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, 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. -- John Skaller Felix, successor to C++: http://felix.sf.net