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?