Improving the Storage Utilization of 0-Complete Trees

A compact 0-complete tree is an indexing mechanism that can be effectively used for large databases with long and variable-size keys. Compared to B-trees, compact 0-complete trees eliminate search values from secondary indices altogether. They are replaced with small-sized surrogates whose typical eight-bit length will be adequate for most practical key lengths. Hence the secondary indices are simply hierarchical collections of (surrogate, pointer)-pairs. This organization reduces the size of the secondary index structure and increases the branching factor of the trees, thus providing a reduction in external accesses per exact-match query. However, the overall storage performance of a compact 0-complete tree structure suffers from its dependency on the distribution of keys. Non-uniformly distributed data may seriously degrade the storage utilization since no insurance against block-underfilling is provided in the structure, and the number of empty entries at the leaf-level depends on the key distribution. We present: (1) a structural modification of 0-complete trees and identify viable page-splitting algorithmics that improve their storage utilization by reducing page-underfilling, which is achieved by introducing the notion of a sequence set that is analogous to that of \(\hbox {B}^{+}\) ${\text{B}}^{+}$ -trees, and (2) complete algorithmic details and implementations of the modified retrieval and maintenance algorithms for searching, insertion, and deletion.