See user `fluffything`'s comment on this same thread: https://news.ycombinator.com/item?id=23895629, describing this approach (Eytzinger layout).

Yes, although the design space explodes once you can reorder, so it's also interesting to consider the restricted problem where you can't reorder. This is still realistic since in many scenarios the layout may be fixed by an external constraint.

A levelwise traversal usually performs well without much effort if you want to optimize for cache friendliness. It's not optimal iirc, but it's dead-simple and much easier on the prefetcher than an inorder traversal.

Edit: Oops, TIL the eytzinger layout other comments have mentioned _is_ a levelwise traversal. Anywho, it's usually a good starting point for this kind of thing.

Binary search is used when you can't optimize the data structure. You have a sorted array, and have to work with that.

If you store the middle element together with its first two quartiles, you're making a B-tree. You will need indirection (pointers) to locate the other chunks that are not stored together and so it goes.

"Binary search" usually refers to the sorted array algorithm, though of course in the abstract sense of subdivision, any subdivision-by-two search is binary and in that sense we have the term "binary search tree".