Re: Fractal tree indexing

On Wed, Feb 13, 2013 at 8:20 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Heikki Linnakangas <hlinnakangas(at)vmware(dot)com> writes:
>> 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.
>
> [ scratches head... ] What's "fractal" about that? Or is that just a
> content-free marketing name for this technique?

The name in the literature is "Cache Oblivious Lookahead Array", aka
COLA. The authors also are founders of TokuTek, and seemed to have
take pains to ring-fence mentions of the algorithm with reference to
its patent.

Well, at least nobody can blame them for submarine patent action.

--
fdr