Cây cân bằng & cây nhiều nhánhBalanced & Multiway Trees

Part of the Data Structures & Algorithms Roadmap knowledge base.

Overview

The previous note ended on a problem. A binary search tree gives O(log n) search, insert, and delete — but only while its height stays near log n, and nothing in the plain BST algorithm enforces that. Feed it 1, 2, 3, 4, 5 and you get a linked list with a wasted pointer per node, and every operation becomes O(n). Since sorted input (auto-increment IDs, timestamps, an ORDER BY export) is the single most common shape of real data, the plain BST is a structure whose worst case is also its most likely case.

The fix is to restore balance as part of every mutation. A self-balancing tree detects when an insert or delete has made some subtree too tall relative to its sibling and repairs it — in O(log n) or better — so the O(log n) bound becomes a guarantee rather than an average. There is no free lunch: you pay extra metadata per node (a height, a colour bit, a child count) and extra work per write. That trade is almost always worth it, which is why practically every ordered-map implementation you will use in production is a self-balancing tree.

This note covers four families and one non-tree alternative:

• AVL trees — strictly balanced, rebalanced by rotation. Fastest lookups, most rotations on write.
• Red-black trees — loosely balanced, fewer rotations. The default in most standard libraries.
• 2-3 trees — the conceptual bridge from binary to multiway; the direct ancestor of both red-black trees and B-trees.
• B-trees and B+ trees — high fan-out, block-oriented, designed around disk pages rather than comparisons. What every database and filesystem actually uses.
• Skip lists — probabilistic, not a tree at all, but achieves the same expected O(log n) with far simpler code and better concurrency.

The applied form of all this — how a database actually turns these structures into an index — is developed in ./18-indexing.md and, for PostgreSQL specifically, in ../../postgresql-dba/en/08-indexing-strategies.md.

Fundamentals

Why balance is worth paying for

Every BST operation costs O(h). The whole game is keeping h at Θ(log n).

At a billion keys the difference between a balanced tree and a degenerate one is 30 comparisons versus a billion. That is not a constant factor; it is the difference between a working system and a hung one.

There are two ways to get the guarantee:

1. Deterministic rebalancing — after each mutation, check a structural invariant and repair it (AVL, red-black, B-tree). Worst case guaranteed.
2. Randomization — make the structure’s shape depend on coin flips rather than on the input order, so no input can be adversarial (skip lists, treaps, randomized BSTs). Expected O(log n), with the worst case merely astronomically unlikely rather than impossible.

Both appear in production. The deterministic route dominates single-threaded in-memory maps and databases; the randomized route wins when the code needs to be simple, lock-free, or concurrent.

Rotations — the primitive operation

A rotation is a local, constant-time restructuring that changes a subtree’s height while preserving the in-order (BST) ordering. It is the single primitive that AVL, red-black, and splay trees are built from.

   Right rotation about y            Left rotation about x
   (y's left child x moves up)       (x's right child y moves up)

        y                                   x
       / \        rotate_right(y)          / \       rotate_left(x)
      x   T3      -------------->         T1  y      <--------------
     / \          <--------------            / \
    T1  T2         rotate_left(x)           T2  T3

   In-order before:  T1 x T2 y T3
   In-order after:   T1 x T2 y T3     <- unchanged, which is the whole point

Read the in-order sequence off both diagrams: T1 x T2 y T3 in each. That invariance is why rotation is safe — it changes the shape without changing the sorted order, so the BST property survives. Note that T2 — the subtree “in the middle” — is the one that changes parents; everything else just gets relabelled.

def rotate_right(y):
    """y's left child becomes the new subtree root. O(1)."""
    x = y.left
    t2 = x.right
    x.right = y
    y.left = t2
    update_height(y)      # y is now lower, update it first
    update_height(x)
    return x              # new subtree root — the caller must reattach it


def rotate_left(x):
    """x's right child becomes the new subtree root. O(1)."""
    y = x.right
    t2 = y.left
    y.left = x
    x.right = t2
    update_height(x)
    update_height(y)
    return y

The “return the new subtree root and let the caller reattach” convention is what makes the recursive insert code below work without parent pointers. It is worth adopting even in languages where parent pointers are cheap, because it removes a whole class of dangling-pointer bugs.

Key Concepts

AVL trees

Named after Adelson-Velsky and Landis (1962), the first self-balancing BST. The invariant is strict:

For every node, the balance factor — height(left) − height(right) — is in {−1, 0, +1}.

Each node stores its height (or, in tighter implementations, just the two-bit balance factor). Here the stored height uses the node convention: an empty subtree is 0, a single node is 1, which is what makes update_height a clean 1 + max(...).

class AVLNode:
    __slots__ = ("key", "left", "right", "height")

    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1        # node convention: a leaf has height 1, empty is 0


def height(node):
    return node.height if node else 0


def balance_factor(node):
    return height(node.left) - height(node.right) if node else 0


def update_height(node):
    node.height = 1 + max(height(node.left), height(node.right))

The four rotation cases. After an insert, at most one node on the path back up becomes unbalanced (|bf| = 2). Which repair to apply depends on the shape of the offending path — two edges, each going left or right:

LL — inserted into the LEFT subtree of the LEFT child      fix: one right rotation
        (30)                        (20)
        /                           /  \
     (20)          ==>           (10)  (30)
     /
  (10)

RR — inserted into the RIGHT subtree of the RIGHT child    fix: one left rotation
     (10)                           (20)
        \                           /  \
        (20)       ==>           (10)  (30)
           \
           (30)

LR — inserted into the RIGHT subtree of the LEFT child     fix: left on child, then right
        (30)              (30)                   (20)
        /                 /                      /  \
     (10)      ==>     (20)         ==>       (10)  (30)
        \              /
        (20)        (10)

RL — inserted into the LEFT subtree of the RIGHT child     fix: right on child, then left
     (30)             (30)                     (40)
        \                \                     /  \
        (50)   ==>       (40)      ==>      (30)  (50)
        /                   \
     (40)                   (50)

The mnemonic: if the two edges point the same way, one rotation; if they zigzag, two. The double rotation’s first step converts the zigzag into a straight line, and the second step is then the simple case.

def avl_insert(node, key):
    """Standard AVL insert. Returns the (possibly new) subtree root. O(log n)."""
    # 1. Ordinary BST insert
    if node is None:
        return AVLNode(key)
    if key < node.key:
        node.left = avl_insert(node.left, key)
    elif key > node.key:
        node.right = avl_insert(node.right, key)
    else:
        return node                       # duplicate key: no change

    # 2. Update this node's height on the way back up
    update_height(node)

    # 3. Rebalance if this node is now out of range
    bf = balance_factor(node)

    if bf > 1 and key < node.left.key:    # Left-Left
        return rotate_right(node)
    if bf < -1 and key > node.right.key:  # Right-Right
        return rotate_left(node)
    if bf > 1 and key > node.left.key:    # Left-Right
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if bf < -1 and key < node.right.key:  # Right-Left
        node.right = rotate_right(node.right)
        return rotate_left(node)

    return node

Worked example — inserting 10, 20, 30, 40, 50, 25:

insert 10:   (10)                                        balanced

insert 20:   (10)                                        bf(10) = -1, OK
                \
                (20)

insert 30:   (10)  bf = -2, RR case      (20)            one left rotation about 10
                \                        /  \
                (20)      ======>     (10)  (30)
                   \
                   (30)

insert 40:      (20)                                     bf(30) = -1, bf(20) = -1, OK
               /    \
            (10)    (30)
                       \
                       (40)

insert 50:      (20)                        (20)         bf(30) = -2, RR case
               /    \                      /    \        left rotation about 30
            (10)    (30)     ======>    (10)    (40)
                       \                        /  \
                       (40)                  (30)  (50)
                          \
                          (50)

insert 25:      (20)  bf = -2, and 25 goes into the LEFT subtree of the right child
               /    \                            -> RL case
            (10)    (40)
                    /  \
                 (30)  (50)
                 /
              (25)

   step 1: rotate_right(40's left = 30)      step 2: rotate_left(20)

        (20)                                       (30)
       /    \                                     /    \
    (10)    (40)                               (20)    (40)
            /  \                               /  \       \
         (25)  (50)                         (10) (25)     (50)
            \
            (30)                            final tree, height 2, all |bf| <= 1

Deletion works the same way — do the ordinary BST delete (the three cases from ./10-tree-data-structures.md), then rebalance on the way back up. The one difference that matters: an insert needs at most one rebalancing (single or double) to restore the invariant, while a delete can need O(log n) of them, because removing a node can shorten a subtree and cascade the imbalance all the way to the root. This is the main reason AVL deletes are more expensive than AVL inserts.

Height bound. Let N(h) be the minimum number of nodes in an AVL tree of height h. Then N(h) = 1 + N(h−1) + N(h−2) — a Fibonacci recurrence — which gives h < 1.44 · log₂(n + 2) − 0.328. So an AVL tree is never more than about 44% taller than a perfectly balanced tree. That is a tight bound, and it is why AVL wins on lookup-heavy workloads.

Red-black trees

A red-black tree is a BST where every node carries one extra bit of colour, subject to five rules:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (the NIL sentinel) is black.
4. A red node’s children are both black — no two reds in a row on any path.
5. Every path from a given node down to any of its descendant NIL leaves contains the same number of black nodes (the node’s black-height).

Rules 4 and 5 together bound the height: the longest root-to-leaf path can alternate red-black, and the shortest can be all black, so the longest is at most twice the shortest. Hence h ≤ 2 · log₂(n + 1).

That is a looser bound than AVL’s 1.44 log₂ n, and the practical consequence is exactly what you would expect: red-black trees are slightly taller, so lookups need a few more comparisons, but they need far less restructuring per write.

Why red-black is the more common library choice. The deciding factor is the delete path. AVL’s O(log n) rotations per delete each touch several nodes and dirty several cache lines; red-black’s guaranteed ≤ 3 rotations per delete replaces most of that work with recolourings, which are single-bit writes. Combined with a smaller per-node footprint (one bit versus a full height field), red-black gives more predictable write latency at the cost of a handful of extra comparisons on read. For a general-purpose container that has no idea what its workload will be, that is the safer default.

Where you will actually meet one:

• C++ std::map, std::set, std::multimap, std::multiset — red-black in every mainstream implementation.
• Java TreeMap, TreeSet, and HashMap’s treeified buckets (long collision chains convert to red-black trees to bound worst-case lookup).
• The Linux kernel — rbtree is used by the CFS scheduler, by the virtual memory area lookup, by ext3’s directory index, and by epoll.
• Ruby, Rust’s BTreeMap — Rust actually chose a B-tree instead, for cache reasons; see below.

Implementing red-black insert/delete correctly is a genuinely fiddly exercise (the delete has six cases), and it is not something to write from scratch in production. Understand the five invariants, understand the height bound they produce, and use the library.

2-3 trees

A 2-3 tree is the conceptual bridge between binary trees and B-trees, and understanding it makes red-black trees obvious. Every internal node is either:

• a 2-node: one key, two children (like a BST node), or
• a 3-node: two keys a < b, three children — < a, between a and b, and > b.

And crucially: all leaves are at exactly the same depth. This is a perfect-balance invariant, stronger than AVL’s.

                 [ 20 | 40 ]                <- a 3-node: two keys, three children
                /     |     \
          [10]    [25 | 30]    [50]

How can insertion preserve perfect depth? By growing upward instead of downward. Insert always lands in a leaf:

• If the leaf is a 2-node, it becomes a 3-node. Done — the depth of nothing changed.
• If the leaf is already a 3-node, it temporarily becomes a “4-node” with three keys, then splits: the middle key is pushed up into the parent, and the two remaining keys become two separate 2-nodes.
• If the parent was also full, the split cascades upward. If it reaches the root, the root splits and the tree’s height increases by one — for every leaf at once, which is precisely why all leaves stay level.

insert 35 into [25 | 30]:

     [ 20 | 40 ]                     [ 20 | 30 | 40 ]           [ 30 ]
    /     |     \                   /    |    |     \          /      \
 [10]  [25|30]  [50]   ==>       [10]  [25]  [35]  [50]  ==>  [20]    [40]
                                                              /  \    /   \
        [25|30|35] overflows;         parent overflows;    [10] [25] [35] [50]
        push 30 up, split into        push 30 up again
        [25] and [35]                                       height grew by 1,
                                                            all leaves still level

A 2-3 tree with n keys has height between log₃ n and log₂ n, so all operations are O(log n) in the worst case, with no rotations at all. The split-and-promote mechanism is the same one B-trees use, just with a fan-out of 3 instead of a few hundred.

The connection to red-black trees: a red-black tree is a 2-3-4 tree (the 2-3 tree generalized to allow 4-nodes) encoded in binary form. A 3-node is represented as a black node with one red child; a 4-node as a black node with two red children. Rule 5 (equal black-height on every path) is exactly the 2-3-4 tree’s “all leaves at the same depth” invariant, seen through that encoding. This is why the two structures have identical asymptotics.

B-trees

A B-tree is a 2-3 tree with the fan-out cranked up — from 3 to hundreds or thousands. The design goal is different from every structure so far: instead of minimizing comparisons, a B-tree minimizes block reads.

The reason is the memory hierarchy. Reading from an SSD costs on the order of 100 microseconds; from a spinning disk, 10 milliseconds; from RAM, ~100 nanoseconds; from L1 cache, ~1 nanosecond. And you never read one byte — the disk delivers a whole 4 KB or 8 KB page, and RAM delivers a whole 64-byte cache line, whether you asked for it or not. So the cost model changes: the number of pages touched is what matters, and the work done inside a page you have already loaded is nearly free.

A B-tree of minimum degree t obeys:

• Every node except the root has between t − 1 and 2t − 1 keys.
• Every internal node with k keys has exactly k + 1 children.
• All leaves are at the same depth.
• Keys within a node are sorted, and act as separators for the child ranges.

                        [ 100 | 200 | 300 ]                    <- root, one page
                       /      |     |      \
                      /       |     |       \
        [10|40|70]  [120|150|180]  [220|260]  [340|370|390]    <- one page each
        /  |  |  \   ...

  A key < 100 goes to child 0; 100 < key < 200 to child 1; and so on.

Sizing it concretely: if a node fills one 8 KB page and each key-plus-pointer entry costs 32 bytes, a node holds about 250 keys, so the fan-out is ~250. Then:

Four disk reads reach four billion keys. And in practice the root and the level below it are permanently in the buffer cache, so a lookup typically costs one or two actual reads. Compare with a balanced binary tree over 4 billion keys: height ~32, and each of those 32 node visits is a potentially random memory or disk access. Same O(log n), but the base of the logarithm is 250 instead of 2, and that base is the entire point.

class BTreeNode:
    def __init__(self, leaf=True):
        self.keys = []          # sorted
        self.children = []      # len(children) == len(keys) + 1 when not a leaf
        self.leaf = leaf


class BTree:
    """CLRS-style B-tree. t is the minimum degree: a node holds t-1..2t-1 keys."""

    def __init__(self, t=3):
        self.t = t
        self.root = BTreeNode(leaf=True)

    def search(self, key, node=None):
        """O(log_t n) node visits; each visit scans <= 2t-1 sorted keys."""
        node = self.root if node is None else node
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and node.keys[i] == key:
            return (node, i)
        if node.leaf:
            return None
        return self.search(key, node.children[i])

    def insert(self, key):
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            # Root is full: grow the tree UPWARD by one level. This is the only
            # way a B-tree's height ever increases, and it keeps all leaves level.
            new_root = BTreeNode(leaf=False)
            new_root.children.append(root)
            self._split_child(new_root, 0)
            self.root = new_root
        self._insert_non_full(self.root, key)

    def _split_child(self, parent, i):
        """Split parent.children[i] (which is full) around its median key."""
        t = self.t
        full = parent.children[i]
        right = BTreeNode(leaf=full.leaf)
        mid_key = full.keys[t - 1]              # the median moves up into the parent
        right.keys = full.keys[t:]              # upper half stays in the new node
        full.keys = full.keys[:t - 1]           # lower half stays in the old node
        if not full.leaf:
            right.children = full.children[t:]
            full.children = full.children[:t]
        parent.keys.insert(i, mid_key)
        parent.children.insert(i + 1, right)

    def _insert_non_full(self, node, key):
        """Pre-emptive splitting: we only ever descend into a node with room."""
        i = len(node.keys) - 1
        if node.leaf:
            node.keys.append(None)
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = key
        else:
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            if len(node.children[i].keys) == 2 * self.t - 1:
                self._split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self._insert_non_full(node.children[i], key)

The design detail worth noticing is pre-emptive splitting: _insert_non_full splits a full child on the way down, so it never has to walk back up to propagate an overflow. That turns insertion into a single downward pass, which matters enormously when each level is a disk read you would otherwise have to repeat.

B+ trees

A B+ tree is the variant that databases and filesystems actually deploy. Two changes from a plain B-tree:

1. All data lives in the leaves. Internal nodes hold only separator keys — no payloads, no row pointers.
2. The leaves are chained into a doubly linked list.

                        [ 100 | 200 ]                       <- internal: separators only
                       /      |      \
            [ 40 | 70 ]   [ 150 ]    [ 250 | 300 ]
             /   |   \      /   \      /    |     \
           ...  ...  ...  ...   ...  ...   ...   ...

   leaf level (every key appears here, with its data pointer):
   [10,20,40] <-> [50,70] <-> [100,120] <-> [150,180] <-> [200,...] <-> ...
        ^                                                                ^
        `------------------ linked list for range scans ----------------'

Both changes exist for the same reason: range queries.

• Because internal nodes carry no payload, each one fits more separator keys per page, so fan-out goes up and height goes down. A B+ tree over the same data is typically shorter than the equivalent B-tree.
• Because the leaves are linked, WHERE created_at BETWEEN '2026-01-01' AND '2026-03-31' becomes: one O(log n) descent to the first matching leaf, then a sequential walk along the leaf chain until the upper bound. Sequential reads are what disks and prefetchers are best at. In a plain B-tree the same scan would have to keep climbing back up into internal nodes to find the next key, producing a scattered access pattern.
• Every lookup costs exactly the same number of node visits (all data is at leaf level), so latency is uniform and predictable rather than “fast if the key happens to sit in the root”.
• Leaves are typically kept only partially full (PostgreSQL’s default fillfactor for B-tree indexes is 90) so subsequent inserts can land without splitting a page.

This is why the structure is essentially universal in storage systems:

That last row is the interesting one. Rust’s BTreeMap is an in-memory structure, with no disk in sight, and it still uses a B-tree — because the same argument applies one level up the hierarchy. A CPU cache line is 64 bytes; packing several keys into one node means one cache miss brings in several comparisons’ worth of data, whereas a pointer-chasing red-black tree pays a cache miss per level. B-trees are not “the disk structure”; they are “the structure for any medium with a nonzero block size”, and that is every medium.

For how PostgreSQL exposes and tunes this in practice — CREATE INDEX, index-only scans, fillfactor, bloat, REINDEX — see ../../postgresql-dba/en/08-indexing-strategies.md and ../../postgresql-dba/en/11-storage-internals-and-vacuum.md. For the data-structure view of indexing in general, including hash and ISAM indexes, see ./18-indexing.md.

Skip lists

A skip list abandons trees entirely. It is a sorted linked list with express lanes: a base list containing every element, and above it a stack of progressively sparser lists, each element promoted to the next level with probability p (usually 0.5).

level 3:  HEAD ---------------------------------> 30 --------------------> NIL
level 2:  HEAD ---------> 10 -------------------> 30 --------> 50 -------> NIL
level 1:  HEAD ---------> 10 ------> 20 -------> 30 --------> 50 -------> NIL
level 0:  HEAD --> 5 --> 10 --> 15 --> 20 --> 25 --> 30 --> 40 --> 50 --> NIL

Search for 40: start top-left. At level 3, 30 < 40 so move to 30; next is NIL so
drop down. At level 2, next after 30 is 50 > 40, drop down. At level 1, same.
At level 0, 30 -> 40. Found. Four levels, a handful of comparisons.

The search is exactly binary search’s idea implemented with pointers: at each level, walk forward while the next key is smaller than the target; when you would overshoot, drop a level. Since each level has about half the nodes of the one below, there are O(log n) levels and O(1) expected steps per level, giving expected O(log n) search, insert, and delete.

import random


class SkipNode:
    __slots__ = ("key", "forward")

    def __init__(self, key, level):
        self.key = key
        self.forward = [None] * (level + 1)     # one next-pointer per level


class SkipList:
    MAX_LEVEL = 16
    P = 0.5

    def __init__(self):
        self.head = SkipNode(None, self.MAX_LEVEL)
        self.level = 0                          # highest level currently in use

    def _random_level(self):
        """Coin flips: level k with probability p^k. Expected height O(log n)."""
        lvl = 0
        while random.random() < self.P and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl

    def search(self, key):
        """Expected O(log n). Walk right while you can, drop a level when you cannot."""
        node = self.head
        for i in range(self.level, -1, -1):
            while node.forward[i] and node.forward[i].key < key:
                node = node.forward[i]
        node = node.forward[0]
        return node is not None and node.key == key

    def insert(self, key):
        # `update[i]` = the rightmost node at level i that precedes the insert point
        update = [self.head] * (self.MAX_LEVEL + 1)
        node = self.head
        for i in range(self.level, -1, -1):
            while node.forward[i] and node.forward[i].key < key:
                node = node.forward[i]
            update[i] = node

        if node.forward[0] and node.forward[0].key == key:
            return                              # already present

        lvl = self._random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.head
            self.level = lvl

        new = SkipNode(key, lvl)
        for i in range(lvl + 1):                # splice in, one level at a time
            new.forward[i] = update[i].forward[i]
            update[i].forward[i] = new

Why anyone uses this instead of a balanced tree:

• The code is a fraction of the size. Compare the ~30 lines above with a correct red-black delete (six cases, easy to get subtly wrong). No rotations, no rebalancing, no colour invariants.
• Concurrency. Insert and delete touch only a handful of forward pointers and never restructure a subtree, so a lock-free or fine-grained-locking skip list is genuinely practical. A lock-free balanced tree is a research paper.
• The input cannot be adversarial. The shape depends on the random number generator, not on insertion order, so sorted input is no worse than random input. (A tree without randomization has an exploitable worst case; a skip list’s worst case requires the RNG to conspire.)
• Range queries are trivial — the bottom level is already a sorted linked list.

The costs: expected rather than guaranteed bounds; O(n) extra pointers on average (with p = 0.5, about 2 pointers per node); and worse cache locality than a B-tree because every level is a pointer chase.

Where you will find them: Redis sorted sets (ZSET combines a hash table for member → score with a skip list for score-ordered range queries — ZRANGEBYSCORE is the leaf-chain walk), LevelDB and RocksDB memtables, Apache Lucene term dictionaries, and HBase.

Comparison

Note the two different worst-case columns hiding here. AVL/red-black/B-tree give guaranteed worst cases. Skip lists give expected ones — the probability that a skip list over a million keys has height above 60 is smaller than the probability of a hardware fault, so in practice the distinction is philosophical, but it does mean a skip list cannot offer a hard real-time bound.

Best Practices

• Use the library. std::map, TreeMap, BTreeMap, SortedDict from sortedcontainers — these are correct, tested, and tuned. Implement a red-black delete once to understand it, then never ship your own.
• Python has no built-in balanced tree. The practical substitutes are bisect on a sorted list (O(log n) search but O(n) insert — fine up to a few thousand elements), sortedcontainers.SortedDict/SortedList (a B-tree-like structure that is genuinely fast in practice), or heapq when you only need the extreme (see ./12-heaps-and-priority-queues.md).
• Choose AVL for read-heavy, red-black for write-heavy. If lookups outnumber mutations by a wide margin, AVL’s tighter height pays. If writes are frequent, red-black’s bounded delete cost pays. If you cannot characterize the workload, red-black is the safer default — which is exactly why libraries pick it.
• Reach for a B-tree, not a binary tree, whenever a block boundary exists. Disk pages, SSD pages, cache lines, network payloads. A fan-out of 250 turns 30 levels into 4.
• Prefer B+ over B when range scans matter. If your access pattern is BETWEEN, ORDER BY ... LIMIT, prefix matching, or “the next N after X”, the linked leaf level is the whole reason the query is fast.
• Never build a search tree by inserting sorted data into a non-balancing structure. If you must use a plain BST, either shuffle first or build from the median of a sorted array recursively, which gives a perfectly balanced tree in O(n).
• Consider a skip list when concurrency or simplicity dominates. Lock-free skip lists are a solved problem; lock-free balanced trees are not. Redis and RocksDB both chose skip lists for exactly this reason.
• Do not confuse “balanced” with “sorted-array fast”. For a static dataset that never changes, a plain sorted array with binary search beats every tree here — same O(log n), better cache behaviour, zero pointer overhead. Trees earn their overhead only when the data mutates. See ./09-search-algorithms.md.
• Remember the write amplification. Every index is a balanced tree that must be updated on every INSERT/UPDATE/DELETE. Five indexes on a table means five tree updates per write. This is the central tension of index design — see ../../postgresql-dba/en/08-indexing-strategies.md.
• Measure the height when debugging a slow tree. A structure that should be O(log n) and is behaving like O(n) almost always has a broken balance invariant, and the height is the single number that reveals it.

References

• roadmap.sh — Data Structures & Algorithms
• AVL tree — Wikipedia
• Red–black tree — Wikipedia
• 2–3 tree — Wikipedia
• B-tree — Wikipedia
• B+ tree — Wikipedia
• Skip list — Wikipedia
• Self-balancing binary search tree — Wikipedia
• CLRS — Introduction to Algorithms, Chapters 13 (Red-Black Trees) and 18 (B-Trees)
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• PostgreSQL Documentation — Index Types
• PostgreSQL Documentation — B-Tree Indexes (internals)
• Redis Documentation — Sorted Sets
• VisuAlgo — AVL and B-tree visualizations
• Big-O Cheat Sheet