A hierarchy of sorted arrays, with merging when needed. Single access time is O(logN), scan is theoretically the fastest possible, inserts and deletes are also O(logN).

Almost no pointer chasing.