Page 6: B+ Tree Fundamentals

What is a B+ Tree?

A B+ tree is like a perfectly balanced multi-level index where:

• All data is stored in leaf nodes (bottom level)

• Internal nodes contain only keys to guide searches

• All leaf nodes are at the same level

• Leaf nodes are linked together

Structure Example (Order 3 B+ Tree)

Copy                    [10, 20]
                   /    |    \
              [5,6]   [10,12]  [20,30]
              /       /     \      \
    [5][6]  [10][12] [17] [20][30] [35]

Components:

• Root: [10, 20] - guides searches

• Internal nodes: [5,6], [10,12], [20,30] - more guides

• Leaf nodes: [5][6], [10][12][17], [20][30][35] - actual data

B+ Tree Properties (Order n)

• Each node has at most n children

• Each node (except root) has at least ⌈n/2⌉ children

• All leaves are at the same level

• Leaves contain the actual records or pointers to records

Searching in B+ Tree

Example: Find key 17 in the tree above

1. Start at root [10, 20]

   • 17 > 10 and 17 < 20, so go to middle child

2. Reach internal node [10, 12]

   • 17 > 12, so go to rightmost child

3. Reach leaf containing [17]

   • Found the record!

Search Path: Root → Internal → Leaf (always same number of steps)

Range Queries

Example: Find all keys between 10 and 25

1. Search for 10 → leads to leaf with [10][12][17]

2. Follow leaf pointers: [10][12][17] → [20][30][35]

3. Collect values: 10, 12, 17, 20 (stop when > 25)

Insertion Process

Case 1: Simple Insertion Insert 11 into leaf [10][12][17] with space: Result: [10][11][12][17]

Case 2: Leaf Split Insert 13 into full leaf [10][11][12] (max 3 entries):

1. Split into [10][11] and [12][13]

2. Promote middle key (12) to parent

3. Parent becomes [10, 12, 20]

Case 3: Internal Node Split If parent is also full, split propagates upward, possibly creating new root.

Worked Example: Building B+ Tree (Order 3)

Insert sequence: 10, 20, 5, 6, 12, 30, 7, 17

Step 1: Insert 10, 20

Copy[10, 20]

Step 2: Insert 5

Copy[5, 10, 20]

Step 3: Insert 6 (causes split)

Copy       [10]
      /    \
  [5, 6]  [10, 20]

Step 4: Insert 12, 30 (right leaf splits)

Copy         [10, 20]
        /    |    \
   [5, 6] [10, 12] [20, 30]

Step 5: Insert 7, 17

Copy         [10, 20]  
        /    |    \
  [5, 6, 7] [10, 12, 17] [20, 30]

Advantages of B+ Trees

• Balanced: All searches take same time

• Efficient: Good for both point and range queries

• Dynamic: Handles insertions/deletions well

• Sequential access: Linked leaves enable fast scanning