Re: B-tree performance

[Peter Brooks <peter.h.m.brooks@gmail.com>]

On Sunday, 1 September 2013 06:57:00 UTC+2, Niklas Holsti  wrote:
> 
> 
> 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.
> 
Yes, I think you're right. Though, because of clashes, leaf nodes can have many members, so it isn't quite a binary tree.
> 
> > 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.
> 
Yes, that is really my questions. Since the hash algorithm will produce a uniformly dense distribution, the array of key values that will fit best will be one that divides 64bit space up evenly.

My question is when you get diminishing returns from using a sorted array. Or, equivalently, what would be the optimal size of the array of key values?