  While a lot of work in theoretical computer science has gone into optimizing
the runtime and space usage of data structures, such work very often neglects a
very important component of modern computers: the cache. In doing so, very
often, data structures are developed that achieve theoretically-good runtimes
but are slow in practice due to a large number of cache misses. In 1999, Frigo
et al. introduced the notion of a cache-oblivious algorithm: an algorithm that
uses the cache to its advantage, regardless of the size or structure of said
cache. Since then, various authors have designed cache-oblivious algorithms and
data structures for problems from matrix multiplication to array sorting. We
focus in this work on cache-oblivious search trees; i.e. implementing an
ordered dictionary in a cache-friendly manner. We will start by presenting an
overview of cache-oblivious data structures, especially cache-oblivious search
trees. We then give practical results using these cache-oblivious structures on
modern-day machinery, comparing them to the standard std::set and other
cache-friendly dictionaries such as B-trees.
