论文摘要
随着主存速度和现代处理器的速度之间的差距逐渐扩大,系统对主存的存取访问成为新的瓶颈,Cache行为对主存数据库系统更加重要。高速缓冲存储器存（Cache）是在处理器与主存之间设置的静态随机访问存储器（SDRAM）。高速缓存装载系统运行时需要经常使用的数据,以减少处理器访问内存的次数,从而减少CPU等待时间。鉴于主存数据库本身的结构特点,Cache行为对主存数据库索引结构的设计显得更加重要。本文深入研究了高速缓存工作原理与Cache敏感（Cache-Conscious）技术,对现有的主存数据库索引结构进行了比较与分析。在CST-树的基础上提出一种改进的Cache敏感-T树—MCST-树（Improved Cache sensitive-Tree）索引结构。MCST-树的结构设计特点如下:（1）保留高频访问数据:构建了一个包含CST-树结点中最大关键字的折半查找树,使用这个折半查找树作为一个目录结构确定实际包含所要查找的关键字所在的结点。因为每次查找都会首先访问折半查找树,所以折半查找树中的内容被访问的频率很高。（2）指针的抽取:首先,将折半查找树保存在一个数组（结点组）中,不再保留指向父亲结点与孩子结点的指针。其次,结点组的孩子结点组连续存储,每个结点组仅保留一个指向其第一个孩子结点组的指针。（3）结点大小设计为Cache块大小:将存放折半查找树的数组设计为一个Cache块大小。结点组设计为一个Cache块大小时,在结点组内的访问不会发生Cache缺失。同时,本文还对应用预取技术时改进的Cache敏感型T-树结点组大小的设计进行分析,并且简单描述了应用预取技术时对改进的Cache敏感型T-树基本操作算法的关键部分的修改。实验结果表明,MCST-树索引结构在查找操作性能优势明显,同时MCST-树索引结构的空间代价最小。综合考虑空间代价与时间代价两个方面的因素,MCST-树的整体性能优于CSB+-树最好的一种变形——FULL CSB+-树。