Main-memory index structures with fixed-size partial keys

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 c ost of key retrieval in terms of cache misses can dominate the cost of an i ndex 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 s tructures, pkT-trees and pkB-trees, which significantly reduce cache misses by storing partial-key information in the index. We show that a small, fix ed amount of key information allows most cache misses to be avoided, allowi ng for a simple node structure and efficient implementation. Finally, we st udy the performance and cache behavior of partial-key trees by comparing th em with other main-memory tree structures for a wide variety of key sizes a nd key value distributions.