B+ Tree
A shallow multiway index with linked data leaves
Use wide nodes to reduce height
A B+ tree stores many separator keys per internal node, so one read chooses among many child ranges. All records live in leaves at the same depth. High branching factors keep disk and database indexes shallow, minimizing expensive page reads.
Try it
Search for a to descend from the root, or scan range [a, b] across linked leaves.
Leaves make range scans sequential
Exact search descends by separators in O(log_B n) node visits. Leaves are linked from left to right, so a range query locates its first key and then scans adjacent leaves without returning to upper levels.
Invariant: internal separators route every key to the correct child range, all leaves have the same depth, and leaf links preserve sorted order.
Splits, merges, and redistribution maintain occupancy as records change. Those updates are why B+ trees remain balanced without periodic rebuilding.