Lecture Notes: Weight-Balanced B-tree

In this lecture, we will study a technique called weight-balancing, which is very important in de-signing data structures, as we will see in later lectures. We will introduce the technique on the B-tree, which can be regarded as the EM equivalent of the binary search tree in RAM. 1 B-tree Structure. Let S be a set of N elements in R. A B-tree T on S is parameterized by two integer values: a leaf parameter b ≥ B and a branching parameter p ≥ 16. We assume that both b and p are multiples of 16. Given a node u of T, we denote by sub(u) the subtree of u. All the leaves of T are at the same level, namely, the length of each root-to-leaf path is the same. Each leaf node, if it is not the root, contains between b/4 and b elements in S—referred to as leaf elements. Each element of S is stored in one, and exactly one, leaf. Consider now an internal node v with child nodes u1, u2,..., uf. We refer to the value of f as the fanout of v. If v is not the root, the value of f must satisfy p/4 ≤ f ≤ p; otherwise, it must hold that f ≥ 2. For each ui (1 ≤ i ≤ f), v stores a routing element ei, which equals the smallest leaf element in sub(ui). Without loss of generality, suppose that e1, e2,..., ef are in ascending order. For each i ∈ [1, f − 1], it must hold that all the leaf elements in sub(ui) be smaller than ei+1