Binary Search Tree

• A tree where each node has at most two children (a ”left” child and a ”right” child).
• All values in the left subtree are < the node’s value.
• All values in the right subtree are > the node’s value.

Balanced BST

• These trees use special rotation rules during insertion/deletion to enforce this balance.

M-way Trees

M-way Tree: child0 < key0 < child1 < key1 < ... < key(m−2) < child(m−1)

Let n = the order (or fan-out) of the tree (this is our M)

B+ Trees

B+ Trees are M-Way (or K-Way) trees with a high fan-out (n)

Keys in each node are in order

• B+ Tree internal node: No linked list

| child0 | k0 | child1 | k1 | child2 | ...

• B+ Tree leaf node: with linked list

| rptr1 | key1 | rptr2 | key2 | rptr3 | key3 | nextLeaf |

B+ Trees Index

Capacity Requirement:

• Internal node（非叶节点）必须：children ∈ [ ⌈n/2⌉ , n ]