B-Tree and B+Tree Search
B-Tree: multiway balanced search tree used in DBs and filesystems.
B+Tree: variant where all keys live in leaves (linked), great for range scans.
B-tree / B+ tree search demo
This placeholder can be extended with a visualisation of the B-tree / B+ tree structure and how a search walks through it.
- Multi-way balanced tree structure
- Node splitting and merging
- Range search demo
B-Tree traits
- Up to children per node (order )
- Root has at least 2 children (unless single-node tree)
- Non-root nodes have or more children
- Keys in-node are ascending; subtrees are ordered intervals
B+Tree traits
- All keys in leaves, leaves linked
- Internal nodes store only indexes
- Optimized for range queries
- From root, sequentially search keys in node
- If found, success
- Else follow child pointer
- Repeat until leaf or success
B+Tree search similar, but always ends at leaves.
- Starting from the root, follow the search path down to the leaf node where the key belongs
- Insert the key into the leaf node in key order
- Split: if the node then holds more than keys (2 for a 3-order B-Tree), split it into two nodes and move the middle key up into the parent
- If the parent overflows as well, keep splitting upwards until the root is reached (the tree grows by one level)
After a key is deleted, if the node holds fewer than keys, it has to be rebalanced:
- Borrowing: if a sibling has a spare key, borrow one from it (through the parent)
- Merging: if the sibling is short of keys as well, merge the node with the sibling and move the matching key of the parent down
- If the parent becomes short after that move, keep adjusting upwards; if the root is merged away, the height of the tree decreases by one
| Aspect | B-Tree | B+ Tree |
|---|---|---|
| Where the keys live | Spread over all nodes | All concentrated in the leaves |
| Internal nodes | Store keys and data | Store index information only |
| Leaf nodes | Not connected | Linked together by pointers |
| Search | Stops at the hit | Always goes down to the leaves |
| Range search | In-order traversal | Scans the linked list in order, which is efficient |
| Typical use | General indexes | Range queries in databases and filesystems |
- Large on-disk data; DB indexes
- Heavy range queries (B+Tree)
node = root
while node != null:
sequentially search the keys inside the node for x
if found:
return position
else:
follow child pointer
return -1
- Search: where is order, keys
- B+Tree similar, better for range scan
Exercise 1
Differences between B-Tree and B+Tree? Scenarios?
Approach: Compare the structures and the scenarios they suit.
Steps:
- B-Tree keys across all nodes; B+Tree keys only in leaves
- B+Tree leaves linked—range-friendly
Answer: B-Tree serves general lookups; B+Tree is good at range searches.
Exercise 2
In a 4-way B-Tree, min children of non-root?
Approach: The order of the tree and the number of children per node.
Steps:
- A non-root node has at least children
- With , that gives 2
Answer: 2 children.
2019·408
Which of the following statements about B-trees is incorrect?
Approach: Check the properties one by one.
Steps:
- (A) correct; (B) correct
- (C) wrong: the root may have only 1 child (a special case)
- (D) not enough information, the height cannot be determined
Answer: (C) is wrong. The root may have 1 child.
