B+ TREES
WITH EXAMPLE
Introduction to Balanced Tree Data
Structures
WHAT IS A B+
TREE?
A B+ tree is a self-balancing tree data structure that
maintains sorted data and allows efficient insertion,
deletion, and search operations. It is widely used in
databases and file systems for indexing.
Key characteristics:
• Extension of B-trees with all values stored exclusively in
leaf nodes
• Internal nodes contain only keys to guide search
operations
• Provides efficient range queries due to linked leaf
structure
• Maintains logarithmic time complexity for all operations
• Optimized for systems that read and write large blocks
of data
STRUCTURE OF
A B+ TREE
A B+ tree consists of internal nodes and leaf
nodes arranged in a balanced hierarchy. Internal
nodes contain only keys that guide the search
process, while leaf nodes store the actual data
pointers. All leaf nodes are connected via a linked
list, enabling efficient sequential access and
range queries. This structure ensures optimal
performance for both point lookups and range
scans.
KEY TERMINOLOGY
AND PROPERTIES
Order (m): Maximum number of children per
internal node, defining tree capacity.
Internal Nodes: Contain up to m-1 keys that guide
search operations to appropriate subtrees.
Leaf Nodes: Store keys paired with pointers to
actual data records in the database.
Balanced Depth: All leaf nodes exist at the same
level, ensuring consistent search performance.
Linked Leaves: Leaf nodes connected via linked
list enabling efficient sequential access and
range scans.
B+ TREE VS B-TREE
B-Tree:
• Stores keys and data in all nodes
• Leaves are not linked together
• Lower fanout per node
• Data accessible at any level
B+ Tree:
• Stores data only in leaf nodes
• Leaves linked for range queries
• Higher fanout→ shorter trees
• Sequential access via leaf links
INSERTION IN
B+ TREES
[Link] the correct leaf node for the new key
[Link] the key in sorted order within the leaf
[Link] the leaf overflows (exceeds capacity), split
the leaf node
[Link] the middle key upward to the
parent node
[Link] node splits may cascade upwards to
maintain balance
This process ensures the tree remains balanced
after every insertion operation.
SEARCHING IN
B+ TREES
The search operation in B+ trees is highly efficient
due to the balanced structure. Starting at the root
node, the algorithm compares the search key with
stored keys to determine which child pointer to
follow. This process continues through internal
nodes until reaching a leaf node containing the
actual data pointers. The balanced height ensures
all searches traverse the same number of levels,
while high fanout means fewer levels overall. This
guarantees logarithmic time complexity O(log n)
for all search operations, making B+ trees ideal for
database indexing.
EXAMPLE OF
Leaf
Left child
Root
Root A B+ TREE
B+ tree with order 4 (max 4 children per node)
5, 6
Step-by-step insertion of keys: 10, 20, 5, 6, 12
• Insert 10, 20: Single leaf node [5, 10, 20]
Right child
10 →
• Insert 5, 6: Leaf splits keys redistribute
• Insert 12: Causes leaf overflow and key
promotion
10, 12, 20
Node splits propagate middle key to parent,
maintaining balance throughout the tree
structure.
Source: AI-generated data. Replace or verify before use.
ADVANTAGES
OF B+ TREES
• High fanout reduces tree height → faster
searches
• Efficient range queries via linked leaf nodes
• Balanced structure ensures logarithmic time
operations
• Widely used in databases and file systems for
indexing
• Optimal for disk-based storage systems
QUESTIONS?
THANK YOU