Re: Fractal tree indexing

On 13.02.2013 17:49, Atri Sharma wrote:
> On 13-Feb-2013, at 20:30, Tom Lane<tgl(at)sss(dot)pgh(dot)pa(dot)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, building an 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