The evolution of effective B-tree: page organization and techniques: a personal account

ABSTRACT

An under-appreciated facet of index search structures is the importance of high performance search within B-tree internal nodes. Much attention has been focused on improving node fanout, and hence minimizing the tree height [BU77, LL86]. [GG97, Lo98] have discussed the importance of B-tree page size. A recent article [GL2001] discusses internal node architecture, but the subject is buried in a single section of the paper.In this short note, I want to describe the long evolution of good internal node architecture and techniques, including an understanding of what problem was being solved during each of the incremental steps that have led to much improved node organizations.

REFERENCES

• 1: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , Marios Skounakis, Weaving Relations for Cache Performance, Proceedings of the 27th International Conference on Very Large Data Bases, p.169-180, September 11-14, 2001
• 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: Michael W. Blasgen , Richard G. Casey , Kapali P. Eswaran, An encoding method for multifield sorting and indexing, Communications of the ACM, v.20 n.11, p.874-878, Nov. 1977 [doi>10.1145/359863.359892]
• 4: {BM71} Bayer, R. and McCreight, E. Organization and Maintenance of Large Ordered Indexes. Acta Informatica 1 (1972) 173-189.
• 5: 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]
• 6: {Co80} Cohen, D. Byte Order: On Holey Wars and a Plea for Peace, USC/ISI (April 1980) at URL: http://www.rdrop.com/~cary/html/endian_faq.html
• 7: {CB87} Carpenter, G. and Bolt, T. Key compression in the B-tree node manager. Wang Institute DB Course project, Feb. 1987
• 8: Shimin Chen , Phillip B. Gibbons , Todd C. Mowry, Improving index performance through prefetching, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.235-246, May 21-24, 2001, Santa Barbara, California, United States
• 9: 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]
• 10: 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
• 11: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 12: 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
• 13: David B. Lomet, Multi-table search for B-tree files, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582101]
• 14: 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]
• 15: 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
• 16: Jun Rao , Kenneth A. Ross, Making B+- trees cache conscious in main memory, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.475-486, May 15-18, 2000, Dallas, Texas, United States
• 17: {STM78} Strong, R., Traiger, I., and Markowsky, G. Slide Search. IBM Report RJ2274 (June 1978).
• 18: {WIGS86} Bernstein, P., Lomet, D., Bakerman, T., MacDonald, W., Malek, S., Mitlak, W., Schweiker, R., Tupper, J., Velardocchia, L. B-Tree Access Method DB-Kit Final Report. Wang Institute Project Course Report, (April. 1986)

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:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Languages