What is Tokutek's Fractal Index actually and how the used COLA?

1 point

11 years ago

There are 3 kinds of write optimized data structures (not including LSM) mentioned in connection to Fractal Index (by Tokutek):

1) Buffered repository trees of any kind. Related publications with the same idea: - http://www.cc.gatech.edu/~bader/COURSES/GATECH/CSE-Algs-Fall2013/papers/Arg03.pdf - http://cs.slu.edu/~goldwasser/publications/SODA2000.pdf

2) COLA (cache-oblivious lookahead (forward pointers) array). - http://supertech.csail.mit.edu/papers/sbtree.pdf

3) Shuttle trees: - http://supertech.csail.mit.edu/papers/sbtree.pdf

What data structure is actually called a "Fractal Tree Index"?

How COLAs used exactly in real software? Is COLA used as a small buffers for buffered tree or it handle terabytes of data in real applications? Why someone would prefer to use COLA instead of buffered tree?

Speaking of buffered tree by Lars Arge: as far as i understand, the "buffers" may be stored in external memory and the "buffers" may have size of entire RAM: the only requirement is to fit into memory for sorting before pushing one level down?

Why someone would prefer to use such a large external memory "buffers" instead of using smaller buffers of size B on every internal node?