论文部分内容阅读
近年来,随着计算机芯片技术的不断改进,中央处理器(CPU)的速度和主存速度之间的差距逐渐扩大,系统对主存的存取访问成为新的瓶颈。Cache是一种容量非常小、但速度非常快的静态RAM存储器,设置在CPU和主存之间。由于Cache中保存着主存中最常使用的数据和指令,因此可以有效地减少CPU的等待时间。Cache命中率越高,CPU的运算效率就越高。Cache命中率对数据库系统索引结构的性能影响非常大,尤其是对主存数据库索引结构的性能,更是至关重要。鉴于此,在主存数据库系统处理过程中,如何提高Cache的命中率,即减少CPU与主存之间的数据交换次数,提高CPU的运算效率,进而对实时应用提供有效支持,成为一项至关重要的内容。 本文对Cache敏感(“Cache-Conscious”)技术进行了深入研究,分析了现有的主存数据库索引结构,并根据“Cache-Conscious”结构定义方法,在T-树的基础上提出了一种适合于主存数据库的Cache敏感T-树(Cache Sensitive T-Tree)索引结构,可以有效地支持实时应用。由于T-树的结点大小通常大于Cache块的大小,因此不能一次被Cache全部命中。CST-树是把原来T-树结点中的内容根据访问频率高低划分为“高频”部分和“低频”部分,在结点中只保留“高频”部分,而将“低频”部分单独保存,这样可以使结点的大小总是小于Cache块的大小,使一个结点一次就可以被Cache完全命中,从而可以获得比T-树更高的Cache命中率,并且不需要使用额外的空间。实验结果表明,在大多数情况下,CST-树的整体性能与原来的T树相比有明显提高。和另一种高效的Cache敏感型主存数据库索引结构CSB~+-树相比,CST-树与其最好的一种变形FULL CSB~+-树性能接近,而使用空间远远小于FULL CSB~+-树。