Technical Reports


Click here for full text: PDF

Adaptive indexing for relational keys

Graefe, Goetz; Kuno, Harumi
HP Laboratories


Keyword(s): databases, indexes, storage systems, B-trees, adaptive merging, database cracking

Abstract: 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.

6 Pages

Additional Publication Information: To be published and presented at SMDB 2010, Long Beach, CA, March 1, 2010

External Posting Date: February 6, 2010 [Fulltext]. Approved for External Publication
Internal Posting Date: February 6, 2010 [Fulltext]

Back to Index