Effect of node size on the performance of cache-conscious B+-trees
Effect of node size on the performance of cache-conscious B+-trees
复制标题
DOI：
10.1145/781027.781063
复制
发表时间：
2003-06
期刊：
影响因子：
--
通讯作者：
R. Hankins;J. Patel
中科院分区：
文献类型：
--
作者：
R. Hankins;J. Patel
在主存数据库中，处理器缓存未命中的次数对系统性能有着至关重要的影响。缓存感知索引旨在通过减少搜索操作期间发生的处理器缓存未命中次数来提高性能。传统观点认为，索引的节点大小应等于缓存行大小，以最小化缓存未命中次数并提高性能。正如我们在本文中所展示的，这种设计选择忽略了其他影响，例如执行的指令数量和TLB未命中次数，这些在决定整体性能方面起着重要作用。为了捕捉节点大小对缓存感知B +树（CSB + -树）性能的影响，我们首先基于搜索过程的基本组件开发了一个分析模型。然后通过实际实现对该模型进行了验证，证明该模型是准确的。分析模型和实验都证实，使用远大于缓存行大小的节点大小可以使CSB + -树获得更好的搜索性能。
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.