Re: B-tree performance

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

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
      .      @       .