Multi-table search for B-tree files

Abstract

A new method of organizing index entries in nodes of a B-tree is presented. The method is designed specifically to work with variable length keys. Thus it is particularly suited to take advantage of the variable length entries that result when key compression techniques are used. The paper analyses the characteristics of compressed keys. Based on this analysis, it is shown that the method results in significant space savings, leading to reduced disk accesses during random searches of a B-tree organized file. The search algorithms are shown to be competitive with the best of previous methods for treating variable length entries.