改进型缓存敏感B+树的研究  

Study of Improved Cache Sensitive B+-Tree

作　　者：王晨[1] 陈刚[1] 董金祥[1] 

机构地区：[1]浙江大学计算机科学与技术学院,浙江杭州310027

出　　处：《计算机测量与控制》2006年第11期1531-1534,1550,共5页Computer Measurement &Control

摘　　要：在内存数据库中,处理器缓存的失配次数对系统的性能有重要的影响;缓存敏感的索引能减少在做查询操作时产生的缓存失配次数,从而提高系统的性能;传统的设计思路将结点大小等于缓存块大小,认为这样就能使得缓存失配次数减少;但是这样的设计忽略了TLB失配对系统性能的影响;我们提出了一种缓存敏感索引??改进型缓存敏感B+树(简称MCSB+树),它同时兼顾了缓存失配和TLB失配对系统性能的影响,比传统的缓存敏感索引能提供更好的操作性能。In main-memory databases, the number of processor cache misses has a critical impact on the performance of the system. Cache conscious indices can reduce the number of processor cache miss that are incurred during the search operation, and improve the performance. 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. But this design choice ignores the effect of TLB misses. We propose a cache sensitive index called ＂ Improved Cache Sensitive B＋- Tree＂ （MCSB＋-Tree）. It gives attention to the effects of cache misses and TLB misses, and can gain better performance than conventional cache conscious indices.

关 键 词：索引 缓存敏感 CSB+树 MCSB+-树 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]