1. Indexing
Definition – Index
Indexing a file means storing, for each record, its key and its physical address (the disk block containing the record) in a separate index file.
| Without an index | With an index |
|---|---|
| Sequential scan → | Browse the index, then direct access to the record |
| Binary search if the file is sorted → | Updates cost more: the index must be updated too |
2. B-Trees
Definition – B-tree of order (Bayer & McCreight, 1972)
A search tree with extra constraints (standard indexing method in DBMSs since 1979):
- All leaves are at the same level.
- Each node contains sorted keys with:
- for the root,
- for every other node.
- An internal node with keys has children.
- Keys in child lie between keys and of the father.
| Node | Min keys | Max keys | Children (internal) |
|---|---|---|---|
| Root | 1 | ||
| Other |
⚠️ “Order” is defined differently in other textbooks (e.g. CLRS uses minimum degree ; Knuth uses the maximum number of children). In this course, order = minimum number of keys per non-root node, so a node holds at most keys.
Node structure
| … |
|---|
| Subtree | Keys it contains |
|---|---|
| key | |
| key | |
| key |
Example – B-tree of order 1 (1 to 2 keys per node)
flowchart TD R["78"] --> A["33 · 40"] R --> B["85"] A --> A1["20"] A --> A2["38"] A --> A3["52"] B --> B1["81"] B --> B2["90"]
3. Search
Algorithm – find key
A generalization of BST search. Starting from the root, in each node:
- is in the node → found;
- → search ;
- → search ;
- → search ;
- the pointer to follow is null → not found.
Since keys inside a node are sorted, binary search can be used within the node.
Worked example (tree above)
- Search 52: 78 → → = [33 40] → → = [52] → found.
- Search 35: 78 → [33 40] → → = [38] → → is null → not found.
4. Insertion
Algorithm
find (with search) the leaf where the new key belongs
insert the key at its position in that node
if overflow (the node now has 2m+1 keys):
split it into two nodes of m keys each
if the node is not the root:
insert the middle key into the parent in the same way
(this may overflow the parent → apply recursively, possibly up to the root)
else:
create a new root containing the middle keyThe tree grows at the root, which keeps all leaves at the same level.
Worked example – insert 78, 52, 81, 40, 33, 90, 85, 20, 38 into an empty B-tree of order 1 (max 2 keys)
| Insert | What happens | Tree after |
|---|---|---|
| 78 | [78] | |
| 52 | [52 78] | |
| 81 | [52 78 81] overflow → split, 78 up → new root | [78] → [52], [81] |
| 40 | [78] → [40 52], [81] | |
| 33 | [33 40 52] overflow → 40 up | [40 78] → [33], [52], [81] |
| 90 | [40 78] → [33], [52], [81 90] | |
| 85 | [81 85 90] overflow → 85 up → parent [40 78 85] overflow → 78 up → new root | [78] → [40] → ([33], [52]); [85] → ([81], [90]) |
| 20 | [33] becomes [20 33] | |
| 38 | [20 33 38] overflow → 33 up into [40] | [78] → [33 40] → ([20], [38], [52]); [85] → ([81], [90]) |
Final tree = the example tree of §2.
5. Deletion
Deleting from an internal node
- Find the node containing the key.
- Find the adjacent key: the largest key of the left subtree (or the smallest of the right subtree) — it is always in a leaf.
- Replace the key to delete by this adjacent key.
- Delete the adjacent key from its leaf (case below).
Deleting from a leaf
remove the key from leaf s
if s now has < m keys: // underflow
let t be a sibling of s, e their separator in the parent p
if keys(s) + keys(t) < 2m: // MERGE
merge s, e and t into one node u
remove e from p; replace the pointers to s and t by one pointer to u
if keys(p) < m: apply the same treatment to p (unless p is the root)
else: // REDISTRIBUTE
share the keys evenly between s and t
update the separator in the parentIf the root ends up empty after a merge, the merged child becomes the new root (the tree loses one level).
Worked example – order 2 (2 to 4 keys per non-root node): delete 5, 6, then 4
Initial tree:
flowchart TD R["11"] --> A["5 · 8"] R --> B["16 · 21"] A --> A1["1 2 3 4"] A --> A2["6 7"] A --> A3["9 10"] B --> B1["12 13 14 15"] B --> B2["17 18 19 20"] B --> B3["22 23 24 25"]
Delete 5 (internal node): largest key of its left subtree = 4 → 4 replaces 5, removed from leaf [1 2 3 4] → [1 2 3] (3 ≥ 2 keys, OK).
flowchart TD R["11"] --> A["4 · 8"] R --> B["16 · 21"] A --> A1["1 2 3"] A --> A2["6 7"] A --> A3["9 10"] B --> B1["12 13 14 15"] B --> B2["17 18 19 20"] B --> B3["22 23 24 25"]
Delete 6 (leaf): [6 7] → [7], underflow (). Sibling [1 2 3]: , not → redistribute. Keys 1 2 3 + separator 4 + 7 → [1 2], new separator 3, [4 7].
flowchart TD R["11"] --> A["3 · 8"] R --> B["16 · 21"] A --> A1["1 2"] A --> A2["4 7"] A --> A3["9 10"] B --> B1["12 13 14 15"] B --> B2["17 18 19 20"] B --> B3["22 23 24 25"]
Delete 4 (leaf): [4 7] → [7], underflow. Sibling [1 2]: → merge [1 2] + 3 + [7] = [1 2 3 7]. Parent becomes [8] → underflow (), not the root. Its sibling [16 21]: → merge [8] + 11 + [16 21] = [8 11 16 21]. The root is now empty → the merged node becomes the root.
flowchart TD R["8 · 11 · 16 · 21"] --> C1["1 2 3 7"] R --> C2["9 10"] R --> C3["12 13 14 15"] R --> C4["17 18 19 20"] R --> C5["22 23 24 25"]
⚠️ Merge vs redistribute is decided by the sibling’s size: merge only if the two nodes together have fewer than keys (so that, with the separator, they fit in one node of ≤ keys); otherwise redistribute.
6. Complexity
Theorem – Number of keys in a B-tree of order and height
- Minimum:
- Maximum:
Derivation:
- Min: root has 1 key and 2 children; every other node has keys and children → level has nodes:
- Max: every node has keys and children → .
Hence the height is of order , and
| Operation | Worst case |
|---|---|
| Search | |
| Insertion | |
| Deletion |
( = order, = number of keys.)
Worked example: order , height → between and keys. The final insertion tree of §4 has height 2 and 9 keys ✓.
7. B⁺-Trees
Definition – B⁺-tree
A B-tree whose leaves contain all the keys:
- internal nodes contain keys only to direct the search toward the right leaf;
- leaves are chained together by pointers → fast sequential (range) scans;
- deletion is always done in a leaf.
Node layout: with , , .
Example
flowchart TD R["8"] --> A["4"] R --> B["10"] A --> L1["1 4"] A --> L2["5 8"] B --> L3["9 10"] B --> L4["11 12"] L1 -. next .-> L2 L2 -. next .-> L3 L3 -. next .-> L4
Keys 4, 8, 10 appear both as guides in internal nodes and in the leaves.
| B-tree | B⁺-tree | |
|---|---|---|
| Where keys are stored | once, in any node | all in leaves (copies in internal nodes) |
| Search ends | possibly at an internal node | always at a leaf |
| Sequential scan | needs a tree traversal | follow the leaf chain |
| Deletion | internal or leaf | always in a leaf |
⚠️ In a B⁺-tree the separator goes to the left on equality ( → ), unlike the strict inequalities of a B-tree.