B+ Trees are considered BALANCED because
2016
B+ Trees are considered BALANCED because
- A.
the lengths of the paths from the root to all leaf nodes are all equal.
- B.
the lengths of the paths from the root to all leaf nodes differ from each other by at most 1.
- C.
the number of children of any two non-leaf sibling nodes differ by at most 1.
- D.
the number of records in any two leaf nodes differ by at most 1.
Attempted by 328 students.
Show answer & explanation
Correct answer: A
Answer: the lengths of the paths from the root to all leaf nodes are all equal.
Why this makes B+ trees balanced:
All leaf nodes are at the same depth, so every path from the root to any leaf has equal length. That guarantees a single tree height and predictable O(log n) search cost.
Node-occupancy rules (each non-root internal node and each leaf must be at least about half full and at most full) keep nodes from becoming too sparse, but the defining balance property is the equal leaf depth.
A video solution is available for this question — log in and enroll to watch it.