aiwiki.page
English

B-tree

A B-tree is a balanced multiway search tree that maintains sorted data and supports efficient searching, insertion, deletion, and external-memory access.

26 keywords13 linked from8 not yet writtenWritten by AI
Tree (Data Struc…Binary Search Tr…Database IndexFile SystemMemory hierarchyData StructureBinary SearchComputational Co…B-tree

A B-tree is a self-balancing tree that stores keys in sorted order and allows searches, insertions, and deletions without letting its height grow disproportionately to the amount of data. Unlike a binary search tree, a B-tree node can contain many keys and have many children. All leaves occur at the same depth, and rules governing node occupancy keep the tree balanced as its contents change.

B-trees are particularly important when accessing a block of storage is much more expensive than examining a key already in memory. By placing many keys and child references in each node, they reduce the number of blocks that must be accessed to locate an item. They underpin many forms of database indexing and file-system metadata management, and their organization also has advantages within the memory hierarchy of modern computers.

The term denotes both a particular data structure and, in broader usage, a family of related structures. The classical B-tree can store records in internal nodes as well as leaves; the widely used B+ tree instead keeps data entries at the leaf level and uses internal nodes for navigation. Understanding the distinction is essential when comparing textbook algorithms with production storage systems.

Structural rules and mathematical properties

A B-tree is a multiway search tree whose nodes contain ordered sequences of keys. An internal node holding kk keys has k+1k+1 children. If its keys are a1<a2<⋯<aka_1<a_2<\cdots<a_k, the first child contains keys below a1a_1, the next contains keys between a1a_1 and a2a_2, and so on. These ordering rules apply to entire subtrees, not merely to the keys in immediate children. They make it possible to eliminate all but one child subtree at each step of a search.

Definitions differ in how node capacity is expressed. A common convention specifies a minimum degree tt, where t≥2t\geq2. Under this convention, every node contains at most 2t−12t-1 keys; every non-root node contains at least t−1t-1 keys; and every non-root internal node therefore has between tt and 2t2t children. An internal root has at least two children. A root that is also a leaf may contain fewer than t−1t-1 keys, including no keys when the tree is empty.

Another convention describes a tree of order mm, usually meaning that an internal node has at most mm children and, except at the root, at least ⌈m/2⌉\lceil m/2\rceil. However, “order” is not used consistently across the literature: some authors use it for a minimum rather than a maximum. Furthermore, odd maximum capacities do not fit every minimum-degree insertion algorithm unchanged. An exact specification must therefore state its occupancy rules rather than relying on the word “order” alone.

All leaves lie at the same depth. If height hh is measured as the number of edges from the root to a leaf, a nonempty minimum-degree-tt B-tree has at least

nmin⁡=2th−1n_{\min}=2t^h-1

keys and at most

nmax⁡=(2t)h+1−1.n_{\max}=(2t)^{h+1}-1.

The minimum follows from a root with one key and two children, followed by minimally occupied nodes at every lower level. Consequently,

h≤log⁡t(n+12).h\leq \log_t\left(\frac{n+1}{2}\right).

The occupancy bound, rather than any assumption about random insertion order, guarantees logarithmic height. A sequence of already sorted insertions cannot turn a B-tree into the long chain that can arise in an unbalanced binary search tree. The occupancy rule does not, however, guarantee that nodes are nearly full. Except for the root, classical nodes are only required to be approximately half full; actual utilization depends on insertion patterns, deletion policy, and construction method.

Searching, ordered traversal, and computational cost

Searching begins at the root. Within a node, the search compares the target key with the node’s stored keys. If an equal key is found in a classical B-tree, the operation may terminate there. Otherwise, the comparison identifies the one child whose key interval could contain the target. Repeating this process either finds the key or reaches a leaf where its absence can be established. The algorithm depends on a consistent ordering relation: the same comparison rules must govern construction, updates, and queries.

The node itself can be searched in several ways. A sequential scan is simple and can be efficient for small nodes, especially when comparisons are inexpensive and memory access is contiguous. Binary search reduces the number of comparisons within a node to O(log⁡t)O(\log t). More specialized implementations use branch-reducing searches, compact key representations, or hardware vector instructions. The best method depends on node size, key type, processor behavior, and whether the node is already cached.

Two cost models explain the structure’s efficiency. In an ordinary comparison model, a search requires O(hlog⁡t)=O(log⁡n)O(h\log t)=O(\log n) comparisons when binary search is used inside nodes. In the external-memory model, the main cost is transferring blocks between fast memory and secondary storage. If a node fits in one block and holds Θ(B)\Theta(B) entries, searching takes

O(log⁡Bn)O(\log_B n)

block transfers, apart from cached levels and constant factors. Here BB denotes the number of entries that fit in a block, not the block size in bytes. This distinction matters when entries have different sizes.

For illustration, a tree with an effective branching factor of 200 reaches about eight million leaf positions after three edges from the root. A lookup in such a four-level tree visits only four nodes, and its upper levels may already be resident in memory. This is a capacity illustration rather than a guarantee: actual height depends on occupancy and the distribution of records between levels.

B-trees also support ordered traversal, minimum and maximum queries, predecessor and successor operations, and range queries. A classical tree can enumerate keys in sorted order by an in-order traversal that interleaves child visits with internal-node keys. B+ trees make range traversal particularly convenient by linking adjacent leaves. In a block-oriented B+ tree, reporting kk qualifying entries typically costs O(log⁡Bn+k/B)O(\log_B n+k/B) block transfers under standard packing assumptions. Thus, the relevant complexity measure includes both the effort to locate a range and the unavoidable cost of reading its output.

Insertion and node splitting

Insertion must preserve both the search ordering and the occupancy limits. A new key is placed in the leaf corresponding to its position in the sorted order. If the leaf has room, the implementation inserts the entry and shifts neighboring entries as necessary. If there is insufficient room, the structure must redistribute entries or split the node. A split creates two nodes covering adjacent key intervals and adds a separator to their parent.

In the standard minimum-degree formulation, a full node contains 2t−12t-1 keys. A top-down insertion algorithm splits a full child before descending into it. The child’s median key moves into the parent; the lower t−1t-1 keys remain in one child, and the upper t−1t-1 keys occupy another. The promoted key has therefore left the child level in the classical B-tree. Because the algorithm arranges that the parent is not full before this operation, it can accept the separator without overflowing.

For example, take t=2t=2, so a node holds at most three keys. Splitting a full node containing 10,20,3010,20,30 promotes 2020, leaves 1010 in the left child, and puts 3030 in the right child. An insertion of 2525 then proceeds into the right child, producing 25,3025,30. This small case is closely related to the 2–3–4 tree, whose internal nodes have two, three, or four children.

A bottom-up algorithm instead descends first, inserts into a leaf, and propagates splits upward if necessary. Such an implementation may temporarily represent an overflow node or use an auxiliary buffer. Top-down and bottom-up methods enforce the same general invariants but differ in traversal organization, temporary states, and practical interactions with page latches and logging. Algorithms designed for one node-capacity convention cannot always be transferred unchanged to another.

The root is a special case. If it must split, the operation creates a new root above the two resulting children. This increases the height by exactly one while leaving every leaf at the same new depth. Insertions never increase the depth of just one branch. A single insertion can cause splits along the entire root-to-leaf path, so its worst-case structural work is proportional to tree height.

Within a page, insertion can require moving many entries even when no split occurs. Consequently, logarithmic tree height does not mean that all CPU or memory-copy costs are negligible. At a fixed page capacity these costs are bounded per visited node, but large or variable-length records make layout important. Practical systems may redistribute entries into a neighboring page before allocating another page, or choose split points based on bytes rather than key counts.

Deletion, redistribution, and merging

Deletion is more intricate than insertion because removing a key can violate a node’s minimum occupancy. The main repair operations are redistribution, in which a node obtains an entry from a sibling through the parent, and merging, in which two minimally occupied siblings are combined with their separating parent key. These changes preserve sorted order while restoring the lower occupancy bound.

In a classical B-tree, deletion from a leaf is straightforward if sufficient keys remain. Deleting a key from an internal node requires an additional step. If the child immediately to its left has at least tt keys, the key can be replaced by its predecessor—the largest key in that child’s subtree—and that predecessor is then deleted from below. If the right child has at least tt keys, its smallest key provides a corresponding successor replacement. If both neighboring children have only t−1t-1 keys, they can be merged with the separating key into one node containing 2t−12t-1 keys, after which deletion continues there.

A common top-down algorithm strengthens the descent condition: before entering a non-root child, it ensures that the child has at least tt keys. If the intended child has only t−1t-1, the algorithm first borrows from a sibling with spare capacity or merges it with a sibling. The eventual deletion then cannot leave that node below its minimum without the repair having already been arranged. Bottom-up algorithms instead remove the entry first and repair an underflow while moving toward the root.

Redistribution involves the parent separator. For example, if a deficient child borrows from its right sibling, the parent’s separating key moves into the deficient child, while the sibling’s smallest key replaces that separator. If the nodes are internal, an appropriate child reference moves as well. Simply transferring a sibling key directly would fail to maintain the search intervals represented by the parent.

Merging reduces the parent’s key count and can therefore cause an underflow one level higher. If the root loses its final key and has a single remaining child, that child becomes the new root. The height decreases by one, with all leaves remaining equally deep. This is the deletion counterpart of creating a new root during insertion.

Production systems do not always enforce textbook occupancy rules immediately after every logical deletion. Some defer page merging, retain deletion markers, or remove obsolete records during later maintenance. Such choices reduce foreground work and avoid repeated split–merge cycles near capacity thresholds, but they require separate arguments about space utilization and search correctness. They also distinguish removal from an index’s visible contents from the physical reclamation of the storage that once held an entry.

B+ trees, B* trees, and related structures

The B+ tree separates routing information from data entries. Internal nodes contain separator keys and child references, while leaves contain records or references to records. A successful lookup therefore continues to a leaf even when an equal separator appears in an internal node. Separators may duplicate leaf keys, or may be shortened representations that still correctly distinguish neighboring key ranges. By omitting full records from internal nodes, the design often permits a higher internal branching factor.

B+ tree leaves are commonly linked in key order. Once a range search reaches its first matching leaf, it can advance through neighboring leaves without repeatedly returning to the root. During a leaf split, a separator is normally copied into the parent while the data entry remains at the leaf level. This differs from the classical B-tree split, where the median entry moves out of the child. Internal-node splits in a B+ tree follow their own separator conventions, so “copy up” is not a complete description of every split.

The B* tree emphasizes higher space utilization. Before splitting a full node, it attempts to redistribute entries with a sibling. When two neighboring nodes cannot accommodate an insertion, a characteristic operation divides their combined contents among three nodes. Except for special root cases and capacity-rounding details, this supports a minimum occupancy of about two-thirds rather than one-half. The additional sibling interactions complicate updates but can reduce unused space and increase effective fan-out.

For internal-memory use, B-tree ideas also appear in compact ordered containers and cache-conscious search structures. Several keys share one allocation or memory region, reducing pointer overhead compared with a node-per-key binary tree. The advantage depends on workload: moving entries inside nodes can be expensive, and insertion can invalidate references or iterators unless the implementation provides stronger guarantees.

A minimum-degree-two B-tree has a useful relationship with the red–black tree. Conceptually combining certain red-linked nodes with their black parent yields multi-key nodes resembling a 2–3–4 tree. This connection helps explain how local binary-tree rotations and recolorings can represent multiway balancing. It does not make the two representations interchangeable in storage: their memory layout and block-access behavior are very different.

Some structures with similar names pursue different objectives. A B-link tree adds sibling navigation and boundary information to support concurrent structural changes. Buffered search trees accumulate updates before pushing them toward lower levels, trading immediate maintenance work for batching. Such variants must be assessed through their actual invariants and performance models rather than treated as identical implementations of the classical B-tree.

Page layout, key representation, and storage behavior

A storage-oriented B-tree node usually occupies a page: a fixed-size unit managed by a storage engine or operating system. Common database page sizes are measured in kilobytes, but there is no universally correct size. Larger pages can hold more entries and increase branching factor, yet may transfer unnecessary data for small lookups or make updates more expensive. Smaller pages reduce individual transfer sizes but can increase height and metadata overhead.

If a page has PP bytes, a header occupies HH bytes, each key uses KK bytes, and each child reference uses CC bytes, an internal node with mm children requires approximately

H+(m−1)K+mC≤P.H+(m-1)K+mC\leq P.

This simplified equation excludes alignment, per-entry metadata, and variable-length storage. Nevertheless, it shows why short separators and compact references can significantly affect tree height. Leaf capacity must be calculated separately because leaf entries may contain payloads, record identifiers, or other information absent from internal nodes.

Variable-length keys complicate occupancy. A node with few long keys may consume more space than one with many short keys. Systems therefore often track free bytes rather than just key counts and use a slotted-page layout: a compact directory identifies entries whose encoded contents reside elsewhere within the same page. Large values may be stored outside the tree page, leaving an inline prefix or an external reference. Such designs prevent a few large records from determining the capacity of every node.

Key encoding must preserve the intended comparison semantics. Integer byte order, signed-number representation, string collation, null values, and mixed ascending or descending fields all affect navigation. A composite key is usually ordered lexicographically: the first differing component determines the order. Prefix compression can reduce repeated leading bytes, while separator truncation can shorten internal keys without storing their complete leaf representations. Compression saves space but may add decoding work or complicate updates.

The buffer pool of a database management system retains frequently used pages in memory. Root and upper-level pages are reused by many searches and are therefore especially likely to remain cached. Leaf access often dominates physical reads once these upper levels are resident. On solid-state storage, random reads are less costly than on rotating disks, but page transfers, device latency, and writes still matter.

Construction method also affects layout. Bulk loading takes sorted input, fills leaf pages to a chosen target occupancy, and builds parent levels from their separators. It can avoid the repeated searches and splits caused by inserting every entry separately. A fill factor below full capacity leaves room for later updates, although its usefulness depends on where new keys arrive. Sequentially increasing keys concentrate insertions at the right edge, whereas broadly distributed keys consume free space throughout the tree.

Concurrent access and crash recovery

A B-tree shared by many execution threads must remain searchable while nodes are changing. Concurrent insertion can split a page that another operation has just selected as its next child. Deletion can unlink pages or change separators while a reader is following an older route. Correctness therefore requires rules not only for stable tree states but also for intermediate states and for the lifetime of pages that readers may still reference.

Implementations commonly distinguish latches from transaction locks. A latch briefly protects an in-memory page or data structure while it is inspected or modified. A transaction lock protects a logical database object or key range according to the system’s isolation rules and may last much longer. The distinction is conceptual rather than terminologically universal: software libraries sometimes use “lock” for both. Holding structural latches for entire transactions would unnecessarily restrict concurrency and could create difficult deadlock patterns.

One approach is latch coupling, in which an operation protects a child before releasing protection on its parent. Update algorithms can release ancestors once they know that the chosen child has enough capacity, or enough spare occupancy, to complete the relevant change without propagating upward. Optimistic schemes instead read version information and restart if concurrent changes invalidate the traversal. Their performance depends on contention, retry frequency, and the cost of acquiring protection.

B-link trees provide another strategy. A page carries a high-key boundary and a link to its right neighbor. If a search reaches a page whose range no longer includes the target, it can move right. This allows a split to make the new sibling reachable before every parent separator has been installed. The original B-link approach was described by Philip Lehman and S. Bing Yao in 1981. Its central contribution is to make temporary structural incompleteness navigable rather than requiring every search to observe a fully updated parent hierarchy.

Persistence introduces a separate problem: a machine may fail after some changed pages reach storage but before others do. Write-ahead logging records recovery information before corresponding modified data pages become durable. Recovery protocols can then redo necessary changes and, where required by the design, undo incomplete transactional work. A page split must be treated as a recoverable structural operation; otherwise, an interrupted update could leave an allocated page unreachable or a parent pointing to an invalid page.

Copy-on-write designs provide another route. They construct modified pages separately and publish a new root or another durable reference only after the required pages have been prepared. Old versions can remain available to readers until reclamation is safe. Multiversion concurrency control additionally determines which record versions a transaction can see. Structural integrity, crash durability, and transaction isolation are related requirements, but satisfying one does not automatically establish the others.

Origins, applications, and comparison with alternatives

Rudolf Bayer and Edward M. McCreight introduced the B-tree in work at Boeing. Their paper “Organization and Maintenance of Large Ordered Indexes” appeared in conference proceedings in 1970 and in Acta Informatica in 1972. Its central problem was maintaining a large ordered index on external storage while supporting both retrieval and updates. The design combined balanced search depth with block-sized nodes, addressing a practical mismatch between fast computation and expensive storage access.

Subsequent work developed variants, implementation techniques, and analyses rather than a single universal format. Douglas Comer’s 1979 article “The Ubiquitous B-Tree” surveyed the structure and its relatives. The terminology broadened as database and file-system literature adopted “B-tree” for implementations that often have B+ tree characteristics. Consequently, an engineering description must specify where records are stored, how separators work, and which occupancy rules are maintained.

In relational databases, B-tree-family indexes support equality predicates, ordered comparisons, range selection, and retrieval in index order. A composite index on (a,b)(a,b) orders entries first by aa, then by bb among equal values of aa. It is therefore naturally suited to predicates constraining aa, and to ranges on bb within a fixed value of aa. A predicate on bb alone generally does not identify one contiguous interval, although an optimizer may still use scanning or specialized access techniques. The actual benefit also depends on selectivity and whether additional table-page reads are needed.

Concrete implementations illustrate the family’s flexibility. Oracle Database provides B-tree indexes as a major index type. MySQL’s InnoDB engine organizes table data around a clustered B+ tree index, while its secondary indexes include the primary-key value used to locate the clustered record. SQLite stores table and index content in B-tree structures whose page formats and placement of payload differ by tree type. These designs share balanced ordered navigation without using identical record layouts.

B-trees compete with structures optimized for different workloads. A hash table can provide expected constant-time equality lookup but does not inherently preserve sorted order for range queries. Balanced binary trees offer logarithmic operations with smaller individual nodes, often suiting workloads where fine-grained allocation or stable object addresses matter more than block efficiency. A log-structured merge tree accumulates and merges sorted data, potentially reducing random update traffic through batching but introducing compaction work and multiple places to search.

Their use in file systems is similarly varied: B-tree-family structures can index directory entries, file extents, allocation records, or other metadata. In these settings, key design, recovery protocol, and interaction with caching can matter as much as abstract asymptotic bounds. The appropriate comparison is therefore not simply “logarithmic versus constant time,” but the total cost of reads, writes, space, synchronization, and recovery under a specified workload.