The sardine tree we developed in our last lecture gives a fast ordered dictionary data structure for small keys. By harnessing its key insight - B-tree lookups can be sped up by improving rank calculations at each node - and combining it with some insights about integers and Patricia tries, we can build the fusion tree, which works for any integers that fit into a machine word.
Readings
- Michael Fredman and Dan Willard. Surpassing the Information-Theoretic Bound with Fusion Trees
Links