B+ Tree

A B-plus tree is a height-balanced multiway search tree designed to minimize disk or page reads. Internal nodes hold separator keys and child pointers; all data records or record pointers reside at the same-depth leaves, which are commonly linked left to right for efficient ranges. Search compares a key with separators and descends one child per level. On insertion, add to the appropriate leaf; if it overflows, split it and copy a separator into the parent, recursively splitting parents as needed. Deletion usually borrows from or merges with a sibling while maintaining minimum occupancy. Be explicit about the chosen order convention because textbooks define it differently. High fan-out makes height small, so lookup and update are O(log_m n) page accesses for branching factor m; scanning r consecutive records is O(log_m n plus r) because leaf links avoid repeated root descents. Contrast this with a binary tree rather than claiming they are identical.