BetrFS: an in-kernel file system that uses Bε trees to organize on-disk storage

Re:BetrFS: an in-kernel file system that uses Bε trees to or... by mbravenboer on Wednesday December 01, 2021 @03:44PM (#29408900)

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.

[ Parent | on HN ]

Re:BetrFS: an in-kernel file system that uses Bε trees to or... by mirekrusin on Thursday December 02, 2021 @06:04AM (#29414703)

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?

[ Parent | on HN ]

Re:BetrFS: an in-kernel file system that uses Bε trees to or... by mbravenboer on Thursday December 02, 2021 @03:54PM (#29422391)

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).

[ Parent | on HN ]