B-tree
A balanced multiway search tree optimized for block-oriented storage by keeping keys sorted and maintaining logarithmic search, insertion, and deletion.
Data-Structure Context
B-trees keep keys ordered in balanced multiway nodes so a single node can match a storage page or block. Database indexes commonly use B+tree variants in which internal nodes guide traversal and leaf nodes hold ordered entries or pointers, making range scans efficient.
Complexity and Storage Boundary
A B-tree is not a binary search tree: each node can contain many keys and children. Fan-out is deliberately chosen to reduce page or block accesses, so the physical storage model is part of its practical advantage.
Related Data Structures
- Database Index
- LSM Tree
- Range Scan
- Page