From: Brian Hurt <bhurt@spnz.org>
To: skaller <skaller@users.sourceforge.net>
Cc: Oliver Bandel <oliver@first.in-berlin.de>, caml-list@inria.fr
Subject: Re: [Caml-list] [1/2 OT] Indexing (and mergeable Index-algorithms)
Date: Thu, 17 Nov 2005 12:08:35 -0600 (CST) [thread overview]
Message-ID: <Pine.LNX.4.63.0511171205570.24132@localhost.localdomain> (raw)
In-Reply-To: <1132248698.9668.44.camel@rosella>
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
next prev parent reply other threads:[~2005-11-17 18:03 UTC|newest]
Thread overview: 30+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-11-16 23:42 Oliver Bandel
2005-11-17 8:15 ` [Caml-list] " skaller
2005-11-17 15:09 ` Brian Hurt
2005-11-17 17:31 ` skaller
2005-11-17 18:08 ` Brian Hurt [this message]
2005-11-17 18:57 ` skaller
2005-11-17 22:15 ` Brian Hurt
2005-11-18 1:49 ` skaller
2005-11-17 8:35 ` Florian Hars
2005-11-17 9:24 ` Oliver Bandel
2005-11-17 12:39 ` Florian Weimer
2005-11-17 20:57 ` Oliver Bandel
2005-11-17 22:02 ` Florian Weimer
2005-11-17 11:49 ` Florian Weimer
2005-11-17 13:55 ` Richard Jones
2005-11-18 14:54 ` Jonathan Bryant
2005-11-18 14:22 ` Oliver Bandel
2005-11-18 14:37 ` Florian Weimer
2005-11-18 15:05 ` Thomas Fischbacher
2005-11-18 15:14 ` Florian Weimer
2005-11-18 16:03 ` Thomas Fischbacher
2005-11-18 20:03 ` Gerd Stolpmann
2005-11-18 20:01 ` Gerd Stolpmann
2005-11-18 21:12 ` Florian Weimer
2005-11-18 16:13 ` Oliver Bandel
2005-11-18 14:45 ` Florian Weimer
[not found] ` <437CD0E5.8080503@yahoo.fr>
2005-11-17 20:02 ` Oliver Bandel
[not found] ` <437CE8EC.1070109@yahoo.fr>
2005-11-17 20:41 ` Oliver Bandel
2005-11-18 15:06 ` Florian Hars
[not found] ` <437BD5F5.6010307@1969web.com>
2005-11-17 20:10 ` Oliver Bandel
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Pine.LNX.4.63.0511171205570.24132@localhost.localdomain \
--to=bhurt@spnz.org \
--cc=caml-list@inria.fr \
--cc=oliver@first.in-berlin.de \
--cc=skaller@users.sourceforge.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).