Balanced Trees: AVL, Red-Black and the B-Tree Behind Database Indexes

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8 and the index examples with PostgreSQL 18.6.

Guess First

We feed the same data to the BST (Binary Search Tree) we wrote in the 11th post of the series and to the AVL tree (the self-balancing tree published by Adelson-Velsky and Landis in 1962) we are about to write: book ids from the Bookstore catalog, exactly as they come from the database, that is, sorted from 1 to 10,000. Then we look at the height of both trees.

foreach (int n in new[] { 1_023, 10_000 })
{
    AvlTree<int> avl = new();
    UnbalancedBst<int> bst = new();
    Stopwatch sw = Stopwatch.StartNew();
    for (int i = 1; i <= n; i++) bst.Add(i);
    long bstMs = sw.ElapsedMilliseconds;
    sw.Restart();
    for (int i = 1; i <= n; i++) avl.Add(i);
    long avlMs = sw.ElapsedMilliseconds;
    Console.WriteLine($"n={n,6}: BST height={bst.Height(),6} ({bstMs} ms), AVL height={avl.Height,2} ({avlMs} ms), rotations={avl.Rotations}");
}

AvlTree<int> big = new();
for (int i = 1; i <= 1_000_000; i++) big.Add(i);
Console.WriteLine($"n=1000000: AVL height={big.Height}, rotations={big.Rotations}, valid={big.IsValid()}");

You already know the BST answer from post 11: sorted inserts put every new node to the right of the previous one, and the tree turns into a linked list. The real question is the AVL side. What is the height with 10,000 elements? 100, 50, 14? And how much does that number grow for 1,000,000 book ids?

Why Balance: The Height = O(log n) Guarantee

The output of a real run:

n=  1023: BST height=  1023 (4 ms), AVL height=10 (0 ms), rotations=1013
n= 10000: BST height= 10000 (141 ms), AVL height=14 (1 ms), rotations=9986
n=1000000: AVL height=20, rotations=999980, valid=True

In a BST every search, insert and delete costs as much as the path from the root to a leaf, so the cost is proportional to the height. With data arriving in random order the height stays around log n on average, but "on average" is not a guarantee. Real data loves to arrive sorted: auto-increment ids, orders in date order, alphabetical ISBN (International Standard Book Number) lists. With sorted inserts the height becomes n, and adding 10,000 elements takes 141 ms because every insert walks the whole chain (about n²/2 comparisons in total).

Balanced trees make a single promise: whatever the insert order, the height stays O(log n). At 1,023 elements the AVL height is 10, the same as a perfectly full binary tree. At 1,000,000 it is 20. You find one id among a million books with at most 20 comparisons. We showed how this cost is derived in the "Deriving Time Complexity from Code" post of the Big-O and Complexity series; here we need a single line: search, insert and delete are O(height), and in a balanced tree the height is O(log n).

The price of this guarantee is rotations. In the output above, 1,000,000 sorted inserts performed 999,980 rotations, almost one per insert. A rotation is a handful of constant-cost pointer changes; the real job is fixing the shape of the tree before it degrades.

Rotations: Turning Left and Right

A rotation flips the parent/child relationship of two nodes without breaking the BST order. In a left rotation the right child y of x moves up, x becomes its left child, and the old left subtree of y moves to the right of x:

private Node RotateLeft(Node x)
{
    Node y = x.Right!;
    x.Right = y.Left;   // y's left subtree is greater than x and less than y: it fits on x's right
    y.Left = x;
    Update(x);          // first x, which is now lower, then y
    Update(y);
    Rotations++;
    return y;           // new root of the subtree
}

private Node RotateRight(Node y)
{
    Node x = y.Left!;
    y.Left = x.Right;
    x.Right = y;
    Update(y);
    Update(x);
    Rotations++;
    return x;
}

Why does the order survive? Every value in the y.Left subtree is greater than x (it was on the right of x) and less than y (it was on the left of y). After the rotation that subtree sits to the right of x and to the left of y, so the in-order sequence is the same. Only the heights change: one side gets one level shorter, the other one level taller.

Implementing AVL Insert

The AVL rule is simple: at every node the difference between the heights of the left and right subtrees (the balance factor) is at most 1. Every node stores its own height; insert walks down like a normal BST insert, and on the way back every node updates its height and rotates if needed:

public sealed class AvlTree<T>(IComparer<T>? comparer = null)
{
    private sealed class Node(T value)
    {
        public T Value = value;
        public Node? Left;
        public Node? Right;
        public int Height = 1;
    }

    private readonly IComparer<T> _comparer = comparer ?? Comparer<T>.Default;
    private Node? _root;

    public int Count { get; private set; }
    public int Rotations { get; private set; }
    public int Height => HeightOf(_root);

    public bool Add(T value)
    {
        bool added = false;
        _root = Insert(_root, value, ref added);
        if (added)
        {
            Count++;
        }

        return added;
    }

    private Node Insert(Node? node, T value, ref bool added)
    {
        if (node is null)
        {
            added = true;
            return new Node(value);
        }

        int cmp = _comparer.Compare(value, node.Value);
        if (cmp < 0)
        {
            node.Left = Insert(node.Left, value, ref added);
        }
        else if (cmp > 0)
        {
            node.Right = Insert(node.Right, value, ref added);
        }
        else
        {
            return node; // the key already exists
        }

        Update(node);
        return Rebalance(node);
    }

    private Node Rebalance(Node node)
    {
        int balance = BalanceOf(node);
        if (balance > 1)
        {
            if (BalanceOf(node.Left!) < 0)
            {
                node.Left = RotateLeft(node.Left!);   // left-right case
            }

            return RotateRight(node);                 // left-left case
        }

        if (balance < -1)
        {
            if (BalanceOf(node.Right!) > 0)
            {
                node.Right = RotateRight(node.Right!); // right-left case
            }

            return RotateLeft(node);                   // right-right case
        }

        return node;
    }

    private static int HeightOf(Node? node) => node?.Height ?? 0;

    private static int BalanceOf(Node node) => HeightOf(node.Left) - HeightOf(node.Right);

    private static void Update(Node node) =>
        node.Height = 1 + Math.Max(HeightOf(node.Left), HeightOf(node.Right));
}

All four cases show up with three keys. The order 10, 20, 30 produces a chain leaning right (right-right) and a single left rotation fixes it. 30, 10, 20 forms an "elbow" (left-right): first the lower node rotates left, then the upper one rotates right. The program's output:

insert [10, 20, 30] -> root=20, rotations=1
insert [30, 20, 10] -> root=20, rotations=1
insert [30, 10, 20] -> root=20, rotations=2

A recursive insert is safe here because the recursion depth equals the tree height, and that height is 20 even with 1,000,000 elements. The StackOverflowException warning from the 5th post of the series applied to a degenerate BST; that is why the insert and Height() of UnbalancedBst are iterative.

The tests check two things separately: the height on sorted data and the invariant on random data. IsValid() checks the order, the stored height and the balance factor at every node; after 10,000 random inserts we compare the result with SortedSet<int>:

[Fact]
public void Add_RandomInput_StaysValidAndSorted()
{
    Random random = new(42);
    AvlTree<int> avl = new();
    SortedSet<int> expected = [];
    for (int i = 0; i < 10_000; i++)
    {
        int key = random.Next(50_000);
        Assert.Equal(expected.Add(key), avl.Add(key));
    }

    Assert.True(avl.IsValid());
    Assert.Equal(expected, avl.InOrder());
    Assert.True(avl.Height <= 1.44 * Math.Log2(avl.Count + 2));
}

Test run summary: Passed!
  total: 10
  failed: 0
  succeeded: 10
  skipped: 0
  duration: 278ms

The 1.44 constant in the last assert comes from the known AVL upper bound: the worst AVL tree is at most about 44% taller than a perfect binary tree with the same number of nodes. We did not write delete here; the logic is the same (the three BST delete cases, followed by Rebalance on the way back), the only difference being that a delete may need more than one rotation along the path. I leave it to you in the small experiment.

Red-Black Trees: Rules and Intuition

.NET's sorted collections use a red-black tree, not AVL. A red-black tree adds a single color bit to every node and keeps these rules:

• Every node is either red or black; the root is black.
• Leaves (null children) count as black.
• Both children of a red node are black: two reds never sit on top of each other.
• Every path from a node down to any leaf contains the same number of black nodes.

The intuition: the last rule makes the shortest path "all black", the third rule makes the longest path "black-red-black-red". So the longest path is at most twice the shortest and the height is bounded by 2·log₂(n+1). The AVL bound is tighter (about 1.44·log₂ n), so AVL searches walk a slightly shorter path. On the other hand a red-black tree keeps balance more loosely, so an insert performs at most two rotations and the remaining fixes are color flips. Red-black is usually considered better for write-heavy data and AVL for read-heavy data; in practice the difference is mostly a constant factor.

The SortedSet.cs file in dotnet/runtime describes its red-black tree as a BST representation of 2-3-4 trees and inserts top-down: it splits full 4-nodes along the search path. We can see this ourselves with reflection:

Type nodeType = typeof(SortedSet<int>).GetNestedType("Node", BindingFlags.NonPublic)!;
Console.WriteLine($"SortedSet<T>.Node properties: {string.Join(", ", nodeType.GetProperties().Select(p => $"{p.Name}:{p.PropertyType.Name}"))}");
FieldInfo setField = typeof(SortedDictionary<int, string>).GetField("_set", BindingFlags.NonPublic | BindingFlags.Instance)!;
Console.WriteLine($"SortedDictionary<TKey,TValue>._set: {setField.FieldType.Name} : {setField.FieldType.BaseType!.Name}");

SortedSet<T>.Node properties: Item:T, Left:Node, Right:Node, Color:NodeColor, IsBlack:Boolean, IsRed:Boolean, Is2Node:Boolean, Is4Node:Boolean
SortedDictionary<TKey,TValue>._set: TreeSet`1 : SortedSet`1

The Color property is the red-black color bit, and Is2Node and Is4Node are traces of the 2-3-4 tree connection. SortedDictionary does not write its own tree; it keeps key/value pairs in a TreeSet, which derives from SortedSet. We covered the API (Application Programming Interface) of these collections and when to pick which in the "Sorted Collections in C#" post of the C# Collections series; what matters here is knowing that even if you add a million sorted ids to a SortedSet, the height stays logarithmic.

B-Trees and B+Trees: Disk Pages and Fanout

In memory, moving from one node to the next takes nanoseconds. On disk the unit is the "page": PostgreSQL and Microsoft SQL (Structured Query Language) Server read data in 8 KB pages. If every level of a binary tree were a separate page read, a million rows would cost 20 page reads. A B-tree turns this around: a node is a page and holds hundreds of keys. The number of children of a node is called the fanout.

A small calculation shows the effect of fanout on height:

public static int Levels(long rows, int fanout)
{
    int levels = 1;
    double capacity = fanout;
    while (capacity < rows)
    {
        capacity *= fanout;
        levels++;
    }

    return levels;
}

rows          binary  fanout 100  fanout 300  fanout 500
1,000,000         20           3           3           3
100,000,000       27           4           4           3
1,000,000,000     30           5           4           4

Even in a billion-row table you find the row by reading four or five pages; and since the root and upper levels are already in memory (in the buffer cache), the reads that actually hit the disk are usually one or two pages.

Databases use a variant of the classic B-tree, the B+tree. There are two differences. First, inner nodes hold keys only for routing; the actual records (or pointers to them) live only at the leaf level. That fits more keys into inner nodes and increases the fanout. Second, pages at the same level are chained together. A range query like WHERE id BETWEEN 500000 AND 520000 goes down the tree once and then walks sideways along the leaf chain. Microsoft's index architecture guide states plainly that SQL Server rowstore indexes are B+trees and that the pages at each level are linked in a doubly linked list; the PostgreSQL documentation says that each level of a B-tree index can be used as a doubly linked list of pages.

A Real B+Tree in PostgreSQL

Let's see the theory in a real index. In my own temporary PostgreSQL 18 container I created a table with a million books and looked inside its primary key index with the pageinspect extension:

CREATE EXTENSION pageinspect;
CREATE TABLE books (id bigint PRIMARY KEY, isbn text NOT NULL, title text NOT NULL);
INSERT INTO books
SELECT i, lpad(i::text, 13, '978'), 'Book ' || i
FROM generate_series(1, 1000000) AS i;
VACUUM ANALYZE books;
SELECT level, root, fastroot FROM bt_metap('books_pkey');
SELECT relpages FROM pg_class WHERE relname = 'books_pkey';
SELECT live_items, btpo_level FROM bt_page_stats('books_pkey', (SELECT root FROM bt_metap('books_pkey')));
SELECT blkno, live_items, btpo_prev, btpo_next, btpo_level FROM bt_multi_page_stats('books_pkey', 1, 3);

 level | root | fastroot
-------+------+----------
     2 |  412 |      412

 relpages
----------
     2745

 live_items | btpo_level
------------+------------
         10 |          2

 blkno | live_items | btpo_prev | btpo_next | btpo_level
-------+------------+-----------+-----------+------------
     1 |        367 |         0 |         2 |          0
     2 |        367 |         1 |         4 |          0
     3 |        286 |         0 |       411 |          1

Let's read it. The root's level is 2, so the tree has three levels: the root, one intermediate level and the leaves. The root holds only 10 keys; each points to an intermediate page holding about 286 keys, and each intermediate page points to leaf pages holding 367 keys. 10 × 286 × 367 is roughly a million. The btpo_prev and btpo_next columns are the leaf chain itself: leaf 1's right neighbor is 2, and 2's left neighbor is 1. The index has 2,745 pages in total, that is 2,745 × 8 KB ≈ 21.4 MB.

Let's search for one id and see how many pages we touch (the output of the second run, since the first also includes planning and catalog reads):

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF) SELECT title FROM books WHERE id = 734512;

 Index Scan using books_pkey on books (actual rows=1.00 loops=1)
   Index Cond: (id = 734512)
   Index Searches: 1
   Buffers: shared hit=4
 Planning Time: 0.018 ms
 Execution Time: 0.033 ms

Four pages: the root, the intermediate page, the leaf and the table page that holds the row itself. A binary tree would take 20 steps over a million rows; the B+tree finished with three index pages. In a range scan the leaf chain comes into play:

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF) SELECT count(*) FROM books WHERE id BETWEEN 500000 AND 520000;

 Aggregate (actual rows=1.00 loops=1)
   Buffers: shared hit=58
   ->  Index Only Scan using books_pkey on books (actual rows=20001.00 loops=1)
         Index Cond: ((id >= 500000) AND (id <= 520000))
         Heap Fetches: 0
         Index Searches: 1
         Buffers: shared hit=58

20,001 rows, 58 pages. 20,001 / 367 ≈ 55 leaf pages, plus the few pages read on the way down. It went down the tree once ("Index Searches: 1") and read the rest by walking the leaf chain.

The clustered vs non-clustered distinction also makes sense in this picture. In SQL Server the leaf level of a clustered index is the table's data pages; rows sit in those leaves in key order. The leaf of a non-clustered index holds the keys plus a row locator pointing to the row, and one more step is needed for the rest of the row. In PostgreSQL the table is always a heap and every index resembles this second kind; the last of the four pages above was that extra step. We saw how to define and query these indexes with EF (Entity Framework) Core in the EF Core series; here we just met the data structure underneath.

Measurement: Searching Sorted Data

I built the three trees with sorted inserts and searched for 1,000 random keys. UnbalancedBst is the baseline:

[MemoryDiagnoser]
public class TreeLookupBenchmarks
{
    private UnbalancedBst<int> _bst = null!;
    private AvlTree<int> _avl = null!;
    private SortedSet<int> _sortedSet = null!;
    private int[] _probes = null!;

    [Params(1_000, 10_000)]
    public int N;

    [GlobalSetup]
    public void Setup()
    {
        _bst = new();
        _avl = new();
        _sortedSet = [];
        for (int i = 0; i < N; i++) // sorted input: the worst case for a plain BST
        {
            _bst.Add(i);
            _avl.Add(i);
            _sortedSet.Add(i);
        }

        Random random = new(42);
        _probes = [.. Enumerable.Range(0, 1_000).Select(_ => random.Next(N))];
    }

    [Benchmark(Baseline = true)]
    public int UnbalancedBst() => _probes.Count(_bst.Contains);

    [Benchmark]
    public int Avl() => _probes.Count(_avl.Contains);

    [Benchmark]
    public int SortedSet() => _probes.Count(_sortedSet.Contains);
}

The measurements were taken on an Apple M5 (10 cores), macOS 27.0.1, .NET 10.0.13 and BenchmarkDotNet 0.15.8. I ran the benchmarks one at a time, but other work was running on the machine at the same time; look at the ratios, not the absolute numbers.

| Method        | N     | Mean        | Ratio | Allocated |
|-------------- |------ |------------:|------:|----------:|
| UnbalancedBst | 1000  |   360.99 us |  1.00 |         - |
| Avl           | 1000  |    10.41 us |  0.03 |         - |
| SortedSet     | 1000  |    10.19 us |  0.03 |         - |
|               |       |             |       |           |
| UnbalancedBst | 10000 | 5,136.85 us | 1.000 |         - |
| Avl           | 10000 |    14.33 us | 0.003 |         - |
| SortedSet     | 10000 |    14.06 us | 0.003 |         - |

When N grows tenfold, 1,000 searches in the unbalanced BST go from 361 µs to 5.1 ms (each search walks half the chain on average); in AVL and SortedSet from 10 µs to 14 µs. That is exactly logarithmic growth: ten times the elements make the path only three or four steps longer. There is no measurable difference between our AVL and the BCL's (Base Class Library) red-black tree; both keep the height small and the rest is a constant factor. None of the searches allocate.

Production Notes

Do not ship your own AVL. The implementation in this post is for learning; if you need a sorted set or map, SortedSet<T> and SortedDictionary<TKey, TValue> are already balanced, tested and maintained. If you do write your own, the reason must be clear: for example storing the subtree size in every node to answer "the k-th element" or "how many records are smaller than this value" in O(log n) (an order statistic tree). The BCL does not offer that.

A balanced tree is an expensive structure. Every element is a separate heap object carrying two child references and a height or color field. If the only question is "does it exist?", HashSet<T> is usually faster and leaner, and if the data is loaded once and read many times, a sorted array with binary search (the 10th post of the series) often wins. What makes a tree truly valuable is staying sorted while the data changes and answering range queries.

In a database the key choice shapes the B+tree. An ever-increasing key (identity, sequential GUID (Globally Unique Identifier) values) always writes to the rightmost leaf and pages stay full. A random key (random GUID) lands on a different leaf on every insert, splits full pages (page splits) and bloats the index. In SQL Server the clustered key is also carried in the row locator of every non-clustered index, so a wide clustered key makes every index bigger. We covered index design in practice in the EF Core and SQL series.

Common Pitfalls

Forgetting to update heights. After a rotation, compute the height of the node that moved down first, then the node that moved up. Reverse the order and a wrong height propagates upward, and after a while the tree silently goes out of balance. Running an invariant check like IsValid() against random data in a test catches this immediately.

A subtree lost during rotation. Forget the x.Right = y.Left line and the left subtree of y falls off the tree; the element count may look right in a test, but searches miss some keys. That is why the test should check the whole in-order output, not just Count.

Walking a degenerate tree recursively. In an unbalanced BST a recursive height or traversal kills the process with a StackOverflowException at 100,000 levels. If you do not know the tree is balanced, write it iteratively.

Reading a B+tree as "every query is O(log n)". Column order and the shape of the query matter: an (AuthorId, PublishedAt) index cannot read a range on PublishedAt alone as one contiguous piece, because the leaf chain is sorted by AuthorId first. PostgreSQL 18's B-tree skip scan does a separate search for each AuthorId value in this case; as the number of distinct authors grows, that gets expensive too.

A Small Experiment

★☆☆ Add Min() and Max() to AvlTree<T>; then, after 1,000,000 sorted inserts, print the first five elements with InOrder().Take(5). Compare the Rotations count with randomly ordered input: which one rotates more?

★★☆ Write Remove(T value): the three BST delete cases (leaf, one child, two children and the in-order successor), then Update and Rebalance on the way back. In your test do 5,000 random inserts and 2,500 removes, and at every step check IsValid() and compare the result with SortedSet<int>.

★★★ In your own PostgreSQL container create the books table with id uuid DEFAULT gen_random_uuid() this time, insert a million rows and compare relpages with the bigint-keyed index. Why did the average live_items in leaf pages drop?

Balanced trees find the smallest or largest element in O(log n), but to do so they keep the entire order. Often we only want the most urgent job: the oldest order, the most urgent shipment, the best-selling book. In the next post we drop full ordering and move to a cheaper structure that keeps a single rule, "the smallest is always on top": heaps and priority queues.