Re: Block B-Tree concept

Martijn van Oosterhout wrote:
> On Fri, Sep 29, 2006 at 10:51:32AM +0100, Heikki Linnakangas wrote:
>> After some thought:
>>
>> Imagine a normal B-tree just like what we have now. But when there is
>> more than one tuple on the same heap page with consecutive index keys,
>> we represent all of them in a single index tuple that contains the key
>> of the first one of them, and a (run-length encoded) bitmap of the
>> OffsetNumbers. We should get most of the space and I/O savings as with
>> the original proposal, but we can vacuum it without re-evaluating index
>> expressions.
>
> I think something like this has been discussed before. Where an index
> tuple currently has the key values followed by a ctid, simply change
> that so that it can be a list of ctid's, in order.

Actually it's t_tid followed by t_info (which is size + flags) followed
by key values.

> This works on having the same key, but doesn't care if the tuples are
> on the same page. It used to be not possible because of how to handle
> forward and backward scanning within an index entry during updates. I
> think with the new "page at a time" index scanning, this got a lot
> easier.

I'm not very interested in the case where you have a lot of equal keys,
I think the bitmap index am is more suitable for that. The Block B-tree
could be used whenever you have a clustered table (including unique
indexes). Some DBMSs have index-organized-tables for the same use case.

When I tested a prototype of the original idea with TPC-C (DBT-2) data,
a block index on the order_line table was under 2% of the size of a
normal B-tree. That's very close to a best-case scenario; narrow rows
and a completely clustered table. I'm aiming at that order of magnitude
reduction in storage size.

> One issue is that a single index page could hold more than 1000 index
> entries, which might cause problems for callers.

I don't think that's a problem.

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