Rudolf Bayer
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.
- 1 AUER, 1~. Schlfisselkompressionen in B*-b~iumen. Diplomarbeit, Tech. U. Miinchen, Mtinchen, Germany, 1976.Google Scholar
- 2 BAYER, R. Symmetric binary B-trees: Data structure and maintenance algorithms. Acta lnformatica 1 (1972), 290-306.Google Scholar
- 3 BArER, R. Storage characteristics and methods for searching and addressing. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 440-444.Google Scholar
- 4 BAYER, l~., AND McCREIGHT, E. Organization and maintenance of large ordered indexes. Acta Informatica 1, 3 (1972), 173-189.Google ScholarDigital Library
- 5 BAYER, R., AND METZGER, J.K. On the encipherment of search tress and random access files. A CM Trans. Database Syst. i, 1 (March 1976), 37-52. Google ScholarDigital Library
- 6 BXYER, R., AND SCHKOLNICK, M. Concurrency of operations on B-trees. IBM Res. Rep. RJ 1791, IBM Res. Lab., San Jose, CMif., May 1976.Google Scholar
- 7 BXYER, R., AND UNTERXU~R, K. Prefix B-trees. IBM Res. Rep. RJ 1796, IBM Res. Lab., San Jose, Calif.~ June 1976.Google Scholar
- 8 KNUTH, D.E. The Art of Computer Programming, Vol. 8: Sorting and Searching. Addison- Wesley, Reading, Mass., 1972. Google ScholarDigital Library
- 9 WA~N~R, R.E. Indexing design considerations. IBM Syst. J. ~ (1973), 351-367.Google Scholar
- 10 WEDEKIND, H. On the selection of access paths in a data base system. In Data Base Management, J.W. Klimbie and K.L. Koffeman, Eds., North-Holland Pub. Co., Amsterdam, 1974, pp. 385-397.Google Scholar
Index Terms
- Prefix B-trees
Recommendations
Multi-table search for B-tree files
SIGMOD '79: Proceedings of the 1979 ACM SIGMOD international conference on Management of dataA 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 ...
Main-memory index structures with fixed-size partial keys
SIGMOD '01: Proceedings of the 2001 ACM SIGMOD international conference on Management of dataThe performance of main-memory index structures is increasingly determined by the number of CPU cache misses incurred when traversing the index. When keys are stored indirectly, as is standard in main-memory databases, the cost of key retrieval in terms ...
Main-memory index structures with fixed-size partial keys
The performance of main-memory index structures is increasingly determined by the number of CPU cache misses incurred when traversing the index. When keys are stored indirectly, as is standard in main-memory databases, the cost of key retrieval in terms ...
Comments