Suggested Final Project Topics

Why they're worth studying: B+ trees are used in production file systems (the common Linux ext fam-

ily of file systems are layered on B+ trees) and several production databases. If you're interested in explor-

ing a data structure that's been heavily field-tested and optimized, this would be a great one to look at!

---

 7 / 22

Cache-Oblivious Binary Search Trees

To get maximal efficiency from a B-tree, it's necessary to know something about the size of the disk pages

or cache lines in the machine. What if we could build a BST that minimized the number of cache misses

during core operations without having any advance knowledge of the underlying cache size? Such a BST

is called a  cache-oblivious binary search tree  and, amazingly enough, we know how to design them by

adapting techniques from van Emde Boas trees.