Effect of node size on the performance of cache-conscious B + -trees
- 10 June 2003
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 31 (1), 283-294
- https://doi.org/10.1145/885651.781063
Abstract
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 a search operation. Conventional wisdom suggests that the index's node size should be equal to the cache line size in order to minimize the number of cache misses and improve performance. As we show in this paper, this design choice ignores additional effects, such as the number of instructions executed and the number of TLB misses, which play a significant role in determining the overall performance. To capture the impact of node size on the performance of a cache-conscious B+ tree (CSB+-tree), we first develop an analytical model based on the fundamental components of the search process. This model is then validated with an actual implementation, demonstrating that the model is accurate. Both the analytical model and experiments confirm that using node sizes much larger than the cache line size can result in better search performance for the CSB+-tree.Keywords
This publication has 17 references indexed in Scilit:
- A Portable Programming Interface for Performance Evaluation on Modern ProcessorsThe International Journal of High Performance Computing Applications, 2000
- The Asilomar report on database researchACM SIGMOD Record, 1998
- B-tree page size when caching is consideredACM SIGMOD Record, 1998
- The five-minute rule ten years later, and other computer storage rules of thumbACM SIGMOD Record, 1997
- Comparison of hardware and software cache coherence schemesACM SIGARCH Computer Architecture News, 1991
- Performance analysis of hierarchical cache-consistent multiprocessorsPerformance Evaluation, 1989
- Performance analysis of multiprocessor cache consistency protocols using generalized timed Petri netsACM SIGMETRICS Performance Evaluation Review, 1986
- On random 2?3 treesActa Informatica, 1978
- Approximating block accesses in database organizationsCommunications of the ACM, 1977
- Analysis and performance of inverted data base structuresCommunications of the ACM, 1975