file.pdf (75.3 kB)

On B-tree Indices for Skewed Distributions

Download (75.3 kB)
journal contribution
posted on 01.06.2004, 00:00 by Christos Faloutsos, H. V Jagadish
It 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).

History

Date

01/06/2004

Exports

Exports