Re: Fractal tree indexing

On 13.02.2013 17:49, Atri Sharma wrote:
> On 13-Feb-2013, at 20:30, Tom Lane<tgl@sss.pgh.pa.us>  wrote:
>
>> First explain why you couldn't build it as an opclass for gist or
>> spgist ...
>
> That needs thinking about a bit.I was confused about the current indexes because they all build on BTrees.But,
buildingan opclass with GiST should be a good solution.
 

That makes no sense. I don't see any way to implement this in an 
opclass, and it wouldn't make sense to re-implement this for every 
opclass anyway.

The basic idea of a fractal tree index is to attach a buffer to every 
non-leaf page. On insertion, instead of descending all the way down to 
the correct leaf page, the new tuple is put on the buffer at the root 
page. When that buffer fills up, all the tuples in the buffer are 
cascaded down to the buffers on the next level pages. And recursively, 
whenever a buffer fills up at any level, it's flushed to the next level. 
This speeds up insertions, as you don't need to fetch and update the 
right leaf page on every insert; the lower-level pages are updated in 
batch as a buffer fills up.

As I said earlier, this is very similar to the way the GiST buffering 
build algorithm works. It could be applied to any tree-structured access 
method, including b-tree, GiST and SP-GiST.

- Heikki