Re: Fast insertion indexes: why no developments

2013/11/12 Claudio Freire <klaussfreire(at)gmail(dot)com>:

> On Tue, Nov 12, 2013 at 6:41 PM, Nicolas Barbier
> <nicolas(dot)barbier(at)gmail(dot)com> wrote:
>
>> (Note that K B-trees can be merged by simply scanning all of them
>> concurrently, and merging them just like a merge sort merges runs.
>> Also, all B-trees except for the first level (of size S) can be
>> compacted 100% as there is no need to reserve space for further
>> insertions in them.)
>
> Unless you can guarantee strong correlation of index-order vs
> physical-order, scanning multiple indexes in index-order will be quite
> slow (random I/O).

As all the bigger trees are written in one pass (as the result of a
merge of multiple smaller trees), I would assume that it is rather
easy to guarantee it for them.

As for the smallest trees (size S), I think it doesn’t matter much as
they “fit easily in memory.” Initially I would say that redefining it
so that K of them (rather than 1) must still fit in memory is the easy
fix.

A future optimization could alleviate the need for the redefinition
(and would also improve normal B-tree indexes): Somehow make sure that
smaller trees (that fit in memory) are typically written out
more-or-less in the right order. For that, one could for example
postpone determining the ultimate block-order to write-out time. This
is similar to what Reiser4 calls “dancing trees,” but unfortunately
requires some rejiggering of the abstraction layers on PostgreSQL (I
think). Having deferred insertion (which is probably way easier to
implement) could conceivably also improve things.

<URL:https://en.wikipedia.org/wiki/Dancing_tree>

Nicolas

--
A. Because it breaks the logical sequence of discussion.
Q. Why is top posting bad?