Data Acquisition, Extraction & Storage — ENS / Inria / PSL

Indexing Recap Q&A — B+trees & Hashing

🔒 Answers locked
Part 1 · B+trees
Recall: B+tree of order m (Knuth's definition)

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.

NodeChildrenKeysHere, m = 5
Root (if not a leaf)2 … m1 … m − 11 … 4 keys
Other internal node⌈m/2⌉ … m⌈m/2⌉ − 1 … m − 12 … 4 keys
Leaf—⌈(m−1)/2⌉ … m − 1 entries2 … 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 1 Search(x)
  1. node ← root
  2. while node is internal do
  3. i ← number of separators K in node such that K ≤ x ▷ children are numbered 0 … k
  4. node ← child i of node ▷ left of K: keys < K, right of K: keys ≥ K
  5. return the entry x if it is in node, otherwise not found
Algorithm 2 Insert(x)
  1. leaf ← Search(x); insert x into leaf, in sorted order
  2. if leaf has ≤ m − 1 entries then return ▷ room left: done
  3. ▷ leaf overflow: it holds m entries
  4. split leaf: keep the first ⌊m/2⌋ entries, move the other ⌈m/2⌉ to a new leaf L′, linked after leaf
  5. copy up the first key of L′ into the parent, with a pointer to L′ ▷ the key also stays in L′
  6. node ← parent
  7. while node holds m keys do ▷ internal overflow
  8. K ← the ⌈m/2⌉-th key of node
  9. split node: keys before K stay, keys after K (and their children) move to a new node N′
  10. if node is the root then create a new root holding K, with children node and N′ ; return ▷ height + 1
  11. push up K into the parent, with a pointer to N′ ▷ K leaves the node
  12. node ← parent
Algorithm 3 Delete(x)
  1. leaf ← Search(x); remove x from leaf
  2. if leaf has ≥ ⌈(m−1)/2⌉ entries then return ▷ no underflow: internal nodes are NOT modified
  3. ▷ leaf underflow
  4. S ← an adjacent sibling of leaf with the same parent (prefer one with spare entries)
  5. if S has > ⌈(m−1)/2⌉ entries then ▷ S can lend an entry
  6. redistribute: move one entry from S to leaf, and update the separator between them in the parent
  7. return
  8. merge leaf and S into one leaf; remove their separator and the pointer to the removed leaf from the parent
  9. node ← parent
  10. while node is not the root and node has < ⌈m/2⌉ − 1 keys do ▷ internal underflow
  11. S ← an adjacent sibling of node
  12. if S has > ⌈m/2⌉ − 1 keys then
  13. 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
  14. merge node + the separator pulled down from the parent + S into one node
  15. node ← parent
  16. 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:

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:

15304560369121521303345516066

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.

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.

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.

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):

directoryglobal depth = 200011011Ald = 2410081000Bld = 151017111Cld = 2210

(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}$.

Q4

When Extensible Hashing Goes Wrong

Same rules as in Q3 (h(k) = k, 2 keys per bucket), starting from this small table:

directoryglobal depth = 101Ald = 181000Bld = 1311

(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?

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.

Servers and keys on the circle0 = 2πk1k2k3k4k5k6k7S1S2S3S4

(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.