Prefix B-Trees
RUDOLF BAYER and KARL UNTERAUER
Technische Universitiit Miinchen
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 pre-
fixes need not he 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 compres-
sion techniques while reducing the processing overhead of compression techniques.
Key Words and Phrases: B-trees, key compression, multiway search trees
CR Categories: 3.73, 3.74
1. SIMPLE PREFIX B-TREES
We assume that the reader is familiar with B-trees [4, 81 and with a variation of
B-trees, called B*-trees [8, lo]. In B*-trees the records of a file together with the
keys identifying them are only stored in leaf nodes of the tree structure. We call
the nonleaves branch nodes or branch pages. Leaves can be linked to their neigh-
bors to allow sequential processing of the leaves without using the branch nodes of
the B*-tree.
We call the part
of a B*-tree consisting only of the branch nodes the B*-index
and the ordered set of leaves the B*-file. In the B*-index some keys, which appear
again in the B*-file with their associated records, are repeated without their records.
The following observation is important for the rest of this paper: The keys stored
in the B*-index are only used to direct the search algorithm and to determine in
which subtree of a given branch node a key and its associated record will be found,
if they are in the tree at all.
It is now a fairly obvious observation that we need not necessarily use the keys
in
the
B*-file
to construct the B*-index. Instead we can use other strings, con-
structed to have desired properties, for building up the equivalent of the B*-index
of a B*-tree.
To give a simple example, we assume that a leaf is already full and contains
keys
Copyright @ 1977, Association for Computing Machinery, Inc. General permission to re-
publish, but not for profit, all or part of this material is granted provided that ACM’s copy-
right notice is given and that reference is made to the publication, to its date of issue, and
to the fact that reprinting privileges were granted by permission of the Association for Corn:
puting Machinery.
Most of the research reported in this paper was performed while the first author was visiting
at IBM&search Laboratory, San Jose, CA 95193. The research of the second author was
sup-
ported by the Sonderforschungsbereich 49-Elektronische Rechenanlagen und Informa-
tionsverarbeitung-of the Deutsche Forschungsgemeinschaft.
Authors’ address: Institut fiir Informatik
der Technischen Universitiit Munchen, Arcisstrasse
21, D-3999 Mtinchen 2, West Germany.
ACM Transactions on Database Systems, Vol. 2, No. 1, March 1977, Pages 11-26.
剩余15页未读，继续阅读
资源评论
