Using individual prefixes in B+-trees

In 1985 the authors developed an original tree structure, based on B+-trees , in which each key keeps track of the prefix it shares with its immediate preceding key using only one byte. This is considered to be a substantial s pace and search-time saving approach. These kind of trees have been success fully implemented and have been used in applications such as information re trieval, general data bases, information systems, library administration sy stems and statistical analysis. This paper presents the structure of these trees, explains how the prefix is used to save space and time and gives a c omparative performance study with respect to similar trees and approaches. (C) 1999 Elsevier Science Inc. All rights reserved.