B-tree indexes, interpolation search, and skew

ABSTRACT

Recent performance improvements in storage hardware have benefited bandwidth much more than latency. Among other implications, this trend favors large B-tree pages. Recent performance improvements in processor hardware also have benefited processing bandwidth much more than memory latency. Among other implications, this trend favors 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 interpolation 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.

REFERENCES

• 1: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , David A. Wood, DBMSs on a Modern Processor: Where Does Time Go?, Proceedings of the 25th International Conference on Very Large Data Bases, p.266-277, September 07-10, 1999
• 2: Gennady Antoshenkov , David B. Lomet , James Murray, Order Preserving Compression, Proceedings of the Twelfth International Conference on Data Engineering, p.655-663, February 26-March 01, 1996
• 3: {BM 70} Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indexes. SIGFIDET Workshop 1970: 107--141.
• 4: {BM 72} Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173--189 (1972).
• 5: Peter A. Boncz , Stefan Manegold , Martin L. Kersten, Database Architecture Optimized for the New Bottleneck: Memory Access, Proceedings of the 25th International Conference on Very Large Data Bases, p.54-65, September 07-10, 1999
• 6: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• 7: {C 77} W. M. Conner: Offset Value Coding. IBM Technical Disclosure Bulletin 20(7), 2832--2837 (1977).
• 8: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 9: {DR 01} Kurt W. Deschler, Elke A. Rundensteiner: B+ Retake: Sustaining High Volume Inserts into Large Data Pages. DOLAP 2001.
• 10: R. F. Deutscher , P. G. Sorenson , J. P. Tremblay, Distribution-dependent hashing functions and their characteristics, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500111]
• 11: Anil K. Garg , C. C. Gotlieb, Order-preserving key transformations, ACM Transactions on Database Systems (TODS), v.11 n.2, p.213-234, June 1986 [doi>10.1145/5922.5923]
• 12: Jim Gray , Goetz Graefe, The five-minute rule ten years later, and other computer storage rules of thumb, ACM SIGMOD Record, v.26 n.4, p.63-68, Dec. 1997 [doi>10.1145/271074.271094]
• 13: Goetz Graefe , Per-Åke Larson, B-Tree Indexes and CPU Caches, Proceedings of the 17th International Conference on Data Engineering, p.349-358, April 02-06, 2001
• 14: {GR 93} Jim Gray, Andreas Reuter: Transaction processing concepts and techniques. Morgan-Kaufman, San Mateo, CA, 1993.
• 15: {GZ 04} Goetz Graefe, Michael J. Zwilling: Transaction support for indexed views. SIGMOD 2004: 323--334.
• 16: David Lomet, B-tree page size when caching is considered, ACM SIGMOD Record, v.27 n.3, p.28-32, Sept. 1, 1998 [doi>10.1145/290593.290598]
• 17: David Lomet, The evolution of effective B-tree: page organization and techniques: a personal account, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603878]
• 18: Witold Litwin , David B. Lomet, The Bounded Disorder Access Method, Proceedings of the Second International Conference on Data Engineering, p.38-48, February 05-07, 1986
• 19: Chris Nyberg , Tom Barclay , Zarka Cvetanovic , Jim Gray , Dave Lomet, AlphaSort: a RISC machine sort, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.233-242, May 24-27, 1994, Minneapolis, Minnesota, United States
• 20: Patrick E. O'Neil, The Escrow transactional method, ACM Transactions on Database Systems (TODS), v.11 n.4, p.405-430, Dec. 1986 [doi>10.1145/7239.7265]
• 21: Patrick E. O'Neil, The SB-tree: an index-sequential structure for high-performance sequential access, Acta Informatica, v.29 n.3, p.241-265, June 1992 [doi>10.1007/BF01185680]
• 22: {P 57} W. W. Peterson: Addressing for Random-Access Storage. IBM J. Res. Development 1(4), 1957, 130--146.
• 23: Yehoshua Perl , Alon Itai , Haim Avni, Interpolation search—a log logN search, Communications of the ACM, v.21 n.7, p.550-553, July 1978 [doi>10.1145/359545.359557]
• 24: {SAB 05} Michael Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Samuel Madden, Elizabeth J. O'Neil, Patrick E. O'Neil, Alex Rasin, Nga Tran, S. B. Zdonik: C-Store: A Column-oriented DBMS. VLDB 2005: 553--564.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Performance