A high performance, universal, key associative access method

ABSTRACT

A new file organization is proposed that combines the advantages of digital B-trees and extendible hashing methods into one organization that can be used universally. The method, like these predecessors, relies on digital searching. The key notions are: (i) that multipage nodes are addressed by the root and can have both data and index entries, the mix of entries changing over time; and (ii) that these nodes can be doubled with file growth and, when this occurs, data nodes at the next level of the tree are absorbed into the pages of these nodes, frequently keeping data closer to the root and simultaneously improving utilization. The result is an unbalanced tree that we call a digital lopsided tree or DL-tree. The paper describes DL-trees and their operations, and examines their properties. The most important engineering issues involve the doubling process and the methods used to optimize the tree properties. Ways of dealing with these issues are suggested.

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: Diehr, G. Extendible hashing extended. Unpublished manuscript, Graduate School of Business Administration, U. of Washington, Seattle, WA.
• 4: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• 5: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 6: Larson, P. Dynamic hashing. BIT 18 (1978), 184--201.
• 7: Litwin, W. Linear virtual hashing: a new tool for files and tables implementation. Proc. 6th Int'l Conf. on Very Large Data Bases, Montreal, 1980.
• 8: Lomet, D. Digital B-trees. Proc. 7th Conf. on Very Large Data Bases, Cannes, France, 1981, 333--343.
• 9: David B. Lomet, Bounded index exponential hashing, ACM Transactions on Database Systems (TODS), v.8 n.1, p.136-165, March 1983 [doi>10.1145/319830.319837]
• 10: Lomet, D. A high performance, universal, key associative access method. IBM Research Report RC9638, Yorktown Heights, New York (Oct. 1982)
• 11: G. N.N. Martin, Spiral Storage: Incrementally Augmentable Hash Addressed Storage, University of Warwick, Coventry, UK, 1979