Model answer
For minimum degree 2, inserting 10,20,5,6,12,30,7,17 yields root [10,20] with leaf children [5,6,7], [12,17], and [30]. Split a full child before descending and promote its median.
Use the key terms, then explain the reasoning.
Trees & Applications
C++17
C++17B-Tree
B-trees store many keys per node and remain shallow, making them ideal for databases and storage systems where block access dominates.
What to understand
- Minimum degree
- Node splitting
- Multiway search
- Disk-page locality
Remember this
- 1All leaves stay at the same depth
- 2Nodes may hold many keys
- 3Splits propagate upward
- 4B-trees minimise storage I/O
Detailed notes
A B-tree node stores multiple sorted keys and child pointers, matching the large block size of disks and databases. High branching factor keeps the tree shallow, so one search performs few expensive block reads.
When insertion reaches a full node, splitting promotes its median key to the parent. Deletion may borrow from a sibling or merge nodes to preserve minimum occupancy; all leaves remain at equal depth.
How it works
- 1Search within a node to select one child interval.
- 2Split full children before descending during insertion.
- 3Promote medians while preserving sorted key ranges.
- 4On deletion, repair minimum occupancy by borrowing or merging.
Where it is used
- Database and filesystem indexes
- Storage engines with page-sized nodes
- Large ordered datasets on secondary memory
Common mistakes
- Treating a B-tree as a binary tree
- Confusing B-tree with binary search tree
- Ignoring minimum-key rules for non-root nodes
Complexity analysis
| Operation | Best | Average | Worst | Extra space |
|---|---|---|---|---|
| Search | O(log n) | O(log n) | O(log n) | O(1) |
| Insert | O(log n) | O(log n) | O(log n) | O(1) |
| Delete | O(log n) | O(log n) | O(log n) | O(1) |
Implementation perspective
This is primarily a conceptual or selection topic. Use the linked implementation topics in this section to see the invariant expressed in C++.
Exam & viva
Open a prompt when you are ready to check your answer.