2 ms·
...tell me how to make something just like a b-tree, but faster If you wanted to do that on modern multilayer-memory architecture, you would use a "cache-obvio
by joe_the_user 12y ago
...tell me how to make something just like a b-tree, but faster
If you wanted to do that on modern multilayer-memory architecture, you would use a "cache-obvious" structure like cache-oblivious b-tree, cache-oblivious Lookahead Array and similar structures. Because these kinds of structures allow large and small scale locality of data, meaning that a disk-read will pull several pieces of data at once, a jump between nodes produces fewer cache misses (at each level) and so-forth.
Michael A. Bender wrote of the original papers on cache oblivious structures and not coincidentally is TokuTek founder.
http://www.tokutek.com/company/team/ http://www.tokutek.com/company/team/
http://en.wikipedia.org/wiki/Cache-oblivious_algorithm http://en.wikipedia.org/wiki/Cache-oblivious_algorithm
http://supertech.csail.mit.edu/cacheObliviousBTree.html http://supertech.csail.mit.edu/cacheObliviousBTree.html