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.