The order m is the maximum number of children of a node. A B+tree is a B-tree in which all data entries live in the leaves, which are linked to their neighbours. The keys in internal nodes are only separators: to the left of separator K every key is < K, and to its right every key is ≥ K.
Node
Children
Keys
Here, m = 5
Root (if not a leaf)
2 … m
1 … m − 1
1 … 4 keys
Other internal node
⌈m/2⌉ … m
⌈m/2⌉ − 1 … m − 1
2 … 4 keys
Leaf
—
⌈(m−1)/2⌉ … m − 1 entries
2 … 4 entries
All leaves are on the same level. The algorithms below use only these bounds:
max every node holds at most m − 1 keys (m children)
min leaf a leaf other than the root holds at least ⌈(m−1)/2⌉ entries
min internal an internal node other than the root holds at least ⌈m/2⌉ − 1 keys
With m = 5, as in all the questions: at most 4 keys, at least 2.
Algorithm 1Search(x)
node ← root
while node is internal do
i ← number of separators K in node such that K ≤ x ▷ children are numbered 0 … k
node ← child i of node ▷ left of K: keys < K, right of K: keys ≥ K
return the entry x if it is in node, otherwise not found
Algorithm 2Insert(x)
leaf ← Search(x); insert x into leaf, in sorted order
if leaf has ≤ m − 1 entries then return▷ room left: done
▷ leaf overflow: it holds m entries
split leaf: keep the first ⌊m/2⌋ entries, move the other ⌈m/2⌉ to a new leaf L′, linked after leaf
copy up the first key of L′ into the parent, with a pointer to L′ ▷ the key also stays in L′
node ← parent
while node holds m keys do▷ internal overflow
K ← the ⌈m/2⌉-th key of node
split node: keys before K stay, keys after K (and their children) move to a new node N′
if node is the root then create a new root holding K, with children node and N′ ; return▷ height + 1
push up K into the parent, with a pointer to N′ ▷ K leaves the node
node ← parent
Algorithm 3Delete(x)
leaf ← Search(x); remove x from leaf
if leaf has ≥ ⌈(m−1)/2⌉ entries then return▷ no underflow: internal nodes are NOT modified
▷ leaf underflow
S ← an adjacent sibling of leaf with the same parent (prefer one with spare entries)
if S has > ⌈(m−1)/2⌉ entries then▷ S can lend an entry
redistribute: move one entry from S to leaf, and update the separator between them in the parent
return
merge leaf and S into one leaf; remove their separator and the pointer to the removed leaf from the parent
node ← parent
while node is not the root and node has < ⌈m/2⌉ − 1 keys do▷ internal underflow
S ← an adjacent sibling of node
if S has > ⌈m/2⌉ − 1 keys then
rotate: the separator in the parent moves down into node, and the closest key of S moves up to replace it (with its child pointer); return
merge node + the separator pulled down from the parent + S into one node
node ← parent
if the root has 0 keys then its only child becomes the root ▷ height − 1
⚠ Correction: I was wrong in the lecture
What I said: when a key is deleted from a B+tree, its copies in the internal nodes must be deleted too.
This is wrong for a B+tree. It is true for a B-tree, but not for a B+tree:
In a B-tree, every key appears exactly once, and internal nodes hold data entries. Deleting a key stored in an internal node removes data, so the key must be removed there and replaced, for example by its predecessor.
In a B+tree, the data entries are all in the leaves, and internal keys are only separators. A separator K only promises "keys < K on the left, keys ≥ K on the right". After deleting the entry K from its leaf, this promise is still true, so the separator can stay. Searches remain correct.
Separators change only when the structure of the tree changes: a redistribution updates one, and a merge removes one. A deletion that does not cause an underflow never touches the internal nodes.
Many thanks to the student who pointed this out after class (Ioana is right!).
Q1
Insertions and Deletions in a B+tree
Consider the following B+tree of order m = 5:
Apply the following operations in sequence, and draw the tree after each one.
(a) Insert 18.
(b) Insert 10.
(c) Delete 15. After this deletion, does the key 15 still appear somewhere in the tree? Is that a problem? Search for 15, then for 17.
(d) Delete 51.
(a) Insert 18: the simple case
18 belongs to the leaf [15 21], since 15 ≤ 18 < 30. The leaf has room, so we insert in sorted order and stop. The index does not change.
(b) Insert 10: splits all the way to the root
10 belongs to the leaf [3 6 9 12], which is full. With 10 it would hold [3 6 9 10 12], which is m = 5 entries, one more than the maximum, so it splits into [3 6] and [9 10 12].
The first key of the new leaf, 9, is copied up. It stays in the leaf, because the leaf holds the data entry.
The root becomes [9 15 30 45 60], which is 5 keys, so it overflows and splits: [9 15] and [45 60]. The middle key 30 is pushed up: it does not stay in either half, because internal keys are only signposts.
The root has split, so 30 becomes the only key of a new root. The height grows from 2 to 3.
(c) Delete 15: the simple case, and an erratum
15 is in the leaf [15 18 21]. After removing it, the leaf still holds 2 entries, the minimum, so we stop: nothing else changes, and 15 is still a separator in the internal node [9 15].
This is the correction to the lecture
15 is no longer in the data, but it stays in the internal node [9 15]. In a B+tree this is correct: see the correction box above Q1. In a B-tree, 15 would have had to be removed from the internal node.
Search 15: root [30]: 15 < 30, go left. Node [9 15]: 15 ≥ 15, take the third pointer. Leaf [18 21]: no 15, so the answer is "not found", which is correct. Search 17: the same path and the same leaf: "not found", which is correct too. A separator that no longer matches any data entry never misdirects a search, because it only bounds the keys of each subtree.
(d) Delete 51: merges all the way to the root
51 is in the leaf [45 51], which becomes [45]: 1 entry, fewer than the minimum of 2, an underflow.
Redistribution? Its siblings under the same parent, [30 33] and [60 66], both hold exactly 2 entries, the minimum, so neither can lend one.
Merge with the right sibling: [45] + [60 66] = [45 60 66]. The right leaf disappears, so its pointer and its separator 60 are removed from the parent, which becomes [45].
The parent [45] now has 1 key, fewer than the minimum of 2: it underflows too. Its sibling [9 15] has exactly 2 keys, so it cannot lend one either.
Merge the two internal nodes, pulling the separator 30 down from the root: [9 15] + 30 + [45] = [9 15 30 45], which is 4 keys, the maximum, and fits.
The root has lost its only key, so it is deleted and the merged node becomes the new root. The height shrinks from 3 to 2.
Notice what happened to the separators. 60 was removed although 60 is still in the data, because a node disappeared, not because a key was deleted. 30 moved down, from the root into the merged node. 51 never appeared in the index at all.
Merging with the left sibling instead is also correct: [30 33] + [45] = [30 33 45], the separator 45 is removed, the parent becomes [60], and after the internal merge the root is [9 15 30 60]. Both trees are valid B+trees.
Q2
B+tree and Sorted Inserts
(a) Back to order m = 5. Starting from an empty tree, insert the keys 1, 2, 3, …, 20 in increasing order. Draw the final tree. What fraction of the leaf slots is used? What happens for a very large number of keys inserted in increasing order?
(b) Propose a way to build a tree with full leaves when the keys arrive sorted.
(a) Inserting 1 to 20 in increasing order
Every new key goes into the rightmost leaf. When it overflows, it splits into 2 entries on the left and 3 on the right, and all later keys go to the right. The left half is never touched again. The same happens to the internal nodes.
Result: 9 leaves for 20 keys, with 20 of 36 slots used (56%), and a height of 3. For a large number of keys, every leaf except the last holds exactly 2 of 4 entries, the minimum, so the fill tends to 50%. The tree takes twice the space and has more levels than necessary.
(c) Why sorted inserts are bad, and a fix
With random keys, a leaf that was split keeps receiving inserts, so it fills up again before it splits; on average leaves are about 69% full (ln 2 ≈ 0.69). With sorted keys, only the last leaf ever receives inserts, so each split leaves behind a half-empty node that will never be filled.
Bulk loading: when the data is already sorted, build the tree bottom-up. Fill each leaf to a chosen fill factor (100%, or 90% to leave room for future inserts), then build each index level from the first key of each node below. This takes a single pass with no splits.
Same 20 keys: 5 full leaves and height 2, instead of 9 half-empty leaves and height 3.
Part 2 · Hashing
Recall: extensible hashing (see the slides)
Static hashing uses a fixed number of buckets. When the data grows, overflow chains get longer, and rehashing everything is expensive. Extensible hashing grows one bucket at a time, using a small directory of pointers.
Directory: an array of $2^{gd}$ pointers, where gd is the global depth. A key k goes to the entry given by the last gd bits of its hash h(k).
Buckets: each bucket has a local depthld ≤ gd. All the keys in a bucket share their last ld bits, and exactly $2^{gd-ld}$ directory entries point to it.
Insert k: follow the entry given by the last gd bits of h(k).
If the bucket has room, insert. Done.
If the bucket is full and ld < gd: split the bucket. Its local depth becomes ld + 1, its keys are redistributed using one more bit, and the directory entries that pointed to it are shared between the old and the new bucket. The directory does not change size. Retry the insert.
If the bucket is full and ld = gd: first double the directory. The new entry 1xy… points to the same bucket as the old entry 0xy…, and gd grows by 1. Then split as in case 2 and retry.
In Q3 and Q4: h(k) = k (so you can read the bits directly), and a bucket holds 2 keys.
Q3
Extensible Hashing: Three Insertions
Consider the following extensible hash table (keys are shown in decimal and binary):
(a) Why do two directory entries point to bucket B? Why does B have local depth 1?
Insert the following keys in sequence, and draw the table after each insertion.
(b) Insert 10.
(c) Insert 9.
(d) Insert 12.
(e) In the final table, how many directory entries point to each bucket? Check the formula $2^{gd-ld}$.
(a) Shared buckets
B holds 5 = 101 and 7 = 111: they only share their last bit. So far, one bit was enough to tell B's keys apart from the others, so B has ld = 1, and both entries ending in 1 (01 and 11) point to it: $2^{2-1} = 2$ entries.
(b) Insert 10 = 1010: the simple case
The last 2 bits are 10, which points to bucket C. C has room, so 10 goes in and we stop.
(c) Insert 9 = 1001: a bucket split
The last 2 bits are 01, which points to B, and B is full. ld = 1 < gd = 2, so we split B without touching the directory size:
B and a new bucket B2 both get ld = 2. Keys are separated by their last 2 bits: 5 = 101 stays in B, and 7 = 111 goes to B2.
Entry 01 still points to B, and entry 11 now points to B2.
Retry: 9 = 1001 goes to B, which now has room.
(d) Insert 12 = 1100: the directory doubles
The last 2 bits are 00, which points to A = {4, 8}, and A is full. ld = gd = 2: no directory entry is left to separate A's keys, so the directory must double first.
Double the directory: gd = 3, 8 entries. Each new entry 1xy points to the same bucket as 0xy.
Split A using 3 bits: 8 = 1000 stays in A (ld = 3), and 4 = 100 goes to the new bucket A2 (ld = 3). Entry 100 now points to A2.
Retry: 12 = 1100 goes to A2, which has room.
Only A was split. B, B2 and C are untouched: they keep ld = 2 and are now each pointed to by 2 entries. Doubling the directory only copies pointers; no data moves.
(e) Checking the formula
Bucket
ld
$2^{gd - ld}$ (gd = 3)
Entries pointing to it
A
3
1
000
A2
3
1
100
B
2
2
001, 101
B2
2
2
011, 111
C
2
2
010, 110
Total: 1 + 1 + 2 + 2 + 2 = 8 = $2^3$ entries.
Q4
When Extensible Hashing Goes Wrong
Same rules as in Q3 (h(k) = k, 2 keys per bucket), starting from this small table:
(a) Insert 64, then 128. How many times does the directory double? How many directory entries and buckets do you end up with, for 4 keys?
(b) Now insert 256. What is the global depth after this insertion? How large is the directory, and how many of the buckets are empty?
(c) What happens if three records have the same key, for example if we insert 3 twice more?
(d) What is the root cause of (a) and (b)? How do real systems avoid these problems?
(e) An equality lookup in an extensible hash table costs about one disk read, the bucket, since the directory fits in memory. That is better than a B+tree. Why do databases still use B+trees as their default index?
(a) Insert 64 and 128
64 = 1000000 goes to A, which has room: A = {8, 64}.
128 = 10000000 also goes to A, which is full, with ld = gd = 1. The keys in binary are 8 = 1000, 64 = 1000000 and 128 = 10000000:
gd = 2: all three keys end in 00, so the split leaves an empty bucket for 10, and A is still overfull.
gd = 3: all three end in 000. Another empty bucket for 100.
gd = 4: 8 ends in 1000, while 64 and 128 end in 0000. They finally separate: A = {64, 128}, and 8 goes to a new bucket.
3 doublings for a single insert. The directory has 16 entries and there are 5 buckets, 2 of them empty, for 4 keys. B still has ld = 1, so 8 of the 16 entries point to it.
(b) Insert 256
256 = 100000000 ends in 0000, so it goes to A = {64, 128}, which is full, with ld = gd = 4. 64, 128 and 256 share their last 6 bits (all zeros). They separate only at bit 7, where 64 = 1000000 differs from 128 and 256.
So the directory doubles 3 more times: gd = 7, 128 entries, for 5 keys. There are 8 buckets, and 4 of them are empty (those for 10, 100, 10000 and 100000).
(c) Duplicates
Three entries with the same hash value share all their bits, so no number of bits can separate them. The algorithm doubles the directory forever. Duplicates beyond the bucket capacity cannot be handled by splitting: real implementations cap the depth and use overflow pages for such buckets.
(d) Root cause and fixes
The structure assumes that the low bits of the hash values are uniformly distributed. With h(k) = k, keys that are multiples of a power of two share their low bits: here 8, 64, 128 and 256 all end in at least three zeros. A good hash function mixes all the bits of the key (for example multiplicative hashing, MurmurHash or xxHash), so that its low bits look random whatever the key distribution. Then the directory grows roughly in proportion to the number of buckets actually needed. For duplicates, no hash function helps: overflow pages are required.
(e) Why B+trees remain the default
Hashing only answers equality queries (WHERE id = 42). It destroys order, so it cannot answer range queries (BETWEEN, <), ORDER BY, prefix searches (LIKE 'abc%') or min/max. A B+tree answers all of them, and its leaves can be scanned in order.
A B+tree also costs only about one disk read per lookup in practice (Q2): its internal levels fit in memory, just like the directory.
Its performance does not depend on the quality of a hash function or on the distribution of the keys.
Part 3 · Distributing keys over servers
Q5
From Modulo Hashing to Consistent Hashing
A key-value store holds n keys spread over m servers, numbered 0 to m − 1. A first, naive design stores key k on server
$$\text{server}(k) = h(k) \bmod m$$
where h is a hash function whose values are uniformly distributed.
(a) A server fails. We move its keys to the other servers, but we keep computing the location with $h(k) \bmod m$. Does this work?
(b) Fix: after each failure, recompute the location of every key with $h(k) \bmod (m-1)$, and move every key whose server changes. On average, how many keys move per failure? Hint: for which values of h is $h \bmod m = h \bmod (m-1)$? You can assume the failed server is the last one, m − 1, so the other servers keep their numbers.
(c) Is this system appropriate for a large key-value store?
Consistent hashing. Servers and keys are both placed on a circle $[0, 2\pi)$: server s at position $\theta_s = h(s)$ and key k at position $\theta_k = h(k)$, with h now mapping to $[0, 2\pi)$. Each key is stored on the first server found going clockwise from the key.
(d) In the figure, which server stores each key? Server S2 fails: which keys move, and where? With n keys and m servers, how many keys move on average when one server fails? And when a server is added?
(e) With $h(k) \bmod m$, finding the server of a key costs $O(1)$. How does a client find the server of a key with consistent hashing, and what does that cost?
(f) Each server stores the keys of the arc between its predecessor and itself. Assume the m servers are placed uniformly at random on the circle. Compute the mean and the variance of the fraction of the circle owned by one server. What does this mean for the load of the servers?
(g) Propose a way to reduce this variance, and compute the new variance.
(a) The naive design breaks
No. Every key with $h(k) \bmod m = s$ is still routed to the failed server s, so reads and writes of those keys fail, wherever we moved the data. The lookup rule and the data placement no longer agree. And if we switch the lookup rule to $\bmod (m-1)$ without moving the data, almost every key is looked up on the wrong server (see (b)).
(b) Rehashing everything: how many keys move?
A key stays on the same server if and only if $h \bmod m = h \bmod (m-1)$. The pair $(h \bmod m,\ h \bmod (m-1))$ repeats with a period equal to the least common multiple of m and m − 1. Since m and m − 1 are coprime, that is $m(m-1)$, so it is enough to count inside one period, $0 \le h < m(m-1)$.
For $h = 0, 1, \dots, m-2$, both remainders are equal to h itself: that gives m − 1 common values.
There are no others. If both remainders equal some r, then h − r is a multiple of m and of m − 1, so a multiple of their least common multiple m(m − 1). Since $0 \le h - r < m(m-1)$, this forces h − r = 0 (i.e., the only multiple of $m(m-1)$ that satisfy the inequality).
So m − 1 values out of m(m − 1) keep their server: a probability of $\frac{m-1}{m(m-1)} = \frac{1}{m}$.
Only n/m keys had to move (those of the failed server), but almost all of them move. A small check with m = 4 and h = 0 … 11:
h
0
1
2
3
4
5
6
7
8
9
10
11
h mod 4
0
1
2
3
0
1
2
3
0
1
2
3
h mod 3
0
1
2
0
1
2
0
1
2
0
1
2
Only 3 keys out of 12 stay put: 1/4 = 1/m. The other 3/4 move, while only the 3 keys of server 3 needed to.
(c) Not appropriate
With m = 100 servers, each failure moves 99% of the data across the network instead of 1%. Failures are routine in a large cluster, and so is adding servers, which has the same cost with $\bmod (m+1)$. Every such event triggers a massive data transfer, during which most keys are temporarily unreachable or must be read from two places. It can even cascade: the transfer overloads the remaining servers, which then fail too.
(d) Consistent hashing: only the failed server's keys move
Before the failure: k6 and k7 go to S1 (the arc wraps around 0), k1 and k2 to S2, k3 to S3, and k4 and k5 to S4. When S2 fails, its arc is absorbed by its successor S3: only k1 and k2 move, to S3. All other keys stay where they are.
In general, only the keys of the failed server's arc move, and an arc covers a fraction 1/m of the circle on average:
$$\mathbb{E}[\text{keys moved}] = \frac{n}{m}$$
This is optimal: those keys had to move anyway. Adding a server moves only the keys of the arc it takes over, n/(m + 1) on average, all taken from a single server.
(e) Finding a key's server costs O(log m), not O(1)
The rule "first server clockwise" is a successor search. The client keeps the m server positions sorted, computes $\theta_k = h(k)$, and looks for the first position ≥ θk, wrapping around to the first server if there is none. With a sorted array, this is a binary search: $O(\log m)$. In the figure, the sorted positions are S1 = 0.4, S2 = 1.9, S3 = 2.6, S4 = 4.6, and k4 at 3.3 is found between 2.6 and 4.6, so it goes to S4.
A sorted array gives $O(\log m)$ lookups, but adding or removing a server costs $O(m)$, because elements have to be shifted. A balanced search tree (or a skip list) gives $O(\log m)$ for lookups and for updates.
With virtual nodes (part (g)), the ring has mv positions, so a lookup costs $O(\log(mv))$.
In practice this is cheap: with m = 1,000 servers, a lookup takes about 10 comparisons in memory, which is negligible next to the network round trip that follows. The real cost is elsewhere: every client must keep an up-to-date copy of the ring, so servers joining or leaving must be broadcast.
(f) The load is very unbalanced
the distribution of an arc. Normalise the circle to length 1, and fix one server S. Its arc goes from S backwards (counter-clockwise) to the previous server, and L is its length. Saying L > x means the previous server is more than x away: the stretch of length x just before S contains none of the other m − 1 servers.
One other server lands uniformly on the circle, so it falls in that stretch with probability x, and outside with probability 1 − x.
The m − 1 other servers are placed independently, so the probability that all of them land outside is the product:
$$P(L > x) = \underbrace{(1-x)\times(1-x)\times\dots\times(1-x)}_{m-1 \text{ other servers}} = (1-x)^{m-1}, \qquad 0 \le x \le 1$$
Mean and variance. $P(L > x) = (1-x)^{m-1}$ is exactly the tail of a Beta(1, m − 1) distribution. For a Beta(α, β), the mean is $\frac{\alpha}{\alpha+\beta}$ and the variance is $\frac{\alpha\beta}{(\alpha+\beta)^2(\alpha+\beta+1)}$. With α = 1 and β = m − 1:
The standard deviation, about 1/m, is as large as the mean: the coefficient of variation is close to 1.
(g) Virtual nodes
Place each server at v positions on the circle, its virtual nodes, for example $h(s\|1), \dots, h(s\|v)$. A server's load is now the sum of v arcs, out of mv arcs in total.
Intuition. With mv points on the circle, each arc has mean $\frac{1}{mv}$ and, by part (f), variance about $\frac{1}{(mv)^2}$. A server owns v of these arcs, which are almost independent. Their variances add up: about $v \times \frac{1}{(mv)^2} = \frac{1}{m^2 v}$, while the mean stays $v \times \frac{1}{mv} = \frac{1}{m}$. The exact computation (the sum follows a Beta(v, mv − v) distribution) confirms it:
The variance is divided by about v, so the relative imbalance shrinks like $1/\sqrt{v}$: with v = 100, each server's load is within about ±10% of the mean instead of ±100%.
Better failures: when a server fails, its v arcs go to v different successors, which are spread over the other servers. Its load is shared, instead of doubling the load of a single neighbour.
Heterogeneous servers: give a bigger machine more virtual nodes, in proportion to its capacity.
Cost: the ring now has mv positions. Each client keeps it sorted and finds a key's server by binary search in $O(\log(mv))$, which is negligible.
🔑 Professor Access
Enter the unlock code to reveal model answers after class discussion.