B-Tree
Subject: Computer and Technology noun /ˈbiː.triː/ 1 definition
- data-structures
- database-indexing
- file-systems
- computer-science
-
Definition (noun)
Entry #231 · UpdatedA B-Tree is a self-balancing search tree data structure that generalizes a binary search tree by allowing each node to hold multiple sorted keys and link to more than two child nodes. Built for systems that read and write data in large fixed-size blocks—such as databases and file systems—it keeps every leaf node at the same depth by splitting overflowing nodes and merging or rebalancing sparse ones during updates. Because each node packs many keys to align with a disk block or memory page, a B-Tree maintains a high branching factor and shallow height, guaranteeing logarithmic time complexity for lookups, insertions, and deletions while minimizing expensive storage I/O.
Common Types
Standard B-Tree: Stores keys alongside data records or pointers in both internal and leaf nodes, allowing searches to stop early at an internal node when a matching key is found.
B+ Tree: Stores all data payloads exclusively in linked leaf nodes while keeping only routing keys in internal nodes, increasing node fanout and speeding up sequential range scans.
B-Star Tree: Maintains at least two-thirds node occupancy instead of one-half by redistributing keys with sibling nodes before splitting two full nodes into three.
Copy-on-Write B-Tree: Writes modified nodes along the root-to-leaf path to newly allocated blocks rather than overwriting pages in place, enabling atomic transactions and snapshots in systems like Btrfs and LMDB.
Example
A relational database indexes a 100-million-row
orderstable using a B-Tree whose 16 KB page-aligned nodes each store roughly 500 keys, keeping the entire index only three to four levels deep. Looking up a specific order ID requires at most four disk page reads from root to leaf—or just one if the upper levels remain cached in memory—rather than the roughly 27 scattered pointer hops a balanced binary search tree would need.