Access Restriction

Author Patel, Jignesh M. ♦ Hankins, Richard A.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Cache-conscious ♦ $b^{+}-tree$ ♦ Index
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.
Description Affiliation: University of Michigan, Ann Arbor, MI (Hankins, Richard A.; Patel, Jignesh M.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2014-01-10
Publisher Place New York
Journal ACM SIGMETRICS Performance Evaluation Review (PERV)
Volume Number 31
Issue Number 1
Page Count 12
Starting Page 283
Ending Page 294

Open content in new tab

   Open content in new tab
Source: ACM Digital Library