[geocar]

The page table on x86/amd64 is a trie. OSDEV[1] has a pretty good page on it.

All you need to remember is that this is what is inside the operating system and hardware layers, so you're already paying for it. What I propose is taking advantage of it. If you can arrange things correctly (see my other comment describing this more fully[2]) you might find things that seem expensive (when dealing only with von neumann memory) are suddenly very cheap when you accept you're programming a piece of real hardware.

[1]: http://wiki.osdev.org/Page_Tables

[2]: https://news.ycombinator.com/item?id=13269288