Task 5 — Hashing & Indexing 25 marks
Build a B-Tree and a B+ Tree on employee_id for the insertion sequence 10, 11, 12, …, 22, with at most 3 keys per node. Completeness 6, correctness 6, viva 13.
The setup
Index key:
employee_id · Insertion order: 10 11 12 13 14 15 16 17 18 19 20 21 22 (ascending) · Max 3 keys per node · the trees must remain balanced — all leaves are always at the same level, and the tree grows only at the root. Split rule (Lecture 8 convention). Insert first; if a node then holds more than 3 keys, split it on the middle — N/2 (ceiling) with N = 4 keys, i.e. the 3rd key is promoted, the first two stay left and the last one goes right. For a B+ tree leaf the separator is copied up (it also stays in the leaf); the parent holds the first key of each child.
Note on conventions. Some textbooks promote the 2nd of the four keys instead, producing a mirror-image (but equally valid) tree. The trees below follow the course slides exactly — use this convention in the assignment and the viva.
A — B-Tree construction
| Insert | Action | Resulting shape |
|---|---|---|
| 10, 11, 12 | Add keys in sorted order — the root fills up (3 keys max). | [10 11 12] |
| 13 | The node now holds 4 keys → split. Split on the middle, N/2 (ceiling) with N = 4 → the 3rd key, 12, is promoted. Height becomes 2. | [12] → [10 11] · [13] |
| 14 | Goes into the right leaf. | [12] → [10 11] · [13 14] |
| 15 | Still fits. | [12] → [10 11] · [13 14 15] |
| 16 | [13 14 15 16] overflows → split, promote 15. | [12 15] → [10 11] · [13 14] · [16] |
| 17 | Goes into the last leaf. | [12 15] → … · [16 17] |
| 18 | Still fits. | [12 15] → … · [16 17 18] |
| 19 | [16 17 18 19] overflows → split, promote 18. | [12 15 18] → [10 11] · [13 14] · [16 17] · [19] |
| 20 | Goes into the last leaf. | [12 15 18] → … · [19 20] |
| 21 | Still fits. | [12 15 18] → … · [19 20 21] |
| 22 | [19 20 21 22] overflows → promote 21; the root [12 15 18 21] then overflows → split it and promote 18. Height grows to 3. | final tree below |
Final B-Tree
Read it back: root
[18] → left [12 15] → leaves [10 11] [13 14] [16 17]; right [21] → leaves [19 20] [22]. All leaves are at the same level ⇒ balanced. Searching for 16: 16 < 18 → left; 15 < 16 → third child → leaf [16 17] — 3 node reads. Searching for 18: found at the root in 1 read — a B-tree search may end at an internal node. B — B+ Tree construction
| Insert | Action | Resulting shape |
|---|---|---|
| 10, 11, 12 | Fill the first leaf. | [10 11 12] |
| 13 | Leaf overflows → split 2 | 2 and copy up; the parent stores the first key of each child. | [10 12] → [10 11] · [12 13] |
| 14 | Goes into the right leaf. | [10 12] → [10 11] · [12 13 14] |
| 15 | [12 13 14 15] overflows → split, copy up 14. | [10 12 14] → [10 11] · [12 13] · [14 15] |
| 16 | Goes into the last leaf. | [10 12 14] → … · [14 15 16] |
| 17 | Leaf overflows → copy up 16, so the root [10 12 14 16] overflows → split the internal node. Height grows. | [10 14] → [10 12] , [14 16] |
| 18 | Goes into the leaf [16 17]. | [10 14] → … leaf [16 17 18] |
| 19 | [16 17 18 19] overflows → split, copy up 18. | [10 14] → [10 12] , [14 16 18] |
| 20 | Goes into the leaf [18 19]. | leaf [18 19 20] |
| 21 | [18 19 20 21] overflows → copy up 20; [14 16 18 20] overflows → split and push 18 to the root. | [10 14 18] → [10 12] , [14 16] , [18 20] |
| 22 | Goes into the leaf [20 21] → [20 21 22]. No overflow. | final tree below |
Final B+ Tree
Read it back: root
Range query
[10 14 18] → [10 12], [14 16], [18 20] → leaves [10 11] [12 13] [14 15] [16 17] [18 19] [20 21 22], chained left → right. Searching for 21 still descends to a leaf (3 node reads) — every search in a B+ tree costs exactly the height, which is what makes performance predictable. Range query
WHERE employee_id BETWEEN 13 AND 20: descend once to [12 13], then walk the chain — 13, 14, 15, 16, 17, 18, 19, 20 — with no further tree traversal. B-Tree vs B+ Tree
| Aspect | B-Tree | B+ Tree |
|---|---|---|
| Data pointer location | Internal and leaf nodes | Only leaf nodes |
| Internal nodes | Store keys and record pointers | Store only keys for navigation |
| Leaf nodes | May or may not be linked | Usually linked |
| Search path | May end at an internal node | Always ends at a leaf node |
| Range query | Less efficient | More efficient |
| Fan-out | Lower | Higher |
| Common in DBMS | Less common | More common |
Why an index at all — and where hashing fits
Without an index the HR office’s WHERE employee_id = 17 is a full table scan: O(n) block reads. A B+ tree index turns it into O(log n) — three node reads here, and typically 3–4 even for millions of rows, because a real node holds hundreds of keys.
| Hash index | B+ Tree index | |
|---|---|---|
| Structure | Bucket = h(key) mod N | Balanced multi-way search tree |
| Equality lookup | O(1) — usually one bucket read | O(log n) |
Range / ORDER BY | Useless — hashing destroys order | Excellent — ordered leaves + sibling chain |
| Problem to manage | Collisions & overflow buckets; rehashing as data grows (extendable/linear hashing) | Splits and merges on insert/delete |
| Fit for this project | Good for an exact national_id lookup | Right default — employee_id, attendance_date ranges, salary reports |
In MySQL/InnoDB the primary key is a B+ tree that stores the rows themselves in its leaves (a clustered index); secondary indexes store the primary-key value and require one extra lookup. So
PRIMARY KEY (employee_id) in Task 2 already created the B+ tree drawn above.