inline index nodes with eytzinger layouts

[spacejam]

https://arxiv.org/pdf/1509.05053.pdf

We spend a lot of time doing binary search in index nodes to find an interesting leaf. This is partially because we don't do interpolation search, but mostly because we are very cache inefficient. Index keys tend to be very short due to the combination of prefix compression and suffix truncation, and the current IVec implementation that inlines up to 22 bytes wastes a ton of space for these short items. A path forward is to inline everything, and use an eytzinger layout. We don't want to use this for leaf nodes too because of the cost it imposes on sequential workloads, but it's probably a great choice for index nodes that point to the leaves.

Over time, we may also experiment with a novel (as far as I know) form of interpolation search that is eytzinger-aware, combining ideas from slope-reuse interpolation search & three-point interpolation search.

http://pages.cs.wisc.edu/~chronis/files/efficiently_searching_sorted_arrays.pdf

It will be interesting to measure various combinations of interpolation search with and without eytzinger layouts, but I suspect that these interesting interpolation search techniques are compatible with eytzinger's cache friendliness and we may be able to achieve nice things by using all of these techniques.