Version française
Home     About     Download     Resources     Contact us    

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

Browse thread
[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 (18:03)
From: Brian Hurt <bhurt@s...>
Subject: Re: [Caml-list] [1/2 OT] Indexing (and mergeable Index-algorithms)

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.