Prefix B -trees

Abstract

Two modifications of B -trees are described, simple prefix B -trees and prefix B -trees. Both store only parts of keys, namely prefixes, in the index part of a B ^* -tree. In simple prefix B -trees those prefixes are selected carefully to minimize their length. In prefix B -trees the prefixes need not be fully stored, but are reconstructed as the tree is searched. Prefix B -trees are designed to combine some of the advantages of B -trees, digital search trees, and key compression techniques while reducing the processing overhead of compression techniques.