AlgoVerse

B-tree

A balanced search tree whose nodes hold several keys and children, with every leaf at the same depth; full nodes are split on the way down. Built for disks: height O(log_t n).

On a disk, reading a block is expensive but reading several keys from the same block is nearly free. So instead of a binary tree, nodes hold several keys and children, which keeps the tree (and the number of disk reads) short.

Read the full explanation ↓
Input:
n=10PDF export

Ten keys into a B-tree with t = 2 (1 to 3 keys per node); the root splits twice and the tree reaches three levels.

  1. class BNode:
  2. def __init__(self):
  3. self.keys = []
  4. self.children = []
  7. def btree(items):
  8. # Minimum degree t = 2: every node has 1 to 3 keys (a 2-3-4 tree).
  9. t = 2
  10. root = BNode()
  11. for k in items:
  12. if len(root.keys) == 2 * t - 1:
  13. new_root = BNode()
  14. new_root.children.append(root)
  15. root = new_root
  16. split_child(root, 0, t)
  17. insert_nonfull(root, k, t)
  18. return root.keys
  21. def insert_nonfull(node, k, t):
  22. while node.children:
  23. i = 0
  24. while i < len(node.keys) and k > node.keys[i]:
  25. i = i + 1
  26. child = node.children[i]
  27. if len(child.keys) == 2 * t - 1:
  28. split_child(node, i, t)
  29. if k > node.keys[i]:
  30. i = i + 1
  31. child = node.children[i]
  32. node = child
  33. i = 0
  34. while i < len(node.keys) and k > node.keys[i]:
  35. i = i + 1
  36. node.keys.insert(i, k)
  39. def split_child(x, i, t):
  40. # The full child y gives its middle key to x and its upper half to a new node z.
  41. y = x.children[i]
  42. z = BNode()
  43. middle = y.keys[t - 1]
  44. z.keys = y.keys[t:]
  45. y.keys = y.keys[: t - 1]
  46. if y.children:
  47. z.children = y.children[t:]
  48. y.children = y.children[:t]
  49. x.keys.insert(i, middle)
  50. x.children.insert(i + 1, z)

Invariant: Every node except the root holds between t−1 and 2t−1 keys, each node's keys are sorted, and all leaves are at the same depth.

Start

∅

Local variables

Orange = changed in this step

items list

1020561230717325

Call stack

  1. btree()line 7
Step 1 of 230
Black = inserted · Orange = key stepplace: 0/10 · inserted: 0/10 · split: 0/4 · split_root: 0/2 · descend: 0/8 · split_full: 0/2
    Explanation

    The idea

    On a disk, reading a block is expensive but reading several keys from the same block is nearly free. So instead of a binary tree, nodes hold several keys and children, which keeps the tree (and the number of disk reads) short.

    In a B-tree of minimum degree t:

    • every node except the root holds between t − 1 and 2t − 1 keys; a node with k keys has k + 1 children;
    • the keys in a node are sorted, and child i holds the keys between key i−1 and key i;
    • all leaves are at the same depth.

    Here t = 2 (a 2-3-4 tree).

    Insertion (CLRS)

    On the way down, each full node is split before we enter it: its middle key moves up to the parent and its upper half becomes a new node. Since the parent is never full, a split never has to travel back up. The tree only grows taller when the root splits, which is why all leaves stay at the same depth.

    Deletion

    Deletion uses the same idea (before entering a child, make sure it has at least t keys), borrowing from a sibling or merging two nodes. Only insertion is shown here.