What is a B-Tree?
Learn what a B-tree is, why databases use it for indexing, and how splitting and merging keep it balanced for this interview question.
Expected Interview Answer
A B-tree is a self-balancing, multi-way search tree where each node can hold multiple keys and multiple children, keeping the tree shallow so search, insert, and delete all run in O(log n) time even for enormous datasets stored on disk.
Unlike a binary search tree where each node has at most two children, a B-tree node of order m can have up to m children and m-1 keys, and every leaf sits at the same depth, which is what keeps the structure balanced. Because a single node holds many keys, one disk read can pull in a whole node's worth of decision-making, minimizing the number of expensive disk seeks needed to find a record. Insertions and deletions maintain balance by splitting overfull nodes or merging underfull ones, propagating changes upward only when necessary. This makes B-trees the standard indexing structure inside relational databases and filesystems, where minimizing I/O operations matters more than minimizing raw comparison count.
- O(log n) search, insert, and delete even at massive scale
- Wide nodes minimize disk I/O compared to binary trees
- Always balanced — every leaf at the same depth
- Standard backbone of database indexes and filesystems
AI Mentor Explanation
A B-tree is like a physical scorebook archive organized into thick binders instead of single index cards. Each binder page (node) holds several match records sorted together, so flipping to one page reveals many candidate matches at once instead of just one, cutting down how many times you have to walk to the shelf. Every binder sits on the same shelf row, so no lookup path is ever deeper than any other. When a binder page fills up, the archivist splits it into two evenly loaded pages rather than letting one page overflow, which is exactly how a B-tree stays balanced.
Step-by-Step Explanation
Step 1
Store multiple keys per node
Each node holds up to m-1 sorted keys and up to m child pointers, unlike a binary tree's single key.
Step 2
Search by scanning within a node
At each node, scan its sorted keys to find the matching key or the correct child range to descend into.
Step 3
Split on overflow during insert
When a node exceeds m-1 keys, split it in two and push the median key up to the parent.
Step 4
Merge or borrow on underflow during delete
When a node falls below the minimum key count, borrow a key from a sibling or merge with one to stay balanced.
What Interviewer Expects
- Explain nodes hold multiple keys and children, not just two
- State every leaf sits at the same depth, keeping the tree balanced
- Connect wide nodes to minimizing disk I/O for database indexes
- Describe split-on-overflow and merge-on-underflow for maintaining balance
Common Mistakes
- Confusing a B-tree with a binary search tree
- Forgetting that all leaves are always at the same depth
- Not connecting the structure to disk I/O minimization in databases
- Claiming B-trees are unbalanced or require manual rebalancing like a naive BST
Best Answer (HR Friendly)
“A B-tree is a balanced tree where each node can hold many keys instead of just one, which keeps the tree very shallow even for huge datasets. I think of it as the structure behind database indexes, because packing many keys per node means each disk read does much more useful work.”
Code Example
class BTreeNode:
def __init__(self, leaf=True):
self.keys = []
self.children = []
self.leaf = leaf
def search(node, key):
i = 0
while i < len(node.keys) and key > node.keys[i]:
i += 1
if i < len(node.keys) and key == node.keys[i]:
return node
if node.leaf:
return None
return search(node.children[i], key)
# A node might hold several sorted keys, e.g. [10, 25, 40]
# with 4 children covering ranges: <10, 10-25, 25-40, >40Follow-up Questions
- How does a B+ tree differ from a plain B-tree?
- Why do relational databases use B-trees instead of binary search trees for indexes?
- How does splitting a node during insertion propagate up the tree?
- What is the minimum number of keys a non-root B-tree node of order m must hold?
MCQ Practice
1. What is the primary reason B-trees are used for database indexes instead of binary search trees?
Wide nodes mean one disk read retrieves many keys worth of decision-making, drastically reducing disk seeks.
2. In a B-tree, what happens when a node exceeds its maximum number of keys during insertion?
Splitting on overflow and promoting the median key is how a B-tree maintains balance during insertion.
3. Which property is guaranteed for every B-tree?
All leaves sitting at the same depth is what keeps a B-tree balanced and guarantees O(log n) operations.
Flash Cards
How many children can a B-tree node of order m have? — Up to m children and up to m-1 keys.
Why are B-trees favored for database indexes? — Wide nodes reduce the number of disk reads needed to find a record.
What happens when a B-tree node overflows on insert? — It splits into two nodes, pushing the median key up to the parent.
What guarantees a B-tree stays balanced? — Every leaf is always at the same depth.