General · EdgepediaSeptember 17, 20267 min read

B+ tree

A B+ tree is a balanced, multi-way tree data structure that keeps all data records in its leaf pages while internal nodes hold only separator keys used to route searches, making it the standard index structure in database systems and file systems. It is a variant of the B-tree described by Rudolf Bayer and Edward M. McCreight in "Organization and Maintenance of Large Ordered Indexes" (Acta Informatica, 1972), and the two names are often used interchangeably in database documentation.¹^•²

Key fact	Detail
Origin	Bayer and McCreight, "Organization and Maintenance of Large Ordered Indexes," Acta Informatica 1(3): 173–189, 1972; a Boeing Scientific Research Laboratories technical report (D1-82-0989) preceded it in 1970¹^•³
Where data lives	All records sit in leaf pages; internal nodes store only keys and pointers, and leaves are chained left to right for range scans²
Original performance	Storage utilization at least 50% but generally much higher; an index of 15,000 keys was maintained at an average of 9 transactions per second on an IBM 360/44 with a 2311 disc⁴
Rebalancing	A node whose key count falls below ⌈(m−1)/2⌉ is rebalanced by borrowing from a sibling or merging; merges can propagate to the root and reduce tree height⁵
Database use	SQL Server rowstore indexes, InnoDB tables, and PostgreSQL B-tree indexes are all organized this way⁶^•⁷^•⁸
Page size in practice	InnoDB uses a default 16 KB index page; PostgreSQL reports that typically over 99% of index pages are leaf pages⁷^•⁸

Structure

A B+ tree of order m keeps its keys sorted at every level. Internal nodes contain separator keys and child pointers; a search descends from the root by comparing the sought key against the separators until it reaches a leaf. All leaves sit at the same depth, so every lookup costs the same number of node accesses, and that number grows logarithmically with the number of keys.²

Two properties distinguish the B+ tree from the original B-tree formulation. First, in a B+ tree the internal nodes carry no data records; every node of a plain B-tree stores keys together with their values, and there is no leaf chain.² Second, the leaf pages are linked into an ordered list. Once a search has found the starting leaf for a range query, the scan simply follows the linked list, collecting keys until it passes the upper bound. This is the structure's greatest strength for range scanning, and it is efficient for disk I/O as well, because leaf nodes are often laid out contiguously on disk so the scan reads sequentially.⁵

The wide nodes exist because the structure was designed for paged storage. Appending to a sorted array shifts everything after the insertion point, which across pages means rewriting the file; a tree of wide pages lets an insertion touch only the nodes along one root-to-leaf path.⁹

Insertion and deletion

Insertion descends to the leaf where the key belongs and inserts it there. When the leaf becomes too full, it divides in two: the higher half of its keys is placed into a fresh leaf, that leaf is inserted into the chain of leaves, and the parent receives a copy of a separator key—on a leaf split, this is the first key of the newly created right leaf. Splits can propagate upward and create a new root, which is how the tree grows.⁵

Deletion removes the key from its leaf. When a node's key count drops below the minimum of ⌈(m−1)/2⌉ for order m, the tree rebalances in one of two ways: redistribution, borrowing a key from an adjacent sibling, or merging, combining with a sibling and removing the separator key from the parent. Merges can propagate upward to the root and reduce the tree height by one.⁵

The exact split policy is an implementation choice rather than a universal rule.

Use in database systems

SQL Server organizes rowstore indexes as B+ trees. Each page in the tree is an index node: the top node is the root, the bottom nodes are leaves, and the levels between are intermediate. In a clustered index the leaf nodes contain the data pages of the underlying table, while root and intermediate nodes hold index rows with a key value and a pointer to the next level down or to a data row. Pages in each level are linked in a doubly linked list, and pages are ordered on the clustered index key; within a page, rows are kept in logical order by a slot array rather than physical order. When a table has multiple partitions, each partition has its own B+ tree.⁶

MySQL InnoDB stores all user data in pages comprising a clustered B-tree index, a layout that other systems call an index-organized table; secondary indexes are also B-trees containing the index key plus a pointer, which is the row's primary key, into the clustered index. The default index page is 16 KB. On insert, InnoDB tries to leave 1/16 of a clustered index page free for future growth: with sequential key-order inserts the pages end up about 15/16 full, while random-order inserts leave pages from 1/2 to 15/16 full. If a page's fill factor drops below MERGE_THRESHOLD, 50% by default, InnoDB tries to contract the tree to free the page.⁷

PostgreSQL implements the standard multi-way balanced tree as its default index type, handling equality and range queries with the operators <, <=, =, >=, and >, plus constructs such as BETWEEN, IN, and anchored LIKE patterns. Its indexes are multi-level trees in which each level can be used as a doubly linked list of pages, and typically over 99% of all pages are leaf pages. Recent versions add B-tree deduplication, which packs duplicate index tuples into posting list tuples to delay page splits, and bottom-up index deletion, which removes version-churn tuples from a leaf page when a split is anticipated.⁸^•¹⁰

Variants and trade-offs

Copy-on-write B-trees keep old page versions so readers never see torn writes. LMDB is described as the most prominent copy-on-write B-tree implementation, relying on memory-mapped I/O for zero-copy reads; that approach requires virtual address space proportional to the database size, which motivates alternative engines that use pread-based I/O with a page cache in memory-constrained environments.¹¹

B+ tree versus LSM-tree. B-tree indexes are read-optimized rather than write-optimized: every insert can dirty a random page, and the cost shows up as write amplification and write-ahead logging. A log-structured merge tree instead turns writes into sequential appends and moves the cost to read time and background compaction, trading read cost for sequential writes.

Delete-heavy workloads leave space behind. A delete-heavy table can leave the index bloated until it is rebuilt with REINDEX or VACUUM in PostgreSQL or OPTIMIZE TABLE in MySQL, though space within a surviving leaf is reusable immediately by later inserts or updates.²^•¹²

Research continues on specialized variants: cache-oblivious B-trees analyze split and merge costs in memory transfers, and designs such as FB+-tree target latch-free updates and cache efficiency for non-volatile memory and main-memory settings.¹³^•¹⁴

The original 1972 paper

Bayer and McCreight's paper organized the pages of a large ordered index into the structure they called B-trees and analyzed the scheme, obtaining performance bounds and computing a near-optimal page size k. Storage utilization was at least 50% but generally much higher. Experiments used indexes up to 100,000 keys; on an IBM 360/44 with a 2311 disc, an index of 15,000 keys could be maintained at an average of 9 transactions per second, and one of 100,000 keys at at least 4 transactions per second.⁴ The work appeared in Acta Informatica volume 1, number 3, pages 173–189, published by Springer.¹ A 1970 Boeing Scientific Research Laboratories technical report with the same title, D1-82-0989, preceded the journal version.³

The paper does not explain what the "B" stands for, and one retrospective teaching note remarks that the trees are not "Bayer trees" but "Boeing trees," reflecting the laboratory where the work was done; the question remains a matter of anecdote rather than settled record.³

References

Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Data structures › Trees

Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026

Notice something wrong?