B Tree vs B+ Tree: Key Differences and When to Use Each

A B tree stores keys and data in all its nodes, while a B+ tree stores data only in its leaf nodes and uses internal nodes just for indexing. This makes B+ trees more efficient for range queries and sequential access compared to B trees.

Quick Comparison

Here is a quick side-by-side comparison of B tree and B+ tree based on key factors.

Factor	B Tree	B+ Tree
Data Storage	Keys and data stored in all nodes	Data stored only in leaf nodes; internal nodes store keys only
Leaf Nodes	Leaf nodes are not linked	Leaf nodes are linked for sequential access
Search Efficiency	Search may end at any node	Search always ends at leaf nodes
Range Queries	Less efficient due to scattered data	More efficient due to linked leaves
Tree Height	Generally shorter	May be taller due to data only in leaves
Use Case	General indexing where updates are frequent	Databases and file systems optimized for range queries

Key Differences

B trees store both keys and their associated data in every node, including internal and leaf nodes. This means that searching for a key can stop as soon as the key is found in any node. In contrast, B+ trees store only keys in internal nodes and keep all actual data in the leaf nodes. This design means searches always go down to the leaves.

Another important difference is that B+ trees link their leaf nodes together in a linked list, which allows for very efficient range queries and ordered traversal. B trees do not have this linked structure, so range queries require more complex navigation.

Because B+ trees store data only in leaves, their internal nodes can hold more keys, potentially increasing the tree's fan-out but also making the tree taller. B trees tend to be shorter since data is spread across all nodes. These structural differences affect performance depending on the use case.

Code Comparison

Below is a simple Python example showing how a B tree node might store keys and data together and perform a search.

python

class BTreeNode:
    def __init__(self, keys=None, data=None, children=None, leaf=True):
        self.keys = keys or []
        self.data = data or []  # Data stored with keys
        self.children = children or []
        self.leaf = leaf

    def search(self, key):
        i = 0
        while i < len(self.keys) and key > self.keys[i]:
            i += 1
        if i < len(self.keys) and key == self.keys[i]:
            return self.data[i]  # Found key and data
        if self.leaf:
            return None
        return self.children[i].search(key)

# Example usage
root = BTreeNode(keys=[10, 20], data=['A', 'B'], leaf=True)
print(root.search(20))

Output

B

B+ Tree Equivalent

Here is a simplified Python example of a B+ tree leaf node storing data and internal nodes storing only keys for indexing.

python

class BPlusTreeNode:
    def __init__(self, keys=None, children=None, leaf=False, data=None, next_leaf=None):
        self.keys = keys or []
        self.children = children or []
        self.leaf = leaf
        self.data = data or []  # Only leaf nodes store data
        self.next_leaf = next_leaf  # Link to next leaf for range queries

    def search(self, key):
        if self.leaf:
            for i, k in enumerate(self.keys):
                if k == key:
                    return self.data[i]
            return None
        else:
            i = 0
            while i < len(self.keys) and key >= self.keys[i]:
                i += 1
            return self.children[i].search(key)

# Example leaf node
leaf = BPlusTreeNode(keys=[10, 20], data=['A', 'B'], leaf=True)
print(leaf.search(20))

Output

B

When to Use Which

Choose a B tree when you need a balanced tree that stores data in all nodes, which can be simpler for some update-heavy applications. It is suitable when you want faster access to data without always reaching leaf nodes.

Choose a B+ tree when your application requires efficient range queries or ordered traversal, such as in databases and file systems. The linked leaf nodes and data-only leaves make sequential access and scanning much faster.

In general, B+ trees are preferred in systems where read performance and range queries are critical, while B trees may be used in simpler indexing scenarios.

Key Takeaways

B trees store data in all nodes; B+ trees store data only in leaves.

B+ trees link leaf nodes for efficient range queries and sequential access.

B trees can be shorter and simpler for some update-heavy uses.

B+ trees are preferred for databases and file systems needing fast range scans.

Choose based on whether your priority is quick single-key access (B tree) or efficient range queries (B+ tree).