Re: Block B-Tree concept

Tom Lane wrote:
> Heikki Linnakangas <heikki@enterprisedb.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