B-tree simulator and visualizer

Each box is a node. The keys inside a node are kept in sorted order, and a node can hold at most order keys, the number you pick above. Nodes with a green border are leaves. Nodes with a dark border are internal nodes, whose keys only guide a search to the right child.

Type a number and press Insert. The key is added to a leaf. If that leaf is already full, it splits in two and its middle key moves up into the parent. Find highlights the path a search takes. Delete removes a key; if that leaves a node with too few keys, the node borrows a key from a neighbour or merges with it. The trace lists each step, and the numbers at the top show the height of the tree and how many nodes and keys it has.

To see why B-trees stay balanced, set the order to 3 and insert 10, 20, 30, 40, 50, 60 and 70 in that order. A plain binary search tree given sorted keys turns into one long chain. The B-tree splits as it fills, and all of its leaves stay at the same depth.

If you are checking a homework answer, set the switches in the top row to match your textbook first. Order means picks whether the order is the most keys a node can hold or the most children (Knuth's definition, one more than the keys). Split a full node picks between splitting full nodes on the way down, as CLRS does, and splitting a node only once it overflows, as most other books do. When an overflowing node can't be split evenly, Uneven split decides which half gets the extra key. B+ tree keeps every key in a leaf and links the leaves. Changing a switch replays the same keys under the new rules, and Copy link saves the settings and keys in the address. The answer key under the tree prints the tree after every step, one line per level, and Copy answer copies it as plain text.

A B-tree is a tree data structure that keeps keys in sorted order and allows search, insertion and deletion in logarithmic time. In a binary search tree, or a balanced one such as a red-black tree, each node has at most two children. A node in a B-tree can hold many keys and have many children, which keeps the tree short: a B-tree holding a billion keys is usually only three or four levels deep.

B-trees were designed for data stored on disk, where reading a block of data takes far longer than comparing keys in memory. Each node is sized to fill one block, usually called a page, so a single read brings in hundreds of keys at once. For this reason B-trees, and especially the B+ tree variant, are used for indexes in almost every relational database, including PostgreSQL, MySQL, SQLite, Oracle and SQL Server, and in many file systems.

A B-tree has three kinds of node:

• the root, the single node at the top;
• internal nodes, whose keys separate the key ranges of their children;
• leaves, the nodes on the bottom level, which have no children.

The keys in a node are stored in sorted order. An internal node with k keys has k + 1 children, and its keys divide the key range between them. Every key in the first child is smaller than the node's first key, every key in the second child lies between the first and second keys, and so on.

The order of the tree limits how many keys a node can hold. Textbooks define order in slightly different ways; in this simulator it is the maximum number of keys in a node. A B-tree keeps three rules at all times:

• no node holds more than the maximum number of keys;
• every node except the root is at least about half full;
• all leaves are at the same depth.

The last rule is what keeps the tree balanced. The tree grows taller only when the root splits, and becomes shorter only when the root is left empty, so every leaf is always the same distance from the root, whatever order the keys arrive in.

In Donald Knuth’s definition, a B-tree of order m has these properties:

• every node has at most m children;
• every internal node except the root has at least ⌈m/2⌉ children;
• the root has at least two children, unless it is a leaf;
• an internal node with k children holds k − 1 keys;
• all leaves are on the same level.

Introduction to Algorithms (CLRS) describes the same structure with a minimum degree t of at least 2. Every node except the root holds at least t − 1 keys, and every node holds at most 2t − 1 keys, so a full node has 2t children. The smallest case, t = 2, allows 2, 3 or 4 children per node and is called a 2-3-4 tree.

By default this simulator counts order as the maximum number of keys in a node; the Order means switch changes it to Knuth’s maximum number of children. The table shows how the default settings map onto the two textbook definitions. With an odd order the simulator follows the textbook rules exactly. With an even order, a split leaves the right-hand node one key short of the left, so the minimum is one key lower than in Knuth’s version.

Height of a B-tree

Because every node except the root is at least half full, the height grows very slowly. CLRS proves that a B-tree with n keys and minimum degree t has height h ≤ log_t((n + 1)/2), counting the edges on the path from the root to a leaf. A database page typically holds a few hundred keys, so take t = 100: a billion keys give h ≤ log₁₀₀(500,000,000) ≈ 4.35, at most four edges and five levels. Real nodes are usually fuller than the minimum, so three or four levels is typical.

Order changes the height noticeably. With the default settings, running the simulator’s insertion code on the keys 1 to 1,000 in sorted order gives a tree 9 levels deep at order 3, 6 levels at order 4 or 5, and 5 levels at order 7.

Why your answer can differ from the textbook’s

Two people can insert the same keys into a B-tree of the same order and draw different trees, and both can be right. Three choices change the shape. The first is what order means: the maximum number of keys or of children. The second is when a full node splits. CLRS splits every full node it passes on the way down, before it knows the new key will need the room, so a node never overflows. Most other textbooks insert the key into the leaf first and split a node only when it holds one key too many, passing the middle key up and repeating the split at the parent if that overflows too. The third is which half gets the extra key when a node splits unevenly.

For example, insert 10, 20, 30, 40, 50, 60 and 70 into a tree whose nodes hold at most 3 keys. Splitting on the way down gives a root of 20 and 40 over the leaves 10, 30 and 50 60 70. Splitting on overflow with the extra key in the left half gives a root of 30 and 60 over 10 20, 40 50 and 70. With the extra key on the right, the result matches the CLRS tree. The same keys in a tree of Knuth order 3 (at most 2 keys, a 2-3 tree) give three levels: 40 at the root, then 20 and 60, then the four leaves. Across 2,000 random exercises of 15 keys with at most 3 keys per node, the simulator’s two split rules produced different trees 1,895 times, so it is worth matching the convention before comparing answers.

Deletion differs in the same way. With splitting on the way down, the simulator follows the CLRS deletion algorithm, which tops up a child before descending into it. With splitting on overflow, it deletes from the leaf and repairs the tree on the way back up: a key removed from an internal node is replaced by its predecessor, and a node left with too few keys borrows from its left sibling if it can, then from its right sibling, and otherwise merges with one of them.

Search

A search starts at the root. Inside each node the keys are compared with the key being looked for, usually with a binary search, to decide which child to follow. This repeats until the key is found, or until a leaf is reached that does not contain it. A search reads one node per level, so its cost grows with the height of the tree: O(log n).

Insertion

A new key is always added to a leaf. The tree is first searched to find the right leaf, and the key is placed there in sorted position. If the leaf already holds the maximum number of keys, it is split: its middle key moves up into the parent, and the other keys are divided between two leaves. If the parent is also full it splits as well, and splitting can continue up to the root. When the root splits, a new root is created above it and the tree becomes one level taller.

This simulator follows the method in the textbook Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. On the way down, any full node is split before the search moves into it, so the insert never has to go back up the tree. The drawback is that a node is occasionally split when it did not strictly need to be.

Deletion

Deletion is more involved, because removing a key can leave a node with fewer keys than the minimum. A node that becomes too small is repaired in one of two ways:

• Borrowing. If a neighbouring node (a sibling) has a key to spare, one key moves from the sibling up into the parent, and a key from the parent moves down into the small node.
• Merging. If the sibling has no key to spare, the two nodes are combined into one, together with the key from the parent that separated them.

A merge takes a key away from the parent, which can leave the parent too small in turn, so repairs can continue up the tree. If the root loses its last key, its only child becomes the new root and the tree becomes one level shorter. To delete a key from an internal node, it is first replaced by the next smaller or next larger key, which always comes from a leaf, so the actual removal always happens in a leaf.

Time complexity of B-tree operations

Every operation walks one path from the root to a leaf, so its cost is proportional to the height of the tree. The table gives the time in terms of the number of keys n, and the number of pages a database would read.

Take a B-tree of order 3, where a node holds at most three keys (a 2-3-4 tree), and insert the keys 10, 20, 30, 40, 50, 60 and 70 in that order. Sorted input is the worst case for a plain binary search tree, which turns into a chain. You can reproduce every step by choosing order 3 in the simulator above and inserting the same keys.

Start from the tree at the end of the insertion example: root 20 and 40, leaves 10, 30 and 50 60 70. With order 3, every node except the root needs at least one key. Each case below starts from that same tree, except the last, and each result is exactly what the simulator produces.

Databases keep their tables and indexes on disk or SSD and read them in fixed-size pages, usually between 4 KB and 16 KB. Fetching a page that is not already in memory is slow compared with searching inside it: around 100 microseconds on a fast SSD and several milliseconds on a spinning disk, against well under a microsecond to search a page that is already in memory.

A balanced binary search tree over a billion keys is about 30 levels deep, so a lookup could need up to 30 page reads. A B-tree node that fills a page holds hundreds of keys, so the same billion keys fit in a tree three or four levels deep. The root and the levels just below it are used by every lookup, so they are almost always cached in memory, and most lookups read only one or two pages from storage.

This is why a B-tree index in a DBMS is usually the default: CREATE INDEX in PostgreSQL, MySQL and SQLite builds a B-tree (in practice a B+ tree) unless you ask for another kind.

The page size therefore sets the fan-out, the number of children each node can have. PostgreSQL uses 8 KB pages, MySQL's InnoDB engine uses 16 KB pages by default, and SQLite uses 4 KB pages by default. Larger pages make the tree shorter, but each lookup then reads more data.

Both keep keys in sorted order and support search, insert and delete in O(log n) time when balanced. The difference is the shape. A binary search tree node holds one key and has two children, so the tree is tall and each step down is cheap. A B-tree node holds many keys, so the tree is short and each step does more work inside a node. In memory the two are close; on disk, where every step down can cost a page read, the B-tree wins by a wide margin.

Most databases use a variant called the B+ tree. In a B+ tree the internal nodes contain only keys that direct a search. All of the records, or pointers to them, are stored in the leaves, and each leaf is linked to the next leaf in key order.

This has two practical advantages. Internal nodes hold only keys, so more of them fit in a page and the tree is shorter. And a range query such as WHERE id > 1000 can find the first matching leaf and then follow the links from leaf to leaf, without going back up the tree. The cost is that every search has to go all the way down to a leaf, even when the key it wants also appears higher up.

People often say "B-tree" when they mean a B+ tree. The simulator shows a classic B-tree by default. Switch Tree to B+ tree to see the other shape. When a leaf splits, the first key of the new right-hand leaf is copied up into the parent and stays in the leaf; when an internal node splits, its middle key moves up and leaves the node, as in a B-tree. Inserting 10 to 70 into a B+ tree whose nodes hold at most 3 keys gives a root of 30 and 50 over the leaves 10 20, 30 40 and 50 60 70, and the arrows show the links a range scan follows.

The B-tree was invented by Rudolf Bayer and Edward McCreight at Boeing Scientific Research Laboratories. They described it in a technical report in 1970, and their paper Organization and Maintenance of Large Ordered Indexes was published in the journal Acta Informatica in 1972. At the time, main memory was small and disks were slow, so an index that needed one disk read for every comparison was not practical. Their idea was to make each node large enough to fill a disk block.

The authors never said what the "B" stands for. Boeing, balanced and Bayer have all been suggested.

By 1979, Douglas Comer's survey The Ubiquitous B-Tree called B-trees "de facto, a standard for file organization". Later work added variants such as the B+ tree and the B* tree. In 1981 Philip Lehman and S. Bing Yao described the B-link tree, which lets many processes read and change the tree at the same time.

Many variants of the B-tree have been developed for particular uses:

• B+ tree. Records are kept only in the leaves, and the leaves are linked in key order. Used by most relational databases.
• B* tree. Nodes are kept at least two-thirds full instead of half full. When a node fills, keys are first moved to a sibling, and only when both are full are the two nodes split into three. This uses space better but makes insertion more complicated.
• B-link tree. Each node also points to its right-hand neighbour and records the largest key it may hold, so a search can still find its key while another process is splitting a node. PostgreSQL's B-tree index is based on this design.
• Copy-on-write B-tree. Pages are never changed in place. An update writes new copies of every page on the path from the leaf to the root, and older versions stay readable. This makes snapshots and crash recovery simple. Used by LMDB and by bbolt, the storage engine of etcd.
• Bw-tree. Designed at Microsoft Research. Changes are recorded as small update records attached to a page instead of rewriting the page, so threads do not need to lock it. Used in SQL Server's in-memory OLTP engine.
• Fractal tree. Internal nodes have buffers that collect new keys and pass them down in batches, which reduces the number of disk writes. Used in TokuDB.

In a database, many transactions read and change the same B-tree at once. To keep each page consistent, the database protects it with a short-lived lock called a latch. Latches are separate from the row locks that transactions use: a latch is held for a few microseconds while a page is read or changed, while a row lock can last for a whole transaction.

The simplest scheme, lock coupling (also called crabbing), latches a child page before releasing its parent. A writer keeps the parent latched until it knows the child will not split or merge, because a split or merge would change the parent too. The B-link tree reduces this. Because each node links to its right-hand neighbour, a search that reaches a node just after it was split can move right to find its key, so a reader needs to hold only one latch at a time. Some newer designs, such as the Bw-tree, avoid latches altogether and use atomic compare-and-swap instructions instead.

The main alternative to the B-tree in storage engines is the log-structured merge tree (LSM tree), used by RocksDB, Cassandra, ScyllaDB and LevelDB (see the LSM tree simulator). A B-tree updates its pages in place, so a stream of writes to random keys becomes a stream of writes to random pages across the index. An LSM tree collects writes in memory, writes them to disk as large sorted files, and merges those files in the background, a process called compaction.

As a rule of thumb, LSM trees cope better with heavy write loads, while B-trees give faster and more predictable reads and range scans. Many storage engines combine ideas from both.

Bulk loading

Building an index by inserting keys one at a time leaves pages partly empty: when keys arrive in random order, B-tree nodes end up about 69% full on average. When an index is created on an existing table, databases instead sort all the keys first and build the tree from the bottom up, filling one leaf after another and then building each level from the one below it. This is faster and gives a more compact tree. PostgreSQL's CREATE INDEX works this way.

Fill factor

A page that is completely full splits as soon as a new key arrives, so databases often leave some free space in each page when they build an index. In PostgreSQL this is the fillfactor setting, which defaults to 90% for B-tree indexes. A lower value suits an index that receives many inserts; 100% suits an index that rarely changes.

Memory

How much of an index stays in memory has a large effect on its speed. PostgreSQL's shared_buffers and InnoDB's innodb_buffer_pool_size set how much memory each database uses to cache pages.

Indexes on several columns

In an index on (a, b, c), entries are sorted by a, then by b, then by c. The index helps queries that filter on a, on a and b, or on all three columns, but not a query that filters on b alone.

Index bloat

In PostgreSQL, deleted and updated rows leave dead entries in an index until VACUUM removes them, so an index can grow much larger than its data. REINDEX CONCURRENTLY rebuilds an index without blocking writes, and the pgstattuple extension reports how much of an index is free or dead space.