Re: Block B-Tree concept

On Tue, Sep 26, 2006 at 11:16:54AM +0100, Heikki Linnakangas wrote:
> To locate the actual matching items on the heap page, we have to scan
> the heap page because we don't have the item ids, so this is a tradeoff
> between CPU and I/O. However, we could have a hybrid where we initially
> store heap tuple pointers like we do now, and when there's more than X
> consecutive pointers to the same page, we collapse them to just one
> pointer to the whole page. This would potentially give us the best of
> both worlds.
>
> This design is more flexible and less invasive than true
> index-organized-tables, because it doesn't require perfect ordering of
> the heap or moving heap tuples around. You can also define than one
> Block B-Tree on a table, though you wouldn't get much benefit from using
> Block B-Tree instead of normal B-Tree if there's no correlation between
> the index order and the heap order.

No, but I think there's scenarios where you may not have extremely high
correlation but you'd still benefit, especially with the hybrid
approach. If you have a field with rather skewed histogram, for example,
where you're likely to have a lot of tuples with one value on any given
page. Of course, you probably would want to exclude that value from the
index entirely if it's on *every* page, but anything where you see
paterns of data wouldn't be like that.
--
Jim Nasby jim(at)nasby(dot)net
EnterpriseDB http://enterprisedb.com 512.569.9461 (cell)