2-3-4 trees and B-trees: multi-key nodes and database indexes

← Back to the section

A red-black tree keeps its balance with colours and rotations. A 2-3-4 tree reaches the same goal another way — it lets a node hold several keys and have several children. It is always perfectly balanced, and its idea leads straight to B-trees, the structure almost every database index is built on.

A node with several keys

In a binary tree a node has one key and at most two children. In a 2-3-4 tree a node may hold up to three keys and therefore up to four children — hence the name. A node comes in three shapes: one key (2 children), two keys (3 children), three keys (4 children).

Keys inside a node are ordered, and children are "wedged" between them: the leftmost child holds keys smaller than the first key, the next one keys between the first and the second, and so on. The search works just like in a binary tree, except that at every node the choice is not between two directions but between several: compare the wanted key with the keys of the node and descend into the right child.

Always balanced, thanks to splitting

The main property of a 2-3-4 tree is that it never goes out of balance, because it does not grow downwards along separate branches — it grows sideways, and all leaves always sit on the same level. The operation that guarantees this is a node split.

On insert we descend towards a leaf and split every full node on the way (a node that already holds three keys): the middle key moves up into the parent, and the two remaining keys go into two separate nodes. By splitting full nodes in advance, on the way down, we guarantee there is always room for the new key, and that the tree grows upwards from the root when it has to — so every branch keeps the same length. No rotations needed.

Because the tree is always balanced, search, insert and delete all cost O(log N) whatever order the data arrives in.

The kinship with red-black trees

A 2-3-4 tree and a red-black tree are, in essence, two notations for one idea. Any 2-3-4 tree converts mechanically into a red-black one and back: a node with several keys unfolds into a small group of red and black nodes, and a split corresponds to a recolouring plus a rotation. They are equivalent in efficiency, so the choice between them is a matter of implementation convenience.

B-trees: 2-3-4 for the disk

Let a node hold not three keys but hundreds or thousands, and you get a B-tree. Why so many? Because of how external storage — working with a disk — is arranged.

Reading from disk is thousands of times slower than reading from memory, and data arrives in blocks, in large chunks at once. So what matters is not the number of comparisons but the number of disk reads. A B-tree sizes its node to match the block (in PostgreSQL that is an 8 KB page): one block read gives you hundreds of keys and one step down the tree.

How low that makes the tree follows from arithmetic: a node with k keys gives k + 1 branches, and the height is the logarithm of the record count in base k + 1.

live example

public class TreeHeightDemo {
    static int levels(long keys, int keysPerNode) {
        long capacity = 1;
        int levels = 0;
        while (capacity < keys) {
            capacity *= keysPerNode + 1;
            levels++;
        }
        return levels;
    }

    public static void main(String[] args) {
        long keys = 1_000_000;
        System.out.println("binary tree, 1 key per node:    " + levels(keys, 1));
        System.out.println("2-3-4 tree, 3 keys per node:    " + levels(keys, 3));
        System.out.println("B-tree, 255 keys per node:      " + levels(keys, 255));
    }
}

Twenty levels against three — and that is not a difference in the order of growth: a logarithm stays a logarithm. What differs is its base, and on disk every level is paid for with a separate block read.

That is why indexes in databases and file systems are B-trees (more precisely, the B+ variant). When you create an index in PostgreSQL, that is what gets built underneath, and a fast index lookup is a descent costing a handful of disk reads.

How it is done in Java

It is worth knowing not only which class to take, but also what the standard library does not have. You will not find a 2-3-4 tree in java.util, nor a B-tree — and that is not an oversight but a consequence of what the collections are for.

The closest class is TreeMap (and TreeSet on top of it). Inside it is a red-black tree, which, as we have just seen, is the same 2-3-4 tree in binary notation: a 3-node unfolds into a black node with one red child, a 4-node into a black node with two red children, and a split becomes a recolouring. The promised complexity is the same: get, put, remove are guaranteed O(log n) whatever order the data arrives in.

A B-tree is absent from the collections on purpose. Its whole gain lies in saving trips to external storage: a wide node pays off when a single read lifts an entire block off the disk. java.util works with what already sits in memory, and there is no disk underneath it. So in the Java world B-trees live not in collections but inside databases, embedded storage engines and file systems — where a read is expensive.

The second difference shows up in range queries.

live example

import java.time.LocalDate;
import java.util.TreeMap;

public class RangeDemo {
    public static void main(String[] args) {
        TreeMap<LocalDate, String> orders = new TreeMap<>();
        orders.put(LocalDate.parse("2026-03-01"), "A-1");
        orders.put(LocalDate.parse("2026-03-07"), "A-2");
        orders.put(LocalDate.parse("2026-03-19"), "A-3");
        orders.put(LocalDate.parse("2026-04-02"), "A-4");
        System.out.println(orders.subMap(
                LocalDate.parse("2026-03-05"), true,
                LocalDate.parse("2026-03-25"), true));
    }
}

TreeMap assembles such a range by walking the tree — jumping up and down through references. In a B+ tree the leaves are additionally linked into a chain, so a range is one descent plus a linear read of consecutive blocks. That is exactly why a "from date to date" query over an indexed column in a database is so cheap.

A trap. The temptation to "cache the table in a TreeMap so we don't go to the database" works exactly as long as the data fits into memory with room to spare. Every entry is a separate node object: on millions of records that means millions of objects, pressure on the garbage collector, and a slow recovery after a restart, because the tree is rebuilt from scratch. The threshold at which it is time to go back to the database index is set not by big-O notation — both structures are logarithmic — but by the data volume and the memory you have.

In short

• In a 2-3-4 tree a node holds up to 3 keys and up to 4 children; the search is a multiway descent.
• The tree is always perfectly balanced thanks to splitting full nodes on the way down: it grows upwards from the root, all leaves on one level. Hence the guaranteed O(log N).
• A 2-3-4 tree is equivalent to a red-black tree: two forms of one idea, and Java's TreeMap is the binary form.
• Raise the number of keys per node to the size of a disk block and you get a B-tree — the basis of database and file-system indexes, where the goal is the fewest disk reads.
• A million records means twenty levels in a binary tree and three in a B-tree with 255 keys per node: the same order of growth, a very different cost per step.
• In a B+ tree the leaves are chained, so a range query is one descent plus a consecutive read; TreeMap assembles the same range by walking the tree.

What to read next

• Red-black trees — the same idea in binary notation: rotations and recolouring instead of splitting.
• Hash tables — lookups in O(1), but with no order and no ranges.
• Binary trees — where a search tree starts and why it degenerates.
• Choosing a data structure — when a tree, when a hash table, when an array.