4 ms·

I'm unfamiliar with this particular implementation, but it sounds (from your one sentence description) kinda like Dancing Trees, created by Hans Reiser, for Rei

I'm unfamiliar with this particular implementation, but it sounds (from your one sentence description) kinda like Dancing Trees, created by Hans Reiser, for ReiserFS. Would this be prior art, or would this be different approaches to similar problems? http://en.wikipedia.org/wiki/Dancing_tree http://en.wikipedia.org/wiki/Dancing_tree

carterschonwald 14y ago
Yes and no. I think they're doing a variant of cache oblivious buffered B epsilon trees. Ill have to go code spelunking (now that the source is available. Boy am I glad it's gplv2 and not some (a)gplv3 variant). Thanks for the interesting reference!
- mjn 14y ago
  For the patent side of things, it being GPLv2 is sort of unfortunate compared to GPLv3, because v3 contains a patent grant, whereas v2 doesn't. It's possible some kind of implicit patent grant could be read into it by a court, e.g. that by open-sourcing some software, a company is making an open offer to use/modify the software, and then if they turned around and sued you for doing so, some equitable doctrine like estoppel would stand in the way. But an explicit patent grant is a lot clearer. For companies wary of v3 for other reasons, I wonder if there's an easy/semi-standardized way to tack on a patent grant? I'd feel much safer using open-source software licensed under some kind of "MIT + patent grant" or "GPLv2 + patent grant" license than the vanilla versions.
  - carterschonwald 14y ago
    Eeek. Didn't realize there was that delta on patents on v2 vs v3. Was aware of that problem with MIT/bsd though. Apache2 kinda is the MIT/bsd with explicit patent grants I guess. I suppose that idemnification from code patent issues is probably part of the commercial license / product then?
  - bradleykuszmaul 14y ago
    If you are interested in this, you should look at our source distribution's license file. We have done the work to get a patent license from MIT, Stony Brook, and Rutgers so that the users of the GPL'd code can use the fractal tree patents. Indemnification is a completely different issue: no open source software that I know of provides any kind of indemnification which would protect you from a lawsuit by a third party. -Bradley (bradley@tokutek.com)
    - mjn 14y ago
      Ah excellent, sorry for missing that. Yeah, I was just looking for a patent grant, not indemnification. I saw the notice of GPLv2, but hadn't seen the additional terms. If anyone else is looking for those, they're located here (possibly among other places): https://github.com/Tokutek/ft-index/blob/master/README-TOKUDB https://github.com/Tokutek/ft-index/blob/master/README-TOKUD... (ctrl+f "PATENT RIGHTS GRANT").
    - carterschonwald 14y ago
      Could you elaborate on the meaning of the phrase "this implementation"? Eg if I write some apache2 Haskell code that can interact seamlessly with the rest of the storage engine implementation, and I swap that part In, is that still the same implementation?
leif 14y ago
Fractal Tree indexes are very different from Dancing Trees. See http://tokutek.com/what-is-a-fractal-tree http://tokutek.com/what-is-a-fractal-tree for an overview, and I'd be happy to answer questions if you have them.
- SwellJoe 14y ago
  Hmmm, after reading the simple explanation PDF of Fractal Trees, they sound more like Dancing Trees than I'd assumed, but I am a poorly informed outsider. The key feature, from a performance perspective, is that writes are minimized by making each write do more, though both also help with SSD wear as a side effect. So, from the outside, it looks like both accomplish many of the same goals, and they do it by fundamentally altering B-tree implementation with modern hardware in mind. But, this isn't my area. I only have a passing understanding of Dancing Trees (my previous business led me to following ReiserFS closely, but I haven't paid any attention to filesystem or database performance in 7+ years), and no real understanding of Fractal Trees. I'm glad it's Open Source, however, and thanks for the pointers.
  - leif 14y ago
    Dancing Trees are algorithmically the same as B+ trees, if I understand the wikipedia article correctly. With just a uniformly random workload with a large enough working set, one would behave pretty much exactly the same as a B+ tree.

carterschonwald 14y ago

Yes and no. I think they're doing a variant of cache oblivious buffered B epsilon trees. Ill have to go code spelunking (now that the source is available. Boy am I glad it's gplv2 and not some (a)gplv3 variant). Thanks for the interesting reference!

mjn 14y ago
For the patent side of things, it being GPLv2 is sort of unfortunate compared to GPLv3, because v3 contains a patent grant, whereas v2 doesn't. It's possible some kind of implicit patent grant could be read into it by a court, e.g. that by open-sourcing some software, a company is making an open offer to use/modify the software, and then if they turned around and sued you for doing so, some equitable doctrine like estoppel would stand in the way. But an explicit patent grant is a lot clearer. For companies wary of v3 for other reasons, I wonder if there's an easy/semi-standardized way to tack on a patent grant? I'd feel much safer using open-source software licensed under some kind of "MIT + patent grant" or "GPLv2 + patent grant" license than the vanilla versions.
- carterschonwald 14y ago
  Eeek. Didn't realize there was that delta on patents on v2 vs v3. Was aware of that problem with MIT/bsd though. Apache2 kinda is the MIT/bsd with explicit patent grants I guess. I suppose that idemnification from code patent issues is probably part of the commercial license / product then?
- bradleykuszmaul 14y ago
  If you are interested in this, you should look at our source distribution's license file. We have done the work to get a patent license from MIT, Stony Brook, and Rutgers so that the users of the GPL'd code can use the fractal tree patents. Indemnification is a completely different issue: no open source software that I know of provides any kind of indemnification which would protect you from a lawsuit by a third party. -Bradley (bradley@tokutek.com)
  - mjn 14y ago
    Ah excellent, sorry for missing that. Yeah, I was just looking for a patent grant, not indemnification. I saw the notice of GPLv2, but hadn't seen the additional terms. If anyone else is looking for those, they're located here (possibly among other places): https://github.com/Tokutek/ft-index/blob/master/README-TOKUDB https://github.com/Tokutek/ft-index/blob/master/README-TOKUD... (ctrl+f "PATENT RIGHTS GRANT").
  - carterschonwald 14y ago
    Could you elaborate on the meaning of the phrase "this implementation"? Eg if I write some apache2 Haskell code that can interact seamlessly with the rest of the storage engine implementation, and I swap that part In, is that still the same implementation?

leif 14y ago

Fractal Tree indexes are very different from Dancing Trees. See http://tokutek.com/what-is-a-fractal-tree http://tokutek.com/what-is-a-fractal-tree for an overview, and I'd be happy to answer questions if you have them.

SwellJoe 14y ago
Hmmm, after reading the simple explanation PDF of Fractal Trees, they sound more like Dancing Trees than I'd assumed, but I am a poorly informed outsider. The key feature, from a performance perspective, is that writes are minimized by making each write do more, though both also help with SSD wear as a side effect. So, from the outside, it looks like both accomplish many of the same goals, and they do it by fundamentally altering B-tree implementation with modern hardware in mind. But, this isn't my area. I only have a passing understanding of Dancing Trees (my previous business led me to following ReiserFS closely, but I haven't paid any attention to filesystem or database performance in 7+ years), and no real understanding of Fractal Trees. I'm glad it's Open Source, however, and thanks for the pointers.
- leif 14y ago
  Dancing Trees are algorithmically the same as B+ trees, if I understand the wikipedia article correctly. With just a uniformly random workload with a large enough working set, one would behave pretty much exactly the same as a B+ tree.