Making B+- trees cache conscious in main memory

ABSTRACT

Previous research has shown that cache behavior is important for main memory index structures. Cache conscious index structures such as Cache Sensitive Search Trees (CSS-Trees) perform lookups much faster than binary search and T-Trees. However, CSS-Trees are designed for decision support workloads with relatively static data. Although B⁺-Trees are more cache conscious than binary search and T-Trees, their utilization of a cache line is low since half of the space is used to store child pointers. Nevertheless, for applications that require incremental updates, traditional B⁺-Trees perform well.

Our goal is to make B⁺-Trees as cache conscious as CSS-Trees without increasing their update cost too much. We propose a new indexing technique called “Cache Sensitive B⁺-Trees” (CSB⁺-Trees). It is a variant of B⁺-Trees that stores all the child nodes of any given node contiguously, and keeps only the address of the first child in each node. The rest of the children can be found by adding an offset to that address. Since only one child pointer is stored explicitly, the utilization of a cache line is high. CSB⁺-Trees support incremental updates in a way similar to B⁺-Trees.

We also introduce two variants of CSB⁺-Trees. Segmented CSB⁺-Trees divide the child nodes into segments. Nodes within the same segment are stored contiguously and only pointers to the beginning of each segment are stored explicitly in each node. Segmented CSB⁺-Trees can reduce the copying cost when there is a split since only one segment needs to be moved. Full CSB⁺-Trees preallocate space for the full node group and thus reduce the split cost. Our performance studies show that CSB⁺-Trees are useful for a wide range of applications.

REFERENCES

• ADW99: 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
• BBC+98: Phil Bernstein , Michael Brodie , Stefano Ceri , David DeWitt , Mike Franklin , Hector Garcia-Molina , Jim Gray , Jerry Held , Joe Hellerstein , H. V. Jagadish , Michael Lesk , Dave Maier , Jeff Naughton , Hamid Pirahesh , Mike Stonebraker , Jeff Ullman, The Asilomar report on database research, ACM SIGMOD Record, v.27 n.4, p.74-80, Dec. 1998 [doi>10.1145/306101.306137]
• BMK99: 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
• CLH98: Trishul M. Chilimbi, et al. Improving pointerbased codes through cache-conscious data placement. Technical report 98, University of Wisconsin- Madison, Computer Science Department.
• Com79: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• Enb99: Richard Enbody. Permon performance monitoring tool (available from http://www.cps .msu.edu/#enbody/perfmon.html). 1999.
• Eng98: InfoCharger Engine. Optimization for decision support solutions (available from http:// www.tandem.com/prod_des/ifchegpd/ifchegpd.htm). 1998.
• HP96: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• Inc99: Sun Microsystems Inc. Ultra sparc user's manual (available from http://www.sun.com/ microelectronics/manuals/ultrasparc/802-7220- 02.pdf as of oct. 16, 1999). 1999.
• Ker89: M. L. Kersten, Using logarithmic code-expansion to speedup index access and maintenance, 3rd International Conference, FODO 1989 on Foundations of Data Organization and Algorithms, p.228-232, July 1989, Paris, France
• LC86: Tobin J. Lehman , Michael J. Carey, A Study of Index Structures for Main Memory Database Management Systems, Proceedings of the 12th International Conference on Very Large Data Bases, p.294-303, August 25-28, 1986
• O'N92: 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]
• Pro99: GNU Project. Gun c compiler manual (available from http://www.gnu.org/software/gcc/ onlinedocs/gcc_toc.html as of oct. 16, 1999). 1999.
• Ram97: Raghu Ramakrishnan, Database management systems, McGraw-Hill, Inc., New York, NY, 1997
• RR99: Jun Rao , Kenneth A. Ross, Cache Conscious Indexing for Decision-Support in Main Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.78-89, September 07-10, 1999
• SKN94: Ambuj Shatdal , Chander Kant , Jeffrey F. Naughton, Cache Conscious Algorithms for Relational Query Processing, Proceedings of the 20th International Conference on Very Large Data Bases, p.510-521, September 12-15, 1994
• Smi82: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• TMJ98: Kristian Torp , Leo Mark , Christian S. Jensen, Efficient Differential Timeslice Computation, IEEE Transactions on Knowledge and Data Engineering, v.10 n.4, p.599-611, July 1998 [doi>10.1109/69.706059 ]
• Wri85: William Wright. Some average performance measures for the B-tree. Acta Inforrnatica, 21:541- 557, 1985.
• Yao78: Andrew Yao. On random 2-3 trees. Acta Inforrnatica, 9:159-170, 1978.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Experimentation, Management, Performance