Sorry for the blatant plug, but it might be relevant — in my M.Sc. thesis I surveyed main memory optimized index techniques and also provided some background fo

Sorry for the blatant plug, but it might be relevant — in my M.Sc. thesis I surveyed main memory optimized index techniques and also provided some background for why traditional binary search is not very optimized for modern hardware. There's lots of illustrations and I cite some great material. :) See here: https://www.researchgate.net/profile/Florian_Gross/publication/275971053_Index_Search_Algorithms_for_Databases_and_Modern_CPUs/links/554cffca0cf29f836c9cd539.pdf https://www.researchgate.net/profile/Florian_Gross/publicati... Along those lines: * CSS Trees: Pointerless b-Trees with a layout optimized for cache lines (http://www.vldb.org/conf/1999/P7.pdf http://www.vldb.org/conf/1999/P7.pdf) * Intel & Oracle's fast architecture-sensitive tree search (combines huge pages, cache line blocking, and SIMD in an optimal layout): http://www.researchgate.net/profile/Jatin_Chhugani/publication/221213860_FAST_fast_architecture_sensitive_tree_search_on_modern_CPUs_and_GPUs/links/0c96051f5d2990770d000000.pdf http://www.researchgate.net/profile/Jatin_Chhugani/publicati... * Adaptive radix trees (http://codematch.muehe.org/~leis/papers/ART.pdf http://codematch.muehe.org/~leis/papers/ART.pdf)