B-Tree: The Foundation of Database Indexing

A B-Tree is a balanced, multiway search tree designed to organize large collections of ordered keys. Unlike a binary search tree, which stores one key per node and has at most two children, a B-Tree stores several sorted keys in each node and can have several child nodes.

This structure supports three central operations:

• Search: follow the key ranges from the root toward a leaf.
• Insert: place a new key in the correct leaf while preserving sorted order.
• Split: divide a node that has become too full and promote a separator key to its parent.

B-Trees are important because they provide an organized way to search through large collections of ordered data. Databases use B-Trees as a foundation for indexing: rather than examining every stored record one by one, an index can guide a search through a small number of increasingly specific decisions.

This article explains the shape of a B-Tree, the invariants that keep it valid, how search works, how insertion changes the structure, how node splitting can propagate toward the root, and why the combination of balance and multiple keys per node makes B-Trees useful for database indexing.

1. The basic idea​

A binary search tree stores one key in each node. A node can have at most two children:

• The left child contains keys smaller than the node’s key.
• The right child contains keys larger than the node’s key.

A B-Tree generalizes this idea by allowing one node to contain several sorted keys and several children. The keys inside a node act as separators between the ranges represented by its children.

For example, consider a node containing three keys:

[20 | 40 | 70]

These separators divide possible search values into four ranges:

child 0: values less than 20
child 1: values from 20 up to, but less than, 40
child 2: values from 40 up to, but less than, 70
child 3: values greater than or equal to 70

The exact treatment of values equal to a separator depends on the implementation. Some implementations place equal values on one side, while others use a separate duplicate-key policy. The important idea is that the keys inside the node divide the key space into ordered ranges, and every child is responsible for one of those ranges.

A B-Tree therefore combines two kinds of ordering:

1. The keys inside each node are sorted.
2. Every child represents the key range associated with the separators around it.

This lets a search skip large portions of the tree. Instead of following one binary decision at every node, the search compares a target with several keys in the current node and then chooses the one child whose range can contain the target.

2. The shape of a B-Tree​

A B-Tree consists of nodes connected in a hierarchy. Each node contains:

• A sequence of keys in sorted order.
• References to child nodes when the node is internal.
• Structural information that identifies whether the node is a leaf.

A small B-Tree might look like this:

                 [40 | 80]
                /    |    \\
       [10 | 25]  [55 | 65]  [95 | 110]

The root contains two separator keys, so it has three child ranges:

• The first child contains values less than 40.
• The second child contains values between 40 and 80.
• The third child contains values greater than 80.

The child nodes in this example are leaves. They contain keys but no children below them.

A larger B-Tree can have more keys per node and many more children. The same pattern still applies: every internal node uses sorted separator keys to direct searches toward the correct child.

The name “B-Tree” refers to a family of balanced multiway search trees. Implementations can differ in details such as the maximum number of keys in a node, the minimum occupancy rules, and how duplicate keys are handled. The central properties remain the same:

• Nodes hold multiple ordered keys.
• Children are ordered by key ranges.
• Nodes have bounded capacity.
• Leaves remain at the same depth.

The tree is not required to have the same number of keys in every node. Instead, each node must stay within the capacity and occupancy limits defined by the particular B-Tree variant.

3. Core invariants​

An invariant is a condition that must remain true before and after an operation. The power of a B-Tree comes from preserving a small set of structural invariants.

3.1 Keys inside a node are sorted​

If a node contains several keys, those keys must appear in ascending order:

[12 | 29 | 61 | 90]

Sorted keys make it possible to decide which range contains a search target. If the keys were unordered, the node would not provide a reliable guide.

When a new key is inserted into a node, it must be placed at the correct position rather than appended arbitrarily. If 45 is inserted into [10 | 30 | 60], the result is:

[10 | 30 | 45 | 60]

The ordering inside the node is preserved.

3.2 Children follow key ranges​

For a node containing keys k1, k2, and k3, its children divide the value space into four ranges:

child 0: values less than k1
child 1: values between k1 and k2
child 2: values between k2 and k3
child 3: values greater than k3

The implementation must apply a consistent rule for equality and duplicate values. What matters is that a value is directed to the appropriate range and that the rule does not contradict the ordering of the node.

For example, in this node:

[40 | 80]

A value such as 25 belongs in the first child range, 60 belongs in the middle range, and 100 belongs in the final range.

3.3 Nodes have bounded capacity​

A B-Tree does not allow a node to grow without limit. Each particular configuration defines a maximum number of keys or children a node can contain. When an insertion would exceed that capacity, the node must be split.

The capacity limit is essential. It keeps the tree organized into manageable nodes and ensures that an insertion cannot simply create an indefinitely large node.

The split operation replaces one overfull node with two nodes and moves a separator into the parent. This creates additional room while preserving the ordering relationship between the affected ranges.

3.4 Nodes follow occupancy rules​

B-Tree variants normally also define a minimum number of keys or children for non-root nodes. These rules prevent most nodes from becoming nearly empty and help keep the structure compact.

The root is often treated specially. It may be allowed to contain fewer keys than ordinary internal nodes, especially when the tree is small. The exact occupancy thresholds depend on the chosen order or degree of the tree, so a general explanation should distinguish the invariant from a particular implementation’s numerical rules.

The essential point is that nodes must not be arbitrarily full or arbitrarily empty. The capacity and occupancy rules work together to control the shape of the tree.

3.5 All leaves have the same depth​

This is the defining balance property. Every leaf is located at the same distance from the root.

Consider this valid shape:

                 [50]
                /    \\
          [20 | 35]  [70 | 90]

Both leaves are at depth one below the root. A shape in which one leaf were deeper than another would violate the B-Tree balance invariant.

Because all leaves remain at the same depth, searches do not encounter a long chain on one side and a short path on the other. Updates must preserve this balance rather than allowing the tree to become uneven.

4. Why multiple keys per node matter​

A B-Tree stores several keys together. This changes the tree’s shape compared with a binary search tree.

A node containing several keys can direct a search to several children. Each level can therefore divide the possible key space into many ranges. As a result, a large number of keys can be represented with relatively few levels.

A binary tree has a branching factor of at most two. A B-Tree can have a much larger branching factor. The exact branching factor is determined by node capacity, but the general relationship is what matters: more children per node usually means fewer levels for the same number of stored keys.

This is particularly relevant to database indexing. A database index must guide searches through a potentially large collection of ordered keys. A B-Tree provides a compact hierarchy in which each visited node supplies several comparisons and chooses a narrower range.

The benefit is not that a B-Tree eliminates comparisons. It organizes them so that each level makes substantial progress toward the target. The search moves from a broad range at the root to a smaller range at each child and eventually reaches a leaf.

A useful mental model is a set of nested range decisions. The root divides the entire key space into broad regions. A child then divides its own region into smaller regions. This continues until the search reaches a leaf that contains the final, narrow range.

5. Searching a B-Tree​

Searching begins at the root. At each node, the algorithm compares the target key with the keys stored in that node.

There are three possible outcomes:

1. The target matches a key in the current node.
2. The target is not present in the current node, but its possible range identifies a child to visit.
3. The current node is a leaf, so the target is not present in the tree.

For example, search for 65 in this tree:

                 [40 | 80]
                /    |    \\
       [10 | 25]  [55 | 65]  [95 | 110]

The search starts at [40 | 80]. The target 65 is greater than 40 and less than 80, so the search follows the middle child. In [55 | 65], it finds 65.

Now search for 60:

1. At [40 | 80], choose the middle child because 60 lies between 40 and 80.
2. At [55 | 65], determine that 60 lies between the stored keys.
3. Because this node is a leaf and does not contain 60, report that the key is absent.

The search does not inspect unrelated branches. Once the correct range has been selected at a node, the remaining ranges can be ignored.

5.1 Search pseudocode​

A simplified search procedure looks like this:

search(node, target):
    find the first key in node that is greater than or equal to target

    if that key equals target:
        return found

    if node is a leaf:
        return not found

    follow the child immediately before that key

If the target is greater than every key in the node, the final child is selected. The phrase “immediately before that key” describes the child whose range lies to the left of the first greater key. An implementation must handle the final-child case separately when the target exceeds every key in the node.

An implementation can scan the keys in a node from left to right. It can also use another method to locate the appropriate position among the keys. The structural algorithm is unchanged: locate the target or select the child representing the target’s range.

5.2 Search complexity​

Let h be the height of the B-Tree. A search visits at most one path from the root to a leaf, so the number of visited levels is proportional to h.

Within each visited node, the algorithm must locate the target’s position among that node’s keys. The total cost can therefore be described in terms of both tree height and the work used to search within a node.

The important structural fact is that the height remains logarithmic when the tree maintains its balance and bounded node capacity. Because each internal node can direct a search to multiple children, the tree can represent many keys without requiring many levels.

For database indexes, this height-focused view explains why B-Trees are attractive: an index lookup follows a bounded, balanced route through the index rather than scanning every key.

6. Inserting a key​

Insertion must add a new key while preserving every B-Tree invariant. A general insertion process is:

1. Start at the root.
2. Use the node’s sorted keys to choose the child range that should contain the new key.
3. Continue until reaching the appropriate leaf.
4. Insert the key into that leaf in sorted order.
5. If the node becomes too full, split it and promote a separator toward the parent.
6. Continue handling overflow as necessary.

The critical operation is the split. Without splitting, a node that reaches its capacity would violate the maximum-size rule.

6.1 Inserting into a leaf without overflow​

Consider a leaf containing:

[10 | 30 | 60]

If the node has room for another key and we insert 45, the result is:

[10 | 30 | 45 | 60]

The keys remain sorted, and the tree’s height and child relationships do not change.

If the leaf is part of a larger tree, the insertion path is selected by comparing the new key with the separators in each ancestor. The new key belongs in exactly one leaf range according to the tree’s ordering rules.

6.2 Inserting into the correct leaf​

Use this tree as an example:

                 [40 | 80]
                /    |    \\
       [10 | 25]  [55 | 65]  [95 | 110]

To insert 35:

• Compare 35 with 40 and 80 at the root.
• Since 35 is less than 40, follow the left child.
• Insert 35 into [10 | 25] in sorted order.

The leaf becomes:

[10 | 25 | 35]

Assuming this is within the node’s capacity, no split is needed.

To insert 75:

• At the root, 75 lies between 40 and 80.
• Follow the middle child.
• Insert it into [55 | 65].

The result is:

[55 | 65 | 75]

Again, the tree remains balanced because only the contents of an existing leaf changed.

7. Splitting a full node​

A split occurs when a node receives a key but exceeds its maximum capacity. The overflowing set of keys is divided into two nodes, and one separator key is moved upward into the parent.

For a simple illustration, suppose a node is temporarily allowed to contain this overflowing sequence:

[10 | 20 | 30 | 40 | 50]

A split may choose 30 as the separator. The keys on either side become two nodes:

left node:   [10 | 20]
separator:        30
right node:  [40 | 50]

The parent receives 30 as a new separator, with the left and right nodes taking the place of the original node.

The separator is not merely a copied label without meaning. It represents the boundary between the two resulting ranges. Values belonging to the left range remain in the left node, and values belonging to the right range remain in the right node.

7.1 Splitting a leaf​

Suppose the middle leaf in this tree is full:

                 [40 | 80]
                /    |    \\
              ...  [55 | 65 | 75]  ...

Insert 70, creating an overflowing sequence:

[55 | 65 | 70 | 75]

For illustration, choose 70 as the separator. The leaf is divided into two leaves:

left leaf:   [55 | 65]
separator:        70
right leaf:       [75]

The parent changes from:

[40 | 80]

to something like:

[40 | 70 | 80]

Its children now include the two leaves created by the split:

                 [40 | 70 | 80]
              /       |       |       \\
            ...   [55 | 65]  [75]     ...

The exact division and separator convention depend on the implementation. The essential operations are always the same: divide the overflowing node, place a separator in the parent, and reconnect the children in their correct key ranges.

7.2 Splitting an internal node​

A split can happen in an internal node, not only in a leaf. Internal nodes contain both keys and child references, so their children must be divided consistently with the key split.

Suppose an internal node has an overflowing key sequence:

[20 | 40 | 60 | 80 | 100]

It also has child subtrees arranged around those keys. If 60 is promoted, the lower keys and their corresponding child ranges form the left internal node:

left internal node:  [20 | 40]

The higher keys and their corresponding child ranges form the right internal node:

right internal node: [80 | 100]

The promoted 60 becomes a separator in the parent. The child references must be divided so that every subtree remains under the correct key range.

This is why a split is a structural operation, not just an array resize. It changes the node set, the parent’s separator keys, and the connections among child subtrees.

8. Split propagation toward the root​

A split may create an overflow in the parent. When a child splits, the parent receives a new separator key. If the parent is already full, adding that separator can make the parent overflow as well.

The repair process then continues upward:

1. Split the overflowing child.
2. Insert the child’s separator into the parent.
3. If the parent now fits, stop.
4. If the parent overflows, split the parent and promote another separator.
5. Continue toward the root if necessary.

This is called split propagation because one insertion can cause a chain of splits along the path back toward the root.

A simplified sequence looks like this:

leaf overflows
    ↓
parent receives a separator
    ↓
parent overflows
    ↓
parent splits and sends a separator upward

The operation still affects only the search path for the inserted key and the ancestors that need repair. It does not require rebuilding every node in the tree.

9. Root splitting and tree growth​

The root is special because it has no parent. If the root overflows, there is no existing node above it to receive the promoted separator. The solution is to create a new root.

Before the split:

[10 | 20 | 30 | 40 | 50]

After choosing 30 as the promoted separator:

                 [30]
                /    \\
          [10 | 20] [40 | 50]

The old root becomes two children of the new root. The height of the tree increases by one, but the leaves remain at the same depth because both resulting branches are created at once.

This is a central feature of B-Tree growth. The tree becomes taller only when the root must split. Ordinary splits below the root may widen the tree without increasing its height.

The root-split operation preserves balance:

• The new root is at the top.
• Its child subtrees come from the same old root.
• Existing leaves remain aligned beneath the new level.

10. A complete insertion example​

Start with a small tree:

                 [40 | 80]
                /    |    \\
       [10 | 25]  [55 | 65]  [95 | 110]

Assume, for illustration, that a leaf can hold only a limited number of keys. Insert 70.

Step 1: Find the target leaf​

At the root, 70 lies between 40 and 80, so follow the middle child.

Step 2: Insert in sorted order​

The middle leaf changes from:

[55 | 65]

to:

[55 | 65 | 70]

If this is still within capacity, the operation ends.

Now suppose instead that the node was already:

[55 | 65 | 75]

Inserting 70 produces:

[55 | 65 | 70 | 75]

If that exceeds capacity, the node must split.

Step 3: Split the overflowing leaf​

Choose 70 as the separator for this illustration:

left leaf:   [55 | 65]
separator:        70
right leaf:       [75]

Step 4: Update the parent​

The root originally contained:

[40 | 80]

It receives 70 and now contains:

[40 | 70 | 80]

The parent’s children are updated so that the new leaves occupy the ranges between the separators.

Step 5: Check the parent​

If the root can hold the new separator, the insertion is complete. If the root is also full, split the root and create a new root.

This example shows the key pattern: descend, insert, split if necessary, promote a separator, and continue upward only when required.

11. Why B-Trees are used for database indexing​

A database index needs to organize keys so that a search can quickly identify the relevant portion of the indexed data. B-Trees are chosen as a foundation for indexing because their structure supports efficient search while remaining updateable through insertion and splitting.

11.1 Balanced search paths​

All leaves have the same depth. A search therefore follows a path whose length is governed by the tree’s height rather than by an unlucky sequence of insertions that creates a long one-sided chain.

Balance is valuable for a database index because the index must continue to provide predictable navigation as keys are added.

11.2 High branching factor​

Each internal node can contain multiple keys and direct the search to multiple children. This allows the tree to represent many ordered keys with relatively few levels.

A small height means that a lookup performs its navigation through a limited number of hierarchical decisions. The tree does not need one separate level for every individual key.

11.3 Local structural updates​

When a node becomes full, the B-Tree does not need to be rebuilt from scratch. It splits the affected node and updates its parent. If necessary, the repair continues up the insertion path.

This makes the structure suitable for a changing index. New keys can be incorporated while preserving ordering and balance.

11.4 Ordered keys​

The keys in a B-Tree remain sorted within nodes, and the child ranges remain ordered. This ordered organization is the foundation of index navigation. The index can distinguish lower, middle, and higher ranges at every level.

11.5 A stable invariant set​

A database index is useful only if its structure remains correct after updates. B-Tree invariants give insertion a clear correctness target:

• Keep node keys sorted.
• Keep children aligned with key ranges.
• Keep nodes within their capacity and occupancy rules.
• Keep all leaves at the same depth.

The search operation relies on exactly these conditions. If an update breaks one of them, later searches could be directed to the wrong subtree or miss a key.

12. Height and complexity​

Let n be the number of keys and let the tree have a bounded height h. A search follows one root-to-leaf path, so its structural cost is proportional to the height plus the work required to locate a position within each visited node.

Insertion has the same downward navigation cost as search, followed by possible splitting on the way upward. In the worst case, a split can propagate from a leaf to the root, so the repair work is also related to the tree height.

Because B-Trees are balanced and each internal node can have multiple children, the height grows logarithmically with the number of stored keys under the usual B-Tree occupancy conditions. The base of that logarithm is related to the tree’s branching factor. A larger branching factor generally permits fewer levels for the same number of keys.

A useful summary is:

• Search: proportional to the tree height, plus in-node key-location work.
• Insert without split: search cost plus insertion into the target node.
• Insert with splits: search cost plus split propagation along part or all of the path to the root.
• Root split: increases the height by one while preserving equal leaf depth.

The precise constant factors depend on node capacity, the strategy used to locate a key within a node, and implementation details. The core reason for the logarithmic height is the combination of bounded node capacity, sufficient occupancy, and balance.

13. Common misconceptions​

13.1 A B-Tree is not a binary tree​

The letter “B” does not mean that each node has two children. A B-Tree is a multiway search tree. A node may contain multiple keys and have several children.

13.2 A split does not mean the whole tree is divided in half​

A node split is local. The overflowing node is divided into two nodes, and a separator is promoted to its parent. Only if the root splits does the tree gain a new level.

13.3 Balance does not mean every node has the same number of keys​

The important balance condition is that all leaves have the same depth. Nodes may contain different numbers of keys as long as they satisfy the capacity and occupancy rules of the particular B-Tree variant.

13.4 Searching does not visit every key​

A B-Tree uses the ordering of node keys and child ranges to choose one path. It does not need to inspect every branch for a single-key lookup.

13.5 Insertion is more than placing a value in a leaf​

The new key is first inserted into the correct leaf, but that may cause a split. The split can modify the parent and may propagate toward the root. Correct insertion is therefore a path-based update with possible structural repair.

14. Implementation checklist​

When implementing or reviewing a B-Tree, check the following points.

Node representation​

A node needs an ordered collection of keys. An internal node also needs child references arranged so that each child corresponds to the range between neighboring separator keys.

Capacity definition​

Define the maximum number of keys or children clearly. The split condition depends on this limit.

Occupancy definition​

Define the minimum occupancy rules for non-root nodes. Do not assume that every B-Tree variant uses exactly the same threshold.

Search position​

The search procedure must correctly locate the first key greater than or equal to the target, or determine that the target belongs after all keys. This position identifies either a matching key or the child to follow.

Leaf insertion​

Insert the key into sorted order. If the key already exists, apply a documented duplicate-key policy rather than silently violating the representation.

Leaf split​

Divide an overflowing leaf into two ordered nodes and promote the appropriate separator to the parent. Preserve the ordering of the resulting ranges.

Internal split​

When splitting an internal node, divide both its keys and its child references. A key separator without correctly divided child ranges is not a valid B-Tree update.

Parent update​

After a child split, insert the promoted separator and the new child reference into the parent at the correct position.

Root split​

If the root overflows, create a new root and make the split pieces its children. Verify that all leaves remain at the same depth.

Invariant testing​

After operations, test that:

• Keys in every node are sorted.
• Child ranges agree with separator keys.
• No node exceeds capacity.
• Occupancy rules are respected.
• Every leaf has the same depth.

15. A practical mental model​

A useful way to think about a B-Tree is as a sequence of sorted range decisions.

At the root, the tree divides the entire key space into broad regions. At the next level, each selected child divides its region into smaller regions. This continues until a leaf is reached.

Insertion follows the same route as search because the new key must belong to the leaf representing its range. A split changes the range map locally: one range becomes two ranges, and the parent receives a new boundary that tells future searches how to distinguish them.

The parent separator is therefore the tree’s way of recording a new decision point. If the parent cannot hold that decision point, the parent itself is divided and another decision point is passed upward. Root splitting creates a new top-level decision point when the old root can no longer contain all of its separators.

This mental model helps explain why B-Tree operations remain understandable even when the nodes contain many keys. The algorithm repeatedly maintains sorted ranges and repairs overflow by introducing additional separators.

16. Practical takeaways​

The most important lessons are these:

1. A B-Tree is a balanced multiway search tree.
2. Each node stores multiple sorted keys.
3. Separator keys divide the key space among child subtrees.
4. Search descends through the one child whose range can contain the target.
5. Insertion first reaches the correct leaf and inserts the new key in sorted order.
6. A full node is repaired by splitting it into two nodes and promoting a separator to the parent.
7. A split can propagate upward when the parent also becomes full.
8. A full root is split by creating a new root, which increases the height by one.
9. All leaves remain at the same depth, preserving balance.
10. The combination of balance, multiple keys per node, ordered ranges, and local split-based updates explains why B-Trees are chosen for database indexing.

Conclusion​

B-Trees provide a structured solution to the problem of indexing ordered data. Their nodes hold multiple keys, their children represent precise key ranges, and their leaves remain at the same depth. These invariants make search systematic: compare within the current node, choose the correct range, and continue downward.

Insertion preserves the same structure through a controlled sequence of updates. The new key is placed in its target leaf. If the leaf becomes too full, it is split, and a separator is promoted to the parent. That separator may cause another split, potentially reaching the root. When the root splits, a new level is created without sacrificing equal leaf depth.

The result is a balanced index whose height grows slowly as keys are added. B-Trees therefore combine efficient navigation with practical update operations, making them a foundational tree structure for database indexing.