Height-balanced multiway trees

摘要

A typical class of structures to organize ordered files is multiway trees, among which the most widely used is the perfectly balanced B-tree. In this paper we present the new family of BMT multiway trees, which are kept balanced in height, similarly to the classical binary height balanced trees used in central memory. The height of a BMT, that is the maximum search length for a key, is shown to be a logarithmic function of the number of keys in the worst case. Updating a BMT by key insertion is studied, and a technique to keep the tree balanced is presented. A comparison between the performance of BMTs and B-trees leads to the conclusion that the two structures are roughly comparable as to search length for a key, while BMTs require less memory space than B-trees for small node sizes. The real difference between BMTs and B-tree is in rebalancing operation, which requires a work proportional to the node size in the BMTs and to the tree height in the B-tree.