pT-树:高速缓存优化的主存数据库索引结构

Prefetching T-Tree:A Cache-optimized Main Memory Database Index Structure

随着主存速度和现代处理器速度之间的差距逐渐扩大,系统对主存的存取访问成为新的瓶颈,Cache行为对主存数据库系统更加重要。索引技术是主存数据库系统设计的关键部分。在CST-树的基础上应用预取技术提高查找操作的性能,提出了一种Cache优化的索引结构预取T-树(pT-tree)。pT-树使用预取技术有效地创建比正常数据传输单元更大的索引结点,从而降低了CST-树的高度,减少了从父亲结点遍历至孩子结点时的Cache缺失。实验结果表明,pT树与B+-树、T-树、CST-树、CSB+-树相比查找性能有所提高。

As the speed gap between main memory and modern processors continues to widen, memory access has become the main bottleneck of processing, so the cache behavior becomes more important for main memory database systems （MMDBs）. Indexing technique is a key component of MMDBs. We proposed a cache-optimized index--Prefetching T-tree （pT-tree） based on a novel CST-tree index, which applies prefetching to CST-tree to accelerate search opera- tions, pT-tree uses prefetching to effectively create wider nodes which are larger than the natural data transfer size. These wider nodes reduce the height of the CST-Tree, thereby decreasing the number of expensive misses when going from parent to child. The experimental performance study shows that our pT-Trees can provide better search perfor- mance than B＋-Trees,T-Trees,CST-Trees and Cache Sensitive B＋-Trees.