Btree

A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. It is designed for storage systems that read and write large blocks of data, such as databases and file systems. A B-tree generalizes binary search trees by allowing nodes to have more than two children; each node contains multiple keys that act as separation values between its subtrees.

In a B-tree of minimum degree t (or order m), each node other than the root has at least t−1 keys and at most 2t−1 keys, and hence between t and 2t children. The root has at least one key and at most 2t−1 keys. All leaves reside at the same depth, ensuring balanced height. The keys within a node are kept in sorted order, and child pointers separate the key ranges of the node's subtrees.

Variants include B-trees and B+ trees. In a classic B-tree, keys and actual records or record pointers may be stored in internal nodes and leaves. In a B+ tree, all records are stored in the leaves, while internal nodes only hold keys for navigation and pointers to the leaves. B-trees are widely used for database indexes and filesystems because they minimize disk I/O through high fan-out and shallow height.

Operations such as search, insert, and delete preserve the B-tree properties and run in O(log n) time with respect to the number of keys n (more precisely O(log_m n) for a tree of order m). Insertion and deletion involve node splits or merges to maintain node capacity constraints.