What I don't understand though is why it wouldn't make sense to sort the keys that are looked for first and look them up in order while traversing the tree. See

What I don't understand though is why it wouldn't make sense to sort the keys that are looked for first and look them up in order while traversing the tree. Seems much better from a cacheing perspective.. EDIT: Ah, each look-up was in different trees. That takes away that optimization.