file.pdf (75.3 kB)
On B-tree Indices for Skewed Distributions
journal contribution
posted on 2004-06-01, 00:00 authored by Christos Faloutsos, H. V JagadishIt is often the case that the set of values over which
a B-Tree is constructed has a skewed distribution.
We present a geometric growth technique to
manage postings records in such cases, and show
that the performance of such a technique is better
than that of a straightforward fixed length postings
list: It guarantees 1 disk access on searching, and it
takes a fraction of the space that its competitor
requires (55% to 66%, in our experiments).