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.
- ADW99.Anastassia Ailamaki, et al. DBMSs on a modern processor: Where does time go. In Proceedings of the 25th VLDB Conference, 1999. Google ScholarDigital Library
- BBC+98.Phil Bernstein, et al. The Asilomar report on database research. Sigmod Record, 27(4), 1998. Google ScholarDigital Library
- BMK99.Peter A. Boncz, et al. Database architecture optimized for the new bottleneck: Memory access. In Proceedings of the 25th VLDB Conference, 1999. Google ScholarDigital Library
- CLH98.Trishul M. Chilimbi, et al. Improving pointerbased codes through cache-conscious data placement. Technical report 98, University of Wisconsin- Madison, Computer Science Department.Google Scholar
- Com79.D. Comer. The ubiquitous B-tree. A CM Computing Surverys, 11(2), 1979. Google ScholarDigital Library
- Enb99.Richard Enbody. Permon performance monitoring tool (available from http://www.cps .msu.edu/#enbody/perfmon.html). 1999.Google Scholar
- Eng98.InfoCharger Engine. Optimization for decision support solutions (available from http:// www.tandem.com/prod_des/ifchegpd/ifchegpd.htm). 1998.Google Scholar
- HP96.J. L. Hennessy and D. A. Patterson. Computer Architecture: a quantitative approach. Morgan Kaufman, San Francisco, CA, 2 edition, 1996. Google ScholarDigital Library
- 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.Google Scholar
- Ker89.Martin L. Kersten. Using logarithmic codeexpansion to speedup index access and maintenance. In Proceedings of 3rd FODO Conference, pages 228-232, 1989. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- O'N92.Patrick E. O'Neil. The SB-tree: An indexsequential structure for high-performance sequentim access. Acta Inforrnatica, 29(3):241-265, 1992. Google ScholarDigital Library
- 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.Google Scholar
- Ram97.Raghu Ramakrishnan. Database Management Systems. McGraw-Hill, 1997. Google ScholarDigital Library
- RR99.Jun Rao and Kenneth A. Ross. Cache conscious indexing for decision-support in main memory. In Proceedings of the 25th VLDB Conference, 1999. Google ScholarDigital Library
- SKN94.Ambuj Shatdal, et al. Cache conscious algorithms for relational query processing. In Proceedings of the 20th VLDB Conference, 1994. Google ScholarDigital Library
- Smi82.Alan J. Smith. Cache memories. A CM Computing Surverys, 14(3):473-530, 1982. Google ScholarDigital Library
- TMJ98.Kristian Torp, et al. Efficient differential timeslice computation. IEEE Transactions on knowledge and data engineering, 10(4), 1998. Google ScholarDigital Library
- Wri85.William Wright. Some average performance measures for the B-tree. Acta Inforrnatica, 21:541- 557, 1985.Google ScholarCross Ref
- Yao78.Andrew Yao. On random 2-3 trees. Acta Inforrnatica, 9:159-170, 1978.Google Scholar
Index Terms
- Making B+- trees cache conscious in main memory
Recommendations
Persistent B+-trees in non-volatile main memory
Computer systems in the near future are expected to have <u>N</u>on-<u>V</u>olatile <u>M</u>ain <u>M</u>emory (NVMM), enabled by a new generation of <u>N</u>on-<u>V</u>olatile <u>M</u>emory (NVM) technologies, such as Phase Change Memory (PCM), STT-MRAM,...
Making B+- trees cache conscious in main memory
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-...
Effect of node size on the performance of cache-conscious B+-trees
In main-memory databases, the number of processor cache misses has a critical impact on the performance of the system. Cache-conscious indices are designed to improve performance by reducing the number of processor cache misses that are incurred during ...
Comments