Abstract: Existing main-memory index structures use pointer elimination and prefetching mechanism to improve the cache consciousness of index structure and reduce the number of cache invalidation, but do not make efficient use of main-memory space and CPU performance. To make index structure utilize memory and CPU much better, this paper proposes DCST-tree. DCST-tree implements data compression to use memory and cache space more effectively. This can reduce the number of swap between memory and cache, and improve the rate of cache hit eventually. Meanwhile, node is partitioned into buckets to increase node size and improve the fan-out degree of node, such that the height of index tree can be reduced. The experimental results show that the proposed index structure has higher cache consciousness and space utilization, compared with existing index structures.

Key words: compression, main-memory index, cache consciousness

摘要： 已有主存索引通过指针消除和预取机制提升索引结构的缓存感知能力，减少缓存失效次数，但是并没有有效地利用现代计算机的CPU性能和内存空间。为了进一步提升索引结构对内存空间以及CPU性能的利用率，提出了DCST-树索引结构。该索引结构采用数据压缩的方式，对结点中的关键字进行压缩，提高索引结构对内存空间和缓存空间的利用率，减少内存访问次数，提高缓存命中率。同时，对结点进行分区，增加结点容量，提高结点扇出度，降低树的高度。实验结果表明，所提方案比现有主存索引机制具有更加高效的空间利用率和缓存感知能力，同时具有更加优秀的查询处理能力。

关键词: 压缩, 主存索引, 缓存敏感