Re: Fast insertion indexes: why no developments

On Wed, Oct 30, 2013 at 9:23 AM, Leonardo Francalanci <m_lists(at)yahoo(dot)it> wrote:
>> LSM-trees seem patent free
>
> I'm no expert, and I gave it just a look some time ago: it looked to me very complicated to get right... and as far as I remember you don't get that much gain, unless you go multi-level which would complicate things further
>
>> Please somebody advise patent status of Y-trees otherwise I wouldn't bother.
>
> y-trees look much more easier to get right... (and to me they also make more sense, but I'm not skilled enough to judge).
>
> There's also the FD-tree, which looks a lot like the (patented...) fractal tree:
> http://www.ntu.edu.sg/home/bshe/fdtree_pvldb.pdf

Skimming the white paper, it's clear right from the start that they
make assumptions about the hardware that appear to be already obsolete
-- extremely poor write performance vs read performance of SSD.
Later generation SSDs are increasingly using hardware optimizations to
convert random writes to sequential writes using various tricks.

Point being: hardware is marching along pretty fast (after 20+ years
of stagnation) and it's dangerous (IMO) to make big software
investments based on the situation on the ground *today*.

merlin