B+ Tree: The Real Database Index

A database index must do more than locate one value. It should also support ordered access and make it possible to retrieve related values efficiently and naturally. The B+ Tree is designed around those requirements.

Its defining rule is simple:

A B+ Tree stores the indexed data only in its leaf nodes.

The internal nodes contain navigation information. They divide the key space and direct a search toward the appropriate child. The leaves contain the actual indexed entries, and the leaves are connected in a chain. That chain lets a search move from one matching leaf entry to nearby entries in sorted order.

This organization explains why B+ Trees are strongly associated with database indexes. A lookup for one key can descend from the root to a leaf. A range query can locate its first matching leaf and then continue through the linked leaves. The structure combines hierarchical searching with sequential ordered access.

This article explains the shape of a B+ Tree, the roles of its internal and leaf nodes, the difference between a B+ Tree and a B-Tree, the importance of leaf chains, and the practical reasoning behind using B+ Trees for database indexing.

1. The indexing problem​

Imagine a table containing many records. One field, such as an identifier, is used frequently when searching for records. Without an index, a lookup may need to examine records one by one. An index changes the organization of the search: instead of starting with every record, the search uses a separate structure that narrows the possible location of the requested key.

A tree is a natural structure for this kind of navigation. The root provides the first division of the search space. Internal nodes provide additional divisions. Eventually, the search reaches a leaf that contains the relevant indexed entry or the position where that entry belongs.

The important design question is where the tree should store the actual data. One possible design stores data throughout the tree. Another separates navigation from data storage. A B+ Tree uses the second design:

• Internal nodes guide the search.
• Leaf nodes contain the indexed data.
• Leaf nodes are connected to neighboring leaves.
• The leaf chain follows key order.
• A range query can use the tree to find its starting point and the leaf chain to continue.

This separation is the central idea behind the structure. The upper levels answer a location question, while the bottom level provides the ordered data sequence.

2. The shape of a B+ Tree​

A B+ Tree has three important kinds of positions: the root, internal nodes, and leaf nodes. The root is the entry point for a search. Internal nodes contain separators and child references. Leaves are the final data-bearing level.

A simplified example looks like this:

                         [30 | 60]
                       /     |      \\
              [10 | 20]   [40 | 50]   [70 | 80]
                /   |   \\    / |  \\     /  |  \\
              L1   L2  L3   L4 L5 L6   L7  L8  L9
                ↔────↔────↔────↔────↔────↔────↔

The exact number of separators, children, and entries is only illustrative. The important structural ideas are:

1. The root contains separator information.
2. Internal nodes contain more separator information and child references.
3. The leaves contain the actual indexed entries.
4. The leaves form an ordered chain from left to right.

Suppose a search requests key 47. The root compares 47 with its separators. Because 47 lies between 30 and 60, the search chooses the middle branch. The next internal node narrows the choice further. Eventually, the search reaches the leaf whose key range contains 47.

The values shown in internal nodes are therefore not the primary destination of a search. They act as a map of the tree’s layout. Their job is to tell the search which direction to take.

3. Internal nodes are navigation structures​

The easiest way to understand an internal node is to think of it as a routing table inside the tree. Its separators describe the key ranges represented by its children.

For example, consider a node containing [30 | 60]:

                  [30 | 60]
                 /    |    \\
              below 30  30–59  60+

The exact boundary convention depends on the representation, but the basic purpose is stable. The first child represents lower keys, the middle child represents keys in the middle region, and the final child represents higher keys.

A lookup for 12 follows the left child. A lookup for 44 follows the middle child. A lookup for 91 follows the right child. Once the search enters the selected child, the same decision process is repeated.

This gives every descent step a clear purpose:

Which child can contain the requested key?

Internal nodes do not need to hold the final data record for a key. They only need enough separator information to direct the search. That makes their role consistent throughout the upper portion of the tree.

This consistency is especially useful when explaining B+ Trees. The upper levels do not mix two different tasks. They do not sometimes finish a lookup and sometimes route it onward. They are primarily navigation layers. The search is directed downward until it reaches the leaf level, where the indexed entries are stored.

4. Leaves contain the indexed data​

In a B+ Tree, leaves are the data-bearing level. A leaf might contain entries such as:

[10 → record A | 14 → record B | 18 → record C]

A neighboring leaf might contain:

[22 → record D | 27 → record E | 31 → record F]

The arrows in this example represent the association between an indexed key and its corresponding data or record reference. The important point is that these entries are in the leaves, not in the internal routing nodes.

This gives the structure a clean division of responsibility:

• The upper part of the tree answers, “Where should the search go?”
• The leaf level answers, “Which indexed entries are actually present?”

That division is the defining feature of the B+ Tree model described here. A B+ Tree is not merely a hierarchy of nodes. It is a navigation hierarchy above an ordered, connected data level.

Because the data is concentrated at the leaves, the final step of a lookup is easy to describe. The search follows separators until it reaches the leaf that represents the requested key range. It then checks the entries in that leaf.

5. How a point lookup works​

A point lookup asks for one particular key. Suppose the requested key is 47, and the upper part of the tree looks like this:

                         [30 | 60]
                       /     |      \\
              [10 | 20]   [40 | 50]   [70 | 80]
                /   |   \\    / |  \\     /  |  \\
              ...  ...  ...  ... ... ...  ... ...

The lookup proceeds conceptually as follows:

1. Start at the root.
2. Compare 47 with the root separators.
3. Since 47 is between 30 and 60, choose the middle child.
4. Compare 47 with the separators in that internal node.
5. Select the child whose key range can contain 47.
6. Continue until reaching a leaf.
7. Examine that leaf for the entry associated with 47.

The search does not need to inspect every leaf. The separator values eliminate branches whose ranges cannot contain the requested key. The tree hierarchy is a way of ruling out irrelevant regions before reaching the data-bearing level.

The important detail is that the search ends at a leaf in the B+ Tree organization. Even if a separator along the path resembles the requested key, that separator is being used as navigation information. The leaf contains the indexed entry that the lookup is trying to retrieve.

6. What happens when a key is absent?​

A B+ Tree can also guide a search for a key that does not exist. Suppose the search requests 26, but the relevant leaf contains:

[22, 24, 28, 31]

The tree still directs the search to this leaf because this is the region where 26 belongs. Inside the leaf, the entries show that 26 would fit between 24 and 28:

[22, 24, 28, 31]
        ^
    26 would fit here

This matters for more than reporting a failed exact lookup. It also provides a natural starting position for a range query. If a query asks for values beginning at 26, the search can reach the appropriate leaf and begin with the first entry at or after that boundary, such as 28.

The navigation hierarchy is therefore based on key ranges, not only on keys that are guaranteed to exist. Separators identify the region in which a key belongs.

7. The leaf chain​

The leaves of a B+ Tree are connected in key order. A simplified chain looks like this:

L1 ↔ L2 ↔ L3 ↔ L4 ↔ L5

If L2 contains smaller keys than L3, then moving from L2 to L3 continues the ordered sequence. The links may be shown as two-way arrows for illustration, but the essential idea is that a leaf provides a path to its neighboring leaf or leaves in the sequence.

The leaf chain is what gives a B+ Tree a second useful direction of movement. A point lookup primarily moves vertically through the hierarchy:

root → internal node → target leaf

A range query combines that vertical descent with horizontal movement:

root → first leaf → next leaf → next leaf → ...

The vertical path finds the starting region. The horizontal path continues through nearby values.

For example, consider these leaves:

L3: [35, 40, 42, 45]
L4: [50, 55, 61, 68]
L5: [72, 78, 84, 90]

For a query requesting keys from 42 through 78, the search first reaches L3. It returns 42 and 45, follows the link to L4, returns 50, 55, 61, and 68, then follows the link to L5 and returns 72 and 78. It stops once the upper boundary has been reached.

The tree hierarchy is used to find the beginning. The leaf chain is used to continue in order.

8. Range queries​

A range query asks for every indexed value within a boundary. Examples include:

• keys greater than or equal to 100;
• keys between 20 and 40;
• keys less than 500;
• keys from A through M.

A B+ Tree handles a range query in two broad phases.

Phase one: find the starting leaf​

The search begins at the root and follows internal separators until it reaches the leaf containing the first possible matching key. If the range begins at 20, the tree locates the leaf where 20 would appear, whether or not 20 is present exactly.

Phase two: follow the leaf chain​

The query reads matching entries from the starting leaf. If the upper boundary extends beyond that leaf, it follows the link to the next leaf and continues. It repeats this process until the range ends.

This is more natural than treating every result as an independent point lookup. The first descent establishes the starting location, and the linked leaves provide the continuation path.

Consider the following sequence:

L1: [2, 5, 9]
L2: [12, 15, 19]
L3: [23, 27, 29]
L4: [34, 38, 41]
L5: [46, 50, 55]

For the range 15 through 41, the process is:

1. Search down the tree for the position of 15.
2. Begin at L2.
3. Return 15 and 19.
4. Follow the link to L3 and return 23, 27, and 29.
5. Follow the link to L4 and return 34, 38, and 41 if the upper boundary is inclusive.
6. Stop once the next entry would exceed the requested range.

The leaves are already organized in key order, so the query does not need to reconstruct that order while scanning.

9. B+ Trees compared with B-Trees​

The principal difference between B-Trees and B+ Trees is where data is stored.

A B-Tree can store data in internal nodes as well as in leaves. As a result, a search may find the requested data before reaching the bottom level. A B+ Tree stores data only in leaves. Its internal nodes contain navigation information, and its leaves contain the indexed entries.

The distinction can be summarized like this:

Both structures use internal nodes to organize a search. The difference is the division of duties. In a B+ Tree, internal nodes consistently act as routing structures, while the leaves consistently act as the data-bearing level.

This creates a simple operational model:

• To find one value, descend to the appropriate leaf.
• To find a range, descend to the first leaf and walk through neighboring leaves.

A B-Tree-style structure may encounter data at multiple levels. A B+ Tree keeps the indexed data in one connected level, which makes ordered leaf traversal an explicit part of the design.

10. Why data-only-in-leaves is useful​

Storing data only in leaves creates a uniform final layer. Every actual indexed entry appears at the leaf level rather than being distributed unpredictably across internal and leaf nodes.

That uniformity has several practical consequences:

• A lookup has a clear destination: a leaf.
• Internal nodes can focus on separators and child navigation.
• A range scan has a clear starting point.
• The leaf level represents the ordered sequence of indexed entries.
• Continuing a range scan means moving through neighboring leaves.

Suppose some records were stored in internal nodes and others were stored in leaves. A range scan would need to account for data encountered during the descent as well as data found in separate leaves. In a B+ Tree, the data-bearing path for the range is concentrated at the bottom.

The internal nodes are still essential. They make the initial search possible by narrowing the key space. The design simply gives the internal layer and the leaf layer different purposes:

internal nodes: navigate
leaf nodes: store and scan data

Once that division is understood, the structure is easier to visualize and explain.

11. A visual comparison​

The contrast can be shown with two simplified diagrams.

A B-Tree-style organization​

                         [30: data | 60]
                       /       |        \\
                 [10: data] [45: data] [75: data]

In this conceptual arrangement, data may appear in the root and in internal nodes. A search could potentially find a data entry at an internal level.

A B+ Tree-style organization​

                         [30 | 60]
                       /     |      \\
                    ...     ...     ...
                     |       |       |
              [10: data] [45: data] [75: data]
                    ↔────────↔────────↔

In the B+ Tree-style arrangement, the upper values guide the search, while the leaves contain the data. The leaf links create an ordered path between neighboring data-bearing nodes.

These diagrams are intentionally small. A real tree can have many entries in each node and many levels between the root and leaves. The essential difference remains the same: data placement and leaf connectivity define the B+ Tree’s database-oriented behavior.

12. B+ Tree invariants​

When reasoning about a B+ Tree, several structural rules should remain visible.

Invariant 1: internal nodes route searches​

An internal node must provide enough separator information to choose the child whose key range can contain the requested value. If the separators do not accurately describe the child ranges, a lookup may be directed to the wrong leaf.

Invariant 2: data entries live in leaves​

The indexed data belongs at the leaf level. Internal separators support navigation, but they are not the final data-bearing locations in the B+ Tree model described here.

Invariant 3: leaves follow key order​

The leaves form an ordered chain. Moving forward through the chain should move forward through the indexed key order. This is the property that allows a range query to continue after locating its first matching leaf.

Invariant 4: neighboring leaves are connected​

The leaf links connect neighboring leaves in the sequence. A missing or incorrect link would interrupt ordered traversal and could make a range scan incomplete or incorrect.

These rules show why a B+ Tree is more than a tree with additional pointers. Its useful behavior comes from the interaction between two structures:

1. a hierarchy that routes searches; and
2. an ordered leaf sequence that supports scanning.

13. A complete range-query walkthrough​

Consider a B+ Tree whose leaves contain the following ordered entries:

L1: [3, 7, 11]
L2: [15, 18, 21]
L3: [25, 29, 33]
L4: [37, 42, 48]
L5: [52, 59, 64]

Assume the leaf links are:

L1 ↔ L2 ↔ L3 ↔ L4 ↔ L5

Now consider the range query 18 through 52.

Step one: navigate to the first leaf​

The search begins at the root and follows separator values until it reaches L2, the leaf containing 18.

Step two: read the starting leaf​

Within L2, return 18 and 21. The value 15 is below the lower boundary and is not returned.

Step three: follow the next leaf​

The link from L2 leads to L3. Return 25, 29, and 33.

Step four: continue through the chain​

The link from L3 leads to L4. Return 37, 42, and 48.

Step five: process the boundary leaf​

The link from L4 leads to L5. Return 52 if the upper boundary is inclusive. Stop before 59, because it exceeds the range.

The result is:

[18, 21, 25, 29, 33, 37, 42, 48, 52]

The tree was needed to find L2. After that, the leaf chain supplied the ordered continuation. This is the operational meaning of the B+ Tree design.

14. Why databases favor B+ Trees​

The source description identifies the main reason directly: B+ Trees support the access patterns expected from database indexes. They place data in leaves, connect the leaves, and make range queries natural.

A database index commonly needs to support two broad tasks:

1. Locate one indexed value.
2. Retrieve a consecutive group of indexed values.

The B+ Tree handles both with one structure. Internal nodes narrow the search to the correct leaf. The linked leaves then support ordered continuation. A structure designed only around locating one isolated value would not automatically provide such a direct path for a range.

The appeal is therefore not based on one feature alone. It comes from the combination:

hierarchical navigation + ordered leaf chain

The hierarchy prevents the search from starting with an unrelated part of the data. The leaf chain prevents the range scan from having to rediscover each following value by restarting at the root.

This is why the B+ Tree is often described as the real database index structure. Its shape matches the two forms of access that an index must make understandable: targeted lookup and ordered traversal.

15. Point lookup and range scan side by side​

It is useful to compare the two operations directly.

Point lookup​

A point lookup for 47 follows this pattern:

root → separator decision → internal node → separator decision → leaf → 47

The search uses the hierarchy until it reaches the leaf that can contain 47.

Range scan​

A range query for 47 through 90 follows this pattern:

root → separator decisions → first leaf → next leaf → next leaf → stop at 90

The beginning is located through the hierarchy. The remainder is retrieved by following the ordered leaf chain.

This comparison highlights an important practical idea: a B+ Tree does not use exactly the same path for every kind of query. It uses the tree path for navigation and the leaf path for ordered continuation.

16. Common misunderstandings​

Misunderstanding 1: internal separator keys are the final data​

Internal keys may look like ordinary indexed values, but in the B+ Tree model they serve as separators. Their purpose is to guide navigation. The actual indexed data entries are stored in leaves.

Misunderstanding 2: finding a matching separator always ends the search​

A B-Tree may store data in an internal node, so a matching internal key can potentially identify the data directly. In a B+ Tree, the search proceeds to the appropriate leaf where the indexed data is stored.

Misunderstanding 3: leaf links are optional decoration​

The leaf chain is central to range queries. It gives a search a direct ordered path after the first leaf has been found.

Misunderstanding 4: a B+ Tree is only useful for exact lookups​

The linked leaves specifically support ordered continuation. This is why the structure is suitable for retrieving a range rather than only one isolated key.

Misunderstanding 5: the tree and leaf sequence are separate indexes​

They are two views of one structure. The upper tree supplies navigation, and the bottom-level chain supplies ordered access to the same indexed data.

Misunderstanding 6: the root alone contains enough information​

The root only makes the first routing decision. Deeper internal nodes continue narrowing the key range. The search must follow the complete path to the relevant leaf.

17. A practical way to draw a B+ Tree​

When learning or debugging a B+ Tree, draw it in two connected parts.

First, draw the routing hierarchy:

root → internal node → leaf

Then draw the leaf sequence separately:

leaf 1 ↔ leaf 2 ↔ leaf 3 ↔ leaf 4

Finally, connect the internal children to the leaves they represent. This prevents a common conceptual error: treating the vertical tree path as the only path through the structure.

For a point lookup, highlight the vertical route:

root → internal node → target leaf

For a range query, highlight both directions:

root → first leaf → next leaf → next leaf → ...

The vertical direction answers, “Where does the search begin?” The horizontal direction answers, “Where do the following ordered entries live?”

This drawing method is also useful for explaining the contrast with a B-Tree. In a B-Tree, data may be encountered at different levels. In a B+ Tree, the data-bearing level is visually concentrated at the leaves.

18. A compact mental model​

A B+ Tree can be remembered as a two-layer system.

The index directory​

The root and internal nodes act like a directory. They divide the key space and identify the route toward a particular leaf. They answer questions such as:

• Should the search move left, middle, or right?
• Which child represents the requested key range?
• Which leaf should contain the starting position for a range?

The ordered data row​

The leaves form an ordered chain containing the indexed entries. They provide the data-bearing layer and the natural path for scanning a range.

This mental model makes the difference from a B-Tree easier to remember. A B-Tree may place data in internal nodes and leaves. A B+ Tree separates the directory-like navigation layer from the data-bearing leaf layer.

Another concise model is:

The upper levels tell you where to look; the linked leaves let you keep reading in order.

19. Questions to ask when evaluating the structure​

When examining a tree index, ask these questions:

1. Where is the actual data stored?
2. What information do internal nodes provide?
3. Where does an exact lookup end?
4. How does a range query find its first matching entry?
5. How does it move to the next entry after the current leaf?
6. Are the leaves arranged in key order?
7. Are neighboring leaves connected?

For the B+ Tree described in this article, the answers are:

• Data is stored in leaves.
• Internal nodes provide navigation separators.
• A lookup reaches the appropriate leaf.
• A range query searches for its starting leaf.
• The query follows the leaf chain for continuation.
• The leaf sequence is ordered.
• Neighboring leaves are linked.

These answers describe the structure’s behavior without reducing it to a diagram or a name.

20. Practical takeaways​

When working with or explaining a B+ Tree, keep these points in mind:

1. Start every search at the root.
2. Treat internal nodes as routing information.
3. Expect the actual indexed entries at the leaves.
4. Use the leaf chain to explain range queries.
5. Compare B+ Trees with B-Trees primarily by data placement.
6. Draw both the vertical search path and the horizontal leaf path.
7. Think of the structure as a navigation hierarchy above an ordered data sequence.
8. For an absent key, locate the leaf where that key would belong.
9. For a range, find the first leaf once and continue through neighboring leaves.
10. Remember that the tree hierarchy and leaf chain work together rather than competing with each other.

21. Summary​

A B+ Tree is a tree structure organized for database indexing. Its defining ideas are straightforward but powerful:

• Data is stored only in leaf nodes.
• Internal nodes guide searches using separator information.
• A lookup descends through the hierarchy toward a leaf.
• The leaves are connected in an ordered chain.
• A range query finds its first leaf through the tree and then follows neighboring leaves.
• A B-Tree may store data in internal nodes, while a B+ Tree keeps data at the leaf level.
• Databases favor B+ Trees because the structure supports both individual lookups and ordered range access.

The most useful summary is this:

A B+ Tree uses its upper levels for navigation and its linked leaves for data and ordered scanning.

Once that division is clear, the shape and behavior of a B+ Tree become much easier to understand. A point lookup descends through the hierarchy until it reaches the correct leaf. A range query uses the same descent to find its beginning, then follows the leaf chain to retrieve neighboring values in order. That combination of hierarchical navigation and sequential leaf access is the reason B+ Trees are so closely associated with real database indexes.