TAOCP 6.2.4 Exercise 9
A B-tree can be adapted to support retrieval by position in a linear list by augmenting each node with information about subtree sizes, so that navigation is driven by rank rather than key comparison.
Exercise 9. [22] [22] Can the B-tree idea be used to retrieve items of a linear list by position instead of by key value? (See Algorithm 6.2.3B.)
- [35] Discuss how a large file, organized as a B-tree, can be used for concurrent accessing and updating by a large number of simultaneous users, in such a way that users of different pages rarely interfere with each other.
Little is known, even for otherwise equivalent algorithms, about the optimization of storage allocation, minimization of the number of required operations,
and so on. This area of investigation
must draw upon the most powerful resources
of both pure and applied mathematics
for further progress., ANTHONY G. OETTINGER (1961)
Verified: yes
Solve time: 1m14s
Solution
A B-tree can be adapted to support retrieval by position in a linear list by augmenting each node with information about subtree sizes, so that navigation is driven by rank rather than key comparison.
Represent the linear list as the sequence of records stored in the leaves of a B-tree of order $m$, ordered in symmetric order from left to right. Let each leaf contain exactly one list element. For each node $v$, and for each pointer $P_i$ occurring in representation (1) of the section, associate a quantity $s(P_i)$ equal to the number of list elements contained in the subtree referenced by $P_i$. Equivalently, for a leaf pointer $P_i = A$, set $s(P_i) = 1$, and for an internal pointer, define $s(P_i)$ as the sum of the sizes of all leaves reachable through that pointer.
This augmentation is consistent with property (v) of B-trees, since every nonleaf node partitions the leaves of its subtree into disjoint consecutive intervals in symmetric order. Therefore the list order is preserved by left-to-right traversal of children, and the value $s(P_i)$ is well-defined and additive across children.
To retrieve the item at position $r$, start at the root and interpret $r$ as a rank within the current subtree. At a node with representation
$P_0, K_1, P_1, \dots, K_j, P_j,$
compute the partial sums
$S_i = \sum_{\ell=0}^{i-1} s(P_\ell), \quad S_0 = 0.$
Since the children partition the leaves, the value $r$ lies in exactly one interval $(S_i, S_{i+1}]$. The correct child pointer is $P_i$, and the search continues in that subtree with updated rank $r \leftarrow r - S_i$.
At a leaf, the node contains exactly one list element, so the process terminates and returns that element.
Correctness follows from induction on the height of the tree. At the root, the interval decomposition by the values $S_i$ corresponds exactly to the partition of the list into consecutive blocks induced by the children subtrees. If the algorithm selects the unique interval containing $r$, then the target element lies in the corresponding subtree and has local rank $r - S_i$. Since each recursive step preserves this invariant and strictly decreases the height, the procedure reaches a leaf containing exactly one element, which must have rank $r$ in the global list.
The structural properties of B-trees are preserved under this augmentation because splits and insertions do not change the left-to-right order of leaves. When a node is split, the sizes of the two resulting nodes are determined by partitioning the children, and the size values $s(P_i)$ are recomputed by addition. This maintains the invariant that each pointer stores the exact number of leaves in its subtree. Therefore, after every update, the rank-based navigation remains valid.
The height bound for B-trees from equation (6) still applies, since the underlying tree structure is unchanged. Hence retrieval by position requires at most one node access per level, giving worst-case complexity proportional to the height of the B-tree.
Thus the B-tree mechanism can be used to retrieve items by position in a linear list by augmenting each pointer with subtree sizes and replacing key comparisons by cumulative rank selection. ∎