Hacker News Reader

Wasn't tokutek's, now part of percona, fractal tree open source _BUT_ patented?

edit: yes, it seems [0]

[0] https://github.com/Tokutek/ft-index/blob/master/PATENTS

Be-trees were invented in 2003, predating the Tokutek patent: see citation [1] in http://supertech.csail.mit.edu/papers/BenderFaJa15.pdf . I think Tokutek was originally not aware of Be-trees and only later discovered the similarity to Be-trees.

This paper (from 2015) seems to be saying that:

"(...) The Bε-tree has since been used by both the high-performance, commercial TokuDB database [4] and the BetrFS research file system [5]. (...)"

First citation from the paper links to http://perso.ens-lyon.fr/loris.marchal/docs-data-aware/broda... – is this the paper you're referring to as prior-art for Bε-trees?

Yeah, though I'm not a laywer and I have not personally studied the Tokutek patent in detail. I did consult at some point on this with somebody experienced in database-related software patents, but please do not take legal advice from me :).

My understanding is that Be-trees are not covered by a valid patent, either because of clear prior art or because Tokutek patented a different data structure. Be-trees are simpler than the original fractal tree afaik (they were not aware of Be-trees at the time of their innovation).

Reply on news.ycombinator.com