From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00
	autolearn=unavailable autolearn_force=no version=3.4.4
Path: 
 border1.nntp.ams.giganews.com!nntp.giganews.com!feeder.erje.net!eu.feeder.erje.net!newsfeed.fsmpi.rwth-aachen.de!news-1.dfn.de!news.dfn.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Niklas Holsti <niklas.holsti@tidorum.invalid>
Newsgroups: comp.lang.ada
Subject: Re: B-tree performance
Date: Sun, 01 Sep 2013 07:57:00 +0300
Organization: Tidorum Ltd
Message-ID: <b8fvorFdlvfU1@mid.individual.net>
References: <9fc26b8a-7a5c-4941-81cb-8f0e9c17a660@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: individual.net 7ybBx6qjOeUqRFOn8ix0rgTOr/13E22qNO0RSLcknk7ZQL/Ic4
Cancel-Lock: sha1:n7iVMRtFZjxjJnSG9asJfAnczVM=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6;
 rv:17.0) Gecko/20130801 Thunderbird/17.0.8
In-Reply-To: <9fc26b8a-7a5c-4941-81cb-8f0e9c17a660@googlegroups.com>
Xref: number.nntp.dca.giganews.com comp.lang.ada:183251
Date: 2013-09-01T07:57:00+03:00
List-Id: <comp.lang.ada>

On 13-08-31 10:14 , Peter Brooks wrote:
> I'm interested to know if anybody has any real-world evidence for
> this hypothesis, or if they agree with my gut feel.
> 
> If I build a B-tree, then the conventional means to search it would
> be to start in the middle, then cascade left and right following the
> pointer structure. That's slow because most searches won't turn up a
> value in the first N levels of the b-tree.

I find your question hard to understand. Are you really talking about
B-trees (http://en.wikipedia.org/wiki/B-tree), with fan-out typically
much larger than 2? Or are you talking about binary trees with 2-way
fan-out? Your phrase "left and right" suggests the latter.

> So it'd make sense to have an array which contains the address values
> of the B-tree down to a certain level. That way, for a look up, you
> search the array, which is nice and quick, and this leads you to the
> correct sub-tree and you then continue as usual, from the top of that
> sub-tree.

If you really mean B-trees, it seems to me that you could just increase
the fan-out of the B-tree to get the same effect. With a fan-out of say
4000, the root of the B-tree consists of a sorted array of 4000 (or
3999) key values, which is nice and quick to search.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
      .      @       .