Re: Fast insertion indexes: why no developments

On Wed, Oct 30, 2013 at 10:53 AM, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:

> LSM-tree also covers the goal of maintaining just 2 sub-trees and a
> concurrent process of merging sub-trees. That sounds like it would
> take a lot of additional time to get right and would need some
> off-line process to perform the merge.
>

Not necessarily.

Merging means applying insertions/deletions from one subtree to another.
While it's normally preferable and more efficient to do it in batches, I've
successfully implemented in-memory versions that use other writers to
perform the task, amortizing the cost of merging across many operations. In
essence, when there's a need to merge two subtrees, an inserting process
also merges one entry, so slowly trees get merged. That works in-memory
very well, it's quite clear that it's not necessarily generalizable to
external storage, but it's a technique to have in mind.

Alternatively, vacuum could do it. It's quite clearly a vacuuming task
anyway.