The performance of main-memory index structures is increasingly determined by the number of CPU cache misses incurred when traversing the index. When keys are stored indirectly, as is standard in main-memory databases, the cost of key retrieval in terms of cache misses can dominate the cost of an index traversal. Yet it is inefficient in both time and space to store even moderate sized keys directly in index nodes. In this paper, we investigate the performance of tree structures suitable for OLTP workloads in the face of expensive cache misses and non-trivial key sizes. We propose two index structures, pkT-trees and pkB-trees, which significantly reduce cache misses by storing partial-key information in the index. We show that a small, fixed amount of key information allows most cache misses to be avoided, allowing for a simple node structure and efficient implementation. Finally, we study the performance and cache behavior of partial-key trees by comparing them with other main-memory tree structures for a wide variety of key sizes and key value distributions.
主内存索引结构的性能越来越多地由遍历索引时发生的CPU高速缓存未命中数决定。当键是间接存储的时(如在主内存数据库中一样),就高速缓存未命中而言,键检索的成本可以支配索引遍历的成本。但是,直接在索引节点中存储大小适中的键在时间和空间上都是效率低下的。在本文中,面对昂贵的高速缓存未命中和非平凡的密钥大小,我们研究了适合OLTP工作负载的树形结构的性能。我们提出了两种索引结构,即pkT树和pkB树,它们通过在索引中存储部分密钥信息 I>来显着减少缓存丢失。我们表明,少量,固定数量的密钥信息可以避免大多数高速缓存未命中的情况,从而实现简单的节点结构和高效的实现。最后,通过将部分键树与其他主内存树结构进行比较,研究了部分键树的性能和缓存行为,以了解各种键大小和键值分布。 P>
机译:朝向多功能主存储器存储结构:在完全有序数据集中利用子空间距离等于精确的KNN查询
机译:用于查询主内存数据结构的交互式SQL关系接口
机译:使用局部观测,局部模型和局部残差来改善晶体结构的最小二乘法
机译:具有固定尺寸的部分键的主内存索引结构
机译:泊松同构和泊松结构(X(2)+ Y(2))(S)部分D(X)楔形部分D(Y)的二次不变量。
机译:设计和制造定制部分臀部采用CT扫描数据和晶格多孔结构的假肢
机译:当协方差矩阵具有结构时,两个多机动意味着的固定尺寸置信区