4 ms·
Are there any comparisons between fractal trees and the database cracking/adaptive indices advocated by [1]? It seems like they're going after the same use patt
by bcoates 11y ago
Are there any comparisons between fractal trees and the database cracking/adaptive indices advocated by [1]? It seems like they're going after the same use pattern but cracking is relatively simpler and even faster for inserts.
[1] http://db.csail.mit.edu/pubs/abadi-column-stores.pdf http://db.csail.mit.edu/pubs/abadi-column-stores.pdf
- acomjean 11y agoNot that I know of. Interesting though. I have to look into column stores more though.
- leif 11y agoCracking is kind of similar in that it delays the "sorting work" done in the indexing structure. However, cracking is fairly heuristic and therefore hard to analyze without an intimate understanding of the workload. Fractal Trees do pretty much the same thing under all workloads (modulo optimizations for things like sequential and Zipfian workloads), so they're easier to analyze and prove bounds for. An interesting new development is http://getkudu.io/ http://getkudu.io/ which applies some ideas common with Fractal Trees and other write-optimized data structures (like LSM-trees) to column stores. At Tokutek, we had some designs for how to implement column store-like data models on Fractal Trees (we called them "matrix stores" because they had some of the benefits of both row stores and column stores), but we didn't get around to implementing them.