What is a B-Tree?
A **B-Tree** is a self-balancing search tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.
Unlike standard binary search trees, a B-Tree is optimized for systems that read and write large blocks of data. It is widely used in **databases** and **file systems** (such as MySQL, PostgreSQL, and NTFS) because it minimizes expensive disk access operations by grouping multiple keys inside a single broad node.
B-Tree Properties (of Order M)
- Node capacity: Every node contains at most $M-1$ keys.
- Child limits: Every internal node (except root) has at least $\lceil M/2 \rceil$ children.
- Root condition: The root has at least 2 children if it is not a leaf node.
- Leaf leveling: All leaf nodes appear on the exact same level, ensuring uniform path depths.
- Keys and splits: An internal node with $k$ children contains exactly $k-1$ keys.
Complexity and Performance
- Search Complexity: O(log N)
- Insertion Complexity: O(log N)
- Deletion Complexity: O(log N)
- Disk Access Cost: O(log_M N) - Extremely low!