Multi-table search for B-tree files

ABSTRACT

A 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 compression techniques are used. The paper analyses the characteristics of compressed keys. Based on this analysis, it is shown that the method results in significant space savings, leading to reduced disk accesses during random searches of a B-tree organized file. The search algorithms are shown to be competitive with the best of previous methods for treating variable length entries.

REFERENCES

• 1: Bayer,R. and McCreight,E.M. Organization and maintenance of large ordered indices. Acta Informatica 1,3(1972), 173--189.
• 2: Rudolf Bayer , Karl Unterauer, Prefix B-trees, ACM Transactions on Database Systems (TODS), v.2 n.1, p.11-26, March 1977 [doi>10.1145/320521.320530]
• 3: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 4: Maruyama,K. and Smith,S.E. Analysis of design alternatives for virtual memory indexes. IBM Research Report RC5087(Oct. 1974) Yorktown Hgts., N.Y.
• 5: Maruyama,K. Index structure for virtual memory-comparison between B-trees and M-trees. IBM Research Report RC5258(Feb. 1975) Yorktown Hgts., N.Y.
• 6: OS/VS Virtual Storage Access Method(VSAM) Programmers' Guide. IBM Publication GC26-3838.
• 7: Strong,H.R., Markowsky,G., and Chandra,A.K. Search within a page. IBM Research Report RJ2080 (Sept. 1977) San Jose, Cal.
• 8: Strong,H.R., Traiger,I.L., and Markowsky,G. Slide search. IBM REsearch Report RJ2274 (June, 1978) San Jose, Cal.
• 9: Wagner, R.E. Index design considerations. IBM Syst. J. 12,4 (1973), 351--367.

INDEX TERMS

Keywords:
B-trees, key compression, searching, variable length