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@nasby.net
EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)