Btrees

B-trees are a family of self-balancing search trees designed to work efficiently with large storage systems. They were introduced by Rudolf Bayer and Ed McCreight in 1972 to provide logarithmic time data access while minimizing expensive disk I/O. B-trees are widely used in databases and file systems.

Structure: In a B-tree of minimum degree t, every node other than the root contains between t-1 and 2t-1 keys. A node with k keys has k+1 children. All leaves appear at the same depth, which keeps the tree height balanced. Keys within a node are kept in sorted order, and children subtrees partition the key space between consecutive keys.

Operations: Search follows a path from root to a leaf by comparing the target key with keys in each node. Insertion adds the key to a leaf; if a node becomes full, it is split into two nodes with a median key promoted to the parent, possibly propagating upward. Deletion may borrow keys from siblings or merge nodes to maintain minimum occupancy, potentially reducing tree height.

Variants and performance: The B+ tree stores all actual data in the leaf nodes, while internal nodes hold only keys and pointers for navigation; leaves are often linked to enable efficient range queries. B*-trees and other variants adjust split/merge rules to increase space utilization. Time complexity for search, insertion, and deletion is O(log n) in the number of keys, and performance is sensitive to disk block size.

Applications: B-trees underpin many database indexes and file systems, enabling efficient lookup, insertion, and range queries with controllable disk I/O. They remain a standard data structure for external memory storage and large-scale indexing, where minimizing disk access dominates performance.