What are B-Trees?

When storing and retrieving large volumes of ordered data, the goal is to keep search, insert, and delete operations efficient while staying balanced. B‑trees (Balanced Trees) do exactly this: maintain sorted keys, keep all leaves at the same depth, and deliver search, insert, and delete. Rudolf Bayer and Edward M. McCreight coined the term B-tree data structure at the Boeing Research Labs in 1971 in the paper Organization and Maintenance of Large Ordered Indices.

What is a B‑Tree (quick recap)

• Nodes hold multiple sorted keys and child pointers.
• All leaves are at the same depth (balanced).
• Internal nodes partition key ranges; leaves hold keys (and row references/rowids).
• Nodes are sized to match pages/blocks, minimizing I/O.

Simple Example – Start With a Binary Search Tree

Here start with an example of a balanced binary search tree (BST). A BST is a very basic structure that obeys a small number of rules:

1. A node can have a maximum of two children
2. The left node must be strictly less than the parant node
3. The right node must be strictly greater than the parent node

The time complexity for a balanced BST is Θ(log(n)), where n is the number of individul nodes. This degrades to the following example, which is still a valid BST, but here we have the worst case time complexity, giving Θ(n). This is an example of an unbalanced BST.

To prevent this issue we now look at the B-Tree. You can think of B-Tress as self-balancing trees that avoids the issue observed with an unbalanced BST. One initial change to the BST is that nodes are now allowed to have more than two children; this condition alone controls the height of the resultant tree. In data storage terms, this means less physical blocks of data in which to store the information. Accessing a large number of blocks of data results in condierable latency overhead.

Formally, the definition of a B-Tree is as follows:

1. Every node has at most m children.
2. Every node, except for the root and the leaves, has at least ⌈m/2⌉ children.
3. The root node has at least two children unless it is a leaf.
4. All leaves appear on the same level.
5. A non-leaf node with k children contains k−1 keys.

Each of the internal nodes separates values that divide its subtrees. In this example, if an internal node has 3 child nodes (or subtrees), then it must have 2 keys: a₁ and a₂. All values in the leftmost subtree will be less than a₁, all values in the middle subtree will be between a₁ and a₂, and all values in the rightmost subtree will be greater than a₂. (this example has a specific order – namely the branching factor, the maximum number of children a node may have of 3).

Big Picture: Why B‑Trees Stay Fast

• Shallow & wide: high fan‑out keeps height low.
• Balanced: every root‑to‑leaf path has equal length.
• Sorted leaves + leaf links: excellent for range scans and ordered results.
• Page‑aware: nodes align to I/O pages, minimizing page reads.

---

Searching Complexity on B Tree

• Worst case Time complexity: Θ(log(n))
• Average case Time complexity: Θ(log(n))
• Best case Time complexity: Θ(log(n))
• Average case Space complexity: Θ(n)
• Worst case Space complexity: Θ(n)

Takeaway

B‑trees deliver the trifecta of fast point lookups, efficient range scans, and stable update performance at scale. The combination of high fan‑out, balanced height, and sorted, linked leaves is why they remain the default general‑purpose index structure decades on.