Re:An Introduction to Cache-Oblivious Data Structures
by elvinyung on Tuesday February 06, 2018 @02:09PM
(#16318619)
Dumb question: is it appropriate to describe fractal trees as an "extreme" version of a log-structured merge tree? At a glance (i.e. if you squint really hard), the buffer flushing process in a fractal tree seems kind of similar to the tablet merging process in LSM trees in that they both batch operations to amortize secondary memory access costs, except fractal trees generalize it to all operations.
[ Parent
| on HN ]
Re:An Introduction to Cache-Oblivious Data Structures
by AstralStorm on Tuesday February 06, 2018 @04:27PM
(#16319954)
Yes, additionally fractal trees have a predictable and compact memory structure while LSMTs are more sparse.
Average case for queries is also better for fractal structure and implementation is actually easier.