Introduction

Suppose you keep a million records and need to find one by its key. If they sit in a sorted array, binary search nails any lookup in about twenty comparisons. Wonderful — until you have to insert a new key in the middle, which means shifting half a million entries.

A plain binary search tree fixes inserts but has its own trap: feed it keys in sorted order and it degenerates into a linked list, turning every lookup back into a slow linear scan.

Balanced search trees are the answer to both problems at once. After every insertion or deletion they quietly reshape themselves so that the tree's height stays proportional to log n — meaning a lookup, an insert, and a delete each touch only a handful of nodes, even with billions of keys. This is the structure that indexes databases and filesystems.

Build a B-Tree

Below is a small B-tree where every node holds at most three keys. Insert numbers and watch what happens: when a node overflows, it splits in two and pushes its middle key up to the parent. That single rule keeps every leaf at exactly the same depth.

<p class="hint">This is a <b>B-tree</b>: every node holds at most 3 keys. Insert a number and watch a full node <b>split</b>, pushing its middle key up to the parent. All leaves stay at the same depth — that's what keeps the height tiny.</p>
<div class="controls">
  <input id="key" type="number" placeholder="key" />
  <button id="add" type="button">Insert</button>
  <button id="seq" type="button">Insert 1..15 in order</button>
  <button id="reset" type="button" class="ghost">Clear</button>
</div>
<div class="stats">
  <span>keys: <b id="count">0</b></span>
  <span>height: <b id="height">0</b></span>
  <span>a sorted-list chain would be <b id="naive">0</b> deep</span>
</div>
<div id="tree" class="tree"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
input { font: 600 14px system-ui, sans-serif; padding: .4rem .55rem; width: 86px;
        border: 1px solid #adb1b8; border-radius: 8px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stats { font-size: .9rem; color: #444; display: flex; gap: 1.1rem; flex-wrap: wrap; margin-bottom: .8rem; }
.stats b { color: #1d3557; }
.tree { display: flex; flex-direction: column; gap: 1.4rem; align-items: center; padding: .4rem 0; overflow-x: auto; }
.level { display: flex; gap: 1.4rem; justify-content: center; flex-wrap: nowrap; }
.node { display: flex; border: 1px solid #cdd9e3; border-radius: 8px; overflow: hidden;
        background: #e8eef3; box-shadow: 0 1px 2px rgba(0,0,0,.08); }
.node .k { padding: .35rem .55rem; font: 700 15px ui-monospace, monospace; color: #1d3557;
           border-right: 1px solid #cdd9e3; min-width: 30px; text-align: center; }
.node .k:last-child { border-right: none; }
.node.flash { animation: pop .5s ease; }
@keyframes pop { 0% { background: #ffe08a; } 100% { background: #e8eef3; } }

// A B-tree of order 4: each node holds at most MAX = 3 keys and at most 4 children.
    // On insert we descend to a leaf, add the key, and if a node overflows we SPLIT it:
    // the middle key moves up to the parent (creating a new root if needed). This keeps
    // every leaf at the same depth and the height at O(log n) — the guarantee behind
    // database indexes. Search/insert/delete are all O(log n) (Bayer & McCreight, 1970).
const MAX = 3; // max keys per node
function newNode(leaf){ return { keys: [], children: [], leaf: leaf }; }
let root = newNode(true);

function splitChild(parent, i){
  const child = parent.children[i];
  const mid = child.keys[1];                 // middle of 3 keys
  const left = newNode(child.leaf);
  const right = newNode(child.leaf);
  left.keys = child.keys.slice(0, 1);
  right.keys = child.keys.slice(2);
  if (!child.leaf){ left.children = child.children.slice(0, 2); right.children = child.children.slice(2); }
  parent.keys.splice(i, 0, mid);
  parent.children.splice(i, 1, left, right);
}
function insertNonFull(node, key){
  let i = node.keys.length - 1;
  if (node.leaf){
    while (i >= 0 && key < node.keys[i]) i--;
    if (node.keys[i] === key) return;        // ignore duplicates
    node.keys.splice(i + 1, 0, key);
  } else {
    while (i >= 0 && key < node.keys[i]) i--;
    i++;
    if (node.children[i].keys.length === MAX){
      splitChild(node, i);
      if (key > node.keys[i]) i++;
    }
    insertNonFull(node.children[i], key);
  }
}
function insert(key){
  if (root.keys.length === MAX){
    const s = newNode(false);
    s.children = [root];
    root = s;
    splitChild(s, 0);
  }
  insertNonFull(root, key);
}
function height(n){ return n.leaf ? 1 : 1 + height(n.children[0]); }
function count(n){ let c = n.keys.length; if(!n.leaf) n.children.forEach(ch => c += count(ch)); return c; }

// Render level by level (BFS) so siblings sit on the same row.
function render(flash){
  const tree = document.getElementById('tree'); tree.innerHTML = '';
  let level = [root];
  while (level.length){
    const row = document.createElement('div'); row.className = 'level';
    const next = [];
    level.forEach(n => {
      const nd = document.createElement('div'); nd.className = 'node' + (flash ? ' flash' : '');
      n.keys.forEach(k => { const s = document.createElement('span'); s.className = 'k'; s.textContent = k; nd.appendChild(s); });
      row.appendChild(nd);
      if (!n.leaf) n.children.forEach(c => next.push(c));
    });
    tree.appendChild(row);
    level = next;
  }
  const c = count(root);
  document.getElementById('count').textContent = c;
  document.getElementById('height').textContent = root.keys.length ? height(root) : 0;
  document.getElementById('naive').textContent = c; // a degenerate BST/list is n deep
}

function add(k){ if (Number.isFinite(k)){ insert(k); render(true); } }
document.getElementById('add').addEventListener('click', () => {
  const v = parseInt(document.getElementById('key').value, 10);
  add(v); document.getElementById('key').value = '';
});
document.getElementById('seq').addEventListener('click', () => {
  root = newNode(true);
  for (let i = 1; i <= 15; i++) insert(i);
  render(true);
  console.log('Inserted 1..15 in order. B-tree height =', height(root), 'vs a sorted chain depth of 15.');
});
document.getElementById('reset').addEventListener('click', () => { root = newNode(true); render(false); });
document.getElementById('key').addEventListener('keydown', e => { if (e.key === 'Enter') document.getElementById('add').click(); });
render(false);
Result
Console

Try inserting keys in sorted order (1, 2, 3, 4, …). A plain binary tree would grow into a tall thin chain; the B-tree instead stays short and wide. Watch the height counter — it barely moves while the number of keys climbs. That flat height is exactly why a lookup stays fast no matter how much data you pour in.

The Real Complexity

How fast is a balanced tree, really — and is this a settled question?

  • Search, insert, delete are all O(log⁡n)O(\log n). Because the height never exceeds a constant times log n, every operation walks one root-to-leaf path, so it scales beautifully: doubling the data adds just one level.
  • The balancing is cheap. A split (in a B-tree) or a rotation (in an AVL or red-black tree) is a local, constant-time fix-up after each update — you never rebuild the whole tree.
  • This is solved. The AVL tree (Adelson-Velsky & Landis, 1962) was the first; B-trees came from Bayer & McCreight (1970) for disk storage; red-black trees were introduced by Bayer (1972) and refined by Guibas & Sedgewick (1978). These aren't open problems — they are textbook, proven, everyday structures.
  • No magic, just invariants. Each variant enforces a simple rule (heights differ by at most one; or no two red nodes in a row; or all leaves at the same depth) that mathematically forces logarithmic height.

The contrast with a hard problem like P vs NP is the point: here the efficient algorithm is known, simple, and provably optimal for comparison-based ordered search.

Where It Matters

"Keep ordered data searchable while it changes" is one of computing's most universal needs, and balanced trees are the standard answer:

  • Database indexes: PostgreSQL, MySQL, Oracle and SQLite all use B-trees (usually B+ trees) so a query can find rows among billions without scanning the table.
  • Filesystems: NTFS, HFS+, Btrfs and others store directory entries and metadata in B-trees for fast lookups on disk.
  • Language libraries: C++'s std::map/std::set and Java's TreeMap are red-black trees, giving ordered iteration plus O(log⁡n)O(\log n) access out of the box.
  • In-memory and key-value stores: ordered indexes, range queries, and schedulers lean on the same logarithmic guarantee.

Understand why a balanced tree stays short and you understand the engine under SQL query optimization and the pattern matching indexes that make search feel instant.

Conclusion

Balanced search trees are one of computer science's quiet triumphs: a handful of local rules — split a full node, rotate an unbalanced one — keep the tree's height proportional to log n forever. Search, insert and delete all stay fast no matter how much data arrives.

So the next time a database returns a row from a billion in milliseconds, you're watching a balanced tree at work. It isn't an open mystery like P vs NP; it's a problem we solved decades ago — and then built the digital world on top of.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/balanced-trees/Content licensed under CC BY-NC 4.0.