Adaptive indexing for relational keys

Graefe, Goetz ; Kuno, Harumi

HP Development Company

关键词: databases;    indexes;    storage systems;    B-trees;    adaptive merging;    database cracking;   

RP-ID  :  HPL-2010-23

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

Adaptive indexing schemes such as database cracking and adaptive merging have been investigated to-date only in the context of range queries. These are typical for non-key columns in relational databases. For complete self-managing indexing, adaptive indexing must also apply to key columns. The present paper proposes a design and offers a first performance evaluation in the context of keys. Adaptive merging for keys also enables further improvements in B-tree indexes. First, partitions can be matched to levels in the memory hierarchy such as a CPU cache and an in- memory buffer pool. Second, adaptive merging in merged B-trees enables automatic master-detail clustering.