B-tree indexes, interpolation search, and skew
Recent performance improvements in storage hardware have benefited bandwidth much more than latency. Among other implications, this trend favors large B-tree pages. Re- cent performance improvements in processor hardware also have benefited processing bandwidth much more than memory latency. Among other implications, this trend fa- vors adding calculations if they save cache faults. With small calculations guiding the search directly to the desired key, interpolation search complements these trends much better than binary search. It performs well if the distribution of key values is perfectly uniform, but it can be useless and even wasteful otherwise. This paper collects and describes more than a dozen techniques for interpola- tion search in B-tree indexes. Most of them attempt to avoid skew or to detect skew very early and then to avoid its bad effects. Some of these methods are part of the folklore of B- tree search, whereas other techniques are new. The purpose of this survey is to encourage research into such techniques and their performance on modern hardware.