General · EdgepediaSeptember 17, 20267 min read

B-tree

A B-tree is a balanced, multiway search tree in which every node holds many keys and children, designed so that searching, insertion, and deletion in a large ordered index require only a few accesses to slow storage such as disk. In the standard definition, every non-root internal node has between ⌈m/2⌉ and m children, where the fixed integer m > 1 is called the order, leaves have no children, and the root follows separate rules and may have as few as 2 children; because the height, and therefore the number of accesses, stays small when m is large, the structure suits data that mostly lives on disk.¹

Key fact	Detail
Definition	Balanced search tree; every non-root internal node has between ⌈m/2⌉ and m children, m is the order, leaves have no children, and the root may have as few as 2 children¹
Origin	Rudolf Bayer and Edward M. McCreight, Boeing Scientific Research Laboratories, "Organization and Maintenance of Large Ordered Indices", 1970 workshop paper, journal version in Acta Informatica vol. 1, pp. 173–189, 1972²^•³
Name	The authors never explained the "B"; suggested readings include balanced, broad, bushy, Boeing, or Bayer¹
B+ tree invariants	Data records only in leaves; a leaf holds between ⌈L/2⌉ and L records; all leaves at the same level; internal nodes have between ⌈M/2⌉ and M children (root 2 to M)⁴
Database use	Default index type of PostgreSQL's `CREATE INDEX`; handles <, <=, =, >=, >, `BETWEEN`, `IN`, `IS NULL`, and left-anchored `LIKE` patterns⁵
Page sizes	InnoDB default index page 16 KB; PostgreSQL index entry limited to about one-third of a page⁶^•⁷
Search cost	Approximately $O(\log_f b_i)$ block accesses, where f is the fanout per node and $b_i$ the number of index entries⁸

Origin

Bayer and McCreight tackled how to maintain an index for a random-access file that changes over time, in situations where the index greatly exceeds the capacity of main storage and has to reside on a disk or drum. Their solution, described in the paper's own summary, is a page-sized, always-balanced ordered index that stays cheap to search and to update on disc.³ Both authors were at the Boeing Scientific Research Laboratories in 1972, and the work appeared in the ACM SIGFIDET Workshop on Data Description and Access in 1970 before the 1972 Acta Informatica version.²^•³

The meaning of the "B" was never explained by the authors. Douglas Comer, author of the 1979 survey "The Ubiquitous B-Tree", noted that "balanced", "broad", or "bushy" might apply, and that others suggest the B stands for Boeing, though he considered it appropriate to think of B-trees as "Bayer"-trees because of Bayer's contributions.¹

Structure and invariants

A B-tree node corresponds to a disk block, and a pointer stored in the tree is the number of the block containing the child node, usually interpreted as an offset into the corresponding file.⁹ Search operations touch only the disk blocks on the path from the root to the leaf containing the target, whereas range operations may continue through multiple leaf blocks, and updates may access sibling blocks during redistribution or merging, which is why a large order m keeps the access count down to one or two in typical indexes.⁹^•¹^•¹⁶

The B+ tree variant, the form most database systems actually deploy, keeps data records only in the leaves and uses internal nodes purely to guide searching. Its invariants are: a leaf always holds between ⌈L/2⌉ and L data records; all leaves sit at the same level; an internal node has between ⌈M/2⌉ and M children, except the root, which may have between 2 and M; and an internal node holds one fewer keys than it has children, with each stored key equal to the smallest key in the subtree rooted at the corresponding child. Keys in internal nodes are kept in sorted arrays.⁴ Sibling pointers between leaves support range searches even though leaf pages may not be physically contiguous on disk.¹⁰

Insertion and deletion. Finding a key is straightforward; insertion and deletion are more involved because they must preserve the invariants. Most insertions and deletions are simple, becoming complicated only when an insertion meets a full node or a deletion leaves a node less than half full.⁴^•¹¹ In Bayer and McCreight's scheme, a page splits only when both adjacent brother pages are full; otherwise an overflow between brothers avoids the split, and underflows do not propagate.² Their cost analysis shows that interference between mixed insertions and deletions degrades performance by at most a factor of 3 relative to pure workloads, and that in their experiments the scheme with overflows performed better than the scheme without.²

B-trees in database systems

B-trees, or some variant, are the standard file organization for applications requiring insertion, deletion, and key range searches.⁹ In PostgreSQL, the CREATE INDEX command creates B-tree indexes by default, and the query planner considers one whenever an indexed column is compared with <, <=, =, >=, or >, including equivalent constructs such as BETWEEN and IN, plus IS NULL and IS NOT NULL conditions. A B-tree index also serves left-anchored pattern matching such as col LIKE 'foo%', and can retrieve rows in sorted order.⁵ Any data type sortable into a well-defined linear order can be indexed, with the limitation that an index entry cannot exceed approximately one-third of a page after compression.⁷

PostgreSQL's implementation is a multi-level tree in which each level forms a doubly-linked list of pages, with a metapage at a fixed position at the start of the first segment file. Leaf pages, the lowest level, contain tuples pointing to table rows; internal pages point to the next level down. Typically over 99% of all pages are leaf pages.⁷

In MySQL's InnoDB engine, all indexes except spatial indexes (which use R-trees) are B-tree data structures, with index records stored in the leaf pages. The default index page is 16 KB, set by innodb_page_size at instance initialization. When records are inserted into a clustered index, InnoDB tries to leave 1/16 of each page free for future growth; sequentially inserted pages end up about 15/16 full, while randomly ordered insertions leave pages from 1/2 to 15/16 full. Bulk index creation uses a sorted index build governed by the innodb_fill_factor setting.⁶ B-trees also appear outside databases: NTFS organizes large directories as B-trees with records pointing to external clusters, and the Btrfs filesystem stores its metadata in btrees whose upper nodes hold only key and block-pointer pairs.¹²^•¹³

B-tree versus LSM-tree

The main modern alternative for write-heavy storage engines is the log-structured merge tree (LSM-tree), adopted by NoSQL products such as BigTable, Cassandra, and RocksDB because it was seen as offering better storage space efficiency and lower write amplification (physical data written exceeds logical data written, hurting performance and wear) than the B+ tree, which powers almost all relational database systems.¹⁴

Hardware changes the comparison. Storage hardware with built-in transparent compression, such as all-flash arrays and computational storage drives, compresses data losslessly without involving the operating system or application. Research published in 2021 and 2022 argued that this hardware narrows the physical storage cost gap between the two structures and creates room to reduce B-tree write amplification directly. Three design techniques, deterministic page shadowing, localized page modification logging, and sparse redo logging, reduced measured B-tree write amplification by over 10x on a commercial drive with built-in compression; the resulting B-tree achieved similar or smaller write amplification and physical storage use than RocksDB.¹⁵ In one comparison at 32 B record size and 4 client threads, WiredTiger's write amplification was 268 at 8 KB page size, 7.1x that of RocksDB's 38, while the modified B-tree reached 28, about 74% of RocksDB's figure.¹⁴ The same work notes that B-tree write amplification is only weakly dependent on dataset size, whereas LSM-tree write amplification grows with the number of levels as the dataset grows.¹⁵

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: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026

Notice something wrong?