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

1. ADW99.Anastassia Ailamaki, et al. DBMSs on a modern processor: Where does time go. In Proceedings of the 25th VLDB Conference, 1999.
2. BBC+98.Phil Bernstein, et al. The Asilomar report on database research. Sigmod Record, 27(4), 1998.
3. BMK99.Peter A. Boncz, et al. Database architecture optimized for the new bottleneck: Memory access. In Proceedings of the 25th VLDB Conference, 1999.
4. CLH98.Trishul M. Chilimbi, et al. Improving pointerbased codes through cache-conscious data placement. Technical report 98, University of Wisconsin- Madison, Computer Science Department.
5. Com79.D. Comer. The ubiquitous B-tree. A CM Computing Surverys, 11(2), 1979.
6. Enb99.Richard Enbody. Permon performance monitoring tool (available from http://www.cps .msu.edu/#enbody/perfmon.html). 1999.
7. Eng98.InfoCharger Engine. Optimization for decision support solutions (available from http:// www.tandem.com/prod_des/ifchegpd/ifchegpd.htm). 1998.
8. HP96.J. L. Hennessy and D. A. Patterson. Computer Architecture: a quantitative approach. Morgan Kaufman, San Francisco, CA, 2 edition, 1996.
9. 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.
10. Ker89.Martin L. Kersten. Using logarithmic codeexpansion to speedup index access and maintenance. In Proceedings of 3rd FODO Conference, pages 228-232, 1989.
11. LC86.Tobin J. Lehman, et al. A study of index structures for main memory database management systems. In Proceedings of the 12th VLDB Conference, 1986.
12. O'N92.Patrick E. O'Neil. The SB-tree: An indexsequential structure for high-performance sequentim access. Acta Inforrnatica, 29(3):241-265, 1992.
13. 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.
14. Ram97.Raghu Ramakrishnan. Database Management Systems. McGraw-Hill, 1997.
15. RR99.Jun Rao and Kenneth A. Ross. Cache conscious indexing for decision-support in main memory. In Proceedings of the 25th VLDB Conference, 1999.
16. SKN94.Ambuj Shatdal, et al. Cache conscious algorithms for relational query processing. In Proceedings of the 20th VLDB Conference, 1994.
17. Smi82.Alan J. Smith. Cache memories. A CM Computing Surverys, 14(3):473-530, 1982.
18. TMJ98.Kristian Torp, et al. Efficient differential timeslice computation. IEEE Transactions on knowledge and data engineering, 10(4), 1998.
19. Wri85.William Wright. Some average performance measures for the B-tree. Acta Inforrnatica, 21:541- 557, 1985.
20. Yao78.Andrew Yao. On random 2-3 trees. Acta Inforrnatica, 9:159-170, 1978.

Index Terms

• Information systems

  • Information retrieval

    • Document representation