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 space and search-time saving approach. These kind of trees have been successfully implemented and have been used in applications such as information retrieval, general data bases, information systems, library administration systems 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 comparative performance study with respect to similar trees and approaches.
individual prefix b+-trees information retrieval page prefix software engineering