Re: Block B-Tree concept

Tom Lane wrote:
> Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
>
>> I don't mean consecutive as in "1, 2, 3, 4, ... without gaps" but as in
>> "A and B are consecutive in the index, if there's no value X in the
>> index so that A < X < B". Maybe there's a better word for that.
>>
>
> Um, but how are you going to make that work without storing the keys for
> both A and B? You won't be able to tell whether an incoming key C
> that's just a bit bigger than A should go before or after B.
>

Let me describe the insertion algorithm:

1. To insert a tuple with key X, we find the position in the index where
the new tuple would go, just like with a normal B-tree. Let's call the
index tuple right before the position A and the next tuple B. So
according to normal B-tree rules, X should go between A and B.

2. If A points to the same heap page as X, we set the bit representing
the offset of the new tuple in the index tuple A (this might require
enlarging the index tuple and event splitting the page), and we're done.
If it points to a different page, we need split the range A-B to A-X-B,
proceed to step 3.

3. To split the range A-B, scan the heap page to see which of the tuples
pointed to by A are >= X and which are < X . If there's no tuples >= X,
insert a new index tuple for X, and we're done. Otherwise, let Y be the
smallest tuple >= X. Insert a new index tuple for Y, containing all the
offsets with keys >= X, and remove those offsets from A. We have now
split A-B to A-Y-B so that A < X < Y < B.

4. Insert the new index tuple for X.

(I'm not sure I got the above description correct for cases with equal
keys.)

Note that we don't keep track of the ordering of tuples that are clumped
into a single index tuple. That's not important, I/O wise, because if
you're going to fetch a heap page into memory, you might as well scan
all the tuples on it and sort them if necessary. That's where the space
and I/O savings comes from.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com