> 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