Please consider COLA: http://people.seas.harvard.edu/~minilek/cs229r/fall13/lec/lec23.pdf http://people.seas.harvard.edu/~minilek/cs229r/fall13/lec/le... A hie

Please consider COLA: http://people.seas.harvard.edu/~minilek/cs229r/fall13/lec/lec23.pdf http://people.seas.harvard.edu/~minilek/cs229r/fall13/lec/le... 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.