The problem of creating B-tree-like dictionaries with small atomic keys from a system containing large, variable-size records is the subject of this paper. These kinds of dictionaries provide guaranteed performance, enhancing the search procedures over external memory. Smaller keys at the top of the searching tree have a larger branching factor and thus require fewer searching accesses; furthermore, avoiding hierarchical arrangements supports the cache-oblivious mode of operations.

In the authors’ opinion, most B-tree papers assume that all used keys have the same size. But, in the worst case, B-tree performance can suffer because of a small number of large records. This paper presents static and dynamic atomic-key dictionaries. Both cases involve substantial organizational overhead. There are situations where a prefix compression alternative saves more space than the suggested method. Therefore, the authors believe that both techniques are likely to be needed.

Formerly, the underlying B-tree idea of dynamic file construction--growth by splitting--was applied to a multiway tree following the preorder traversal of its nodes. Thus, we obtained a B-tree searching structure of standard length records. In Knuth’s monograph [1], this idea is considered in relation to non-uniform tries.

The objective of this work is to adapt the general B-tree file searching technique to overcome certain complicated circumstances. Advanced software developers are the intended audience.