B-tree indexes, interpolation search, and skew

B-tree indexes, interpolation search, and skew,10.1145/1140402.1140409,Goetz Graefe

B-tree indexes, interpolation search, and skew   (Citations: 5)
BibTex | RIS | RefWorks Download
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.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Thus, today’s databases ought to employ large I/Os [12], and techniques are needed that complement large pages, e.g., interpolation search [7] and master-detail clustering...

    Goetz Graefe. Master-detail clustering using merged indexes

    • ...For example, a B-tree index with a hash value as leading key field permits very efficient search based on fast comparisons as well as interpolation search rather than binary search [27]...
    • ...Other techniques for the same purpose include interpolation search [27] and pointer swizzling [58] among index pages in the buffer pool...

    Goetz Graefe. New algorithms for join and grouping operations

Sort by: