Re: Block B-Tree concept

Tom Lane wrote:
> Heikki Linnakangas <heikki(at)enterprisedb(dot)com> writes:
>
>> I've been experimenting with the idea of a so-called Block B-Tree. The
>> basic idea is that instead of storing an index tuple for each heap
>> tuple, we store an index tuple for each heap block. This dramatically
>> reduces the size of an index, leading to savings on I/O.
>>
>
> VACUUM?
>
There's a few options that I've thought of this far:

1. Whenever a tuple is found dead on page X, vacuum of the index will
have to go to that page again to see if there's any matching tuples left.

2. Have a reference counter on index tuple that's increased on insert
and decreased by vacuum.

3. Do nothing. Let index scans mark the index tuple as dead when it's
convenient. There's no correctness problem with just leaving dead index
tuples there, because you have to check the index quals on each heap
tuple anyway when you scan.

3. probably isn't an option in itself, but we might want to do some kind
of a mixture of 1 and 3.

I'm thinking that Block B-Tree is not a candidate for non-MVCC system
catalogs, but I think that's OK.

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