B+ Tree Index

Overview

The B+ Tree is the most widely used index structure in relational databases. It’s a variant of the B-Tree optimized for disk-based storage and range queries. MySQL InnoDB, PostgreSQL, Oracle, and SQL Server all use B+ Trees as their primary index structure.

Key differences from B-Tree:

• Data only in leaf nodes (internal nodes only hold keys for routing)
• Leaves are linked (forming a sorted linked list for range queries)
• All leaves at the same level (guaranteed balance)

Structure

Internal Nodes

Internal nodes contain keys and pointers to children. They do NOT contain data records.

Internal Node: [K1 | K2 | K3]
  Pointer P0: subtree with keys < K1
  Pointer P1: subtree with K1 <= keys < K2
  Pointer P2: subtree with K2 <= keys < K3
  Pointer P3: subtree with keys >= K3

Leaf Nodes

Leaf nodes contain keys and pointers to data records (or the data itself). Leaves are linked together.

Leaf Node: [K1:ptr1 | K2:ptr2 | K3:ptr3]
  → next leaf pointer
  Each ptr points to a record in the table (or contains the data)

Mermaid Diagram: B+ Tree Structure

graph TD
    subgraph "Internal Nodes"
        R["[40 | 70]"]
        I1["[10 | 20 | 30]"]
        I2["[50 | 60]"]
        I3["[80 | 90]"]
    end
    
    subgraph "Leaf Nodes (Linked)"
        L1["5:ptr | 10:ptr | 15:ptr"]
        L2["20:ptr | 25:ptr | 30:ptr"]
        L3["35:ptr | 40:ptr"]
        L4["45:ptr | 50:ptr | 55:ptr"]
        L5["60:ptr | 65:ptr | 70:ptr"]
        L6["75:ptr | 80:ptr"]
        L7["85:ptr | 90:ptr | 95:ptr"]
    end
    
    R --> I1
    R --> I2
    R --> I3
    
    I1 --> L1
    I1 --> L2
    I1 --> L3
    I2 --> L4
    I2 --> L5
    I3 --> L6
    I3 --> L7
    
    L1 -.->|next| L2
    L2 -.->|next| L3
    L3 -.->|next| L4
    L4 -.->|next| L5
    L5 -.->|next| L6
    L6 -.->|next| L7
    
    style R fill:#e3f2fd
    style I1 fill:#e3f2fd
    style I2 fill:#e3f2fd
    style I3 fill:#e3f2fd
    style L1 fill:#d4edda
    style L2 fill:#d4edda
    style L3 fill:#d4edda
    style L4 fill:#d4edda
    style L5 fill:#d4edda
    style L6 fill:#d4edda
    style L7 fill:#d4edda

Properties

Operations

Point Query (Search)

Search(key):
  1. Start at root
  2. At each internal node:
     - Find the child pointer for the key's range
     - Follow the pointer to the next level
  3. At leaf node:
     - Search for the key
     - Return the data pointer

Time: O(log_m n) disk reads

Range Query

This is where B+ Trees shine. The leaf chain allows efficient scanning of ranges.

RangeQuery(low, high):
  1. Search for low key → find starting leaf
  2. Scan leaf nodes following next pointers
  3. Continue until key > high

Time: O(log_m n) for initial seek + O(k/m) for scanning
  where k = number of records in range

Mermaid Diagram: Range Query

flowchart LR
    subgraph "Range: 25 to 65"
        A["Search for 25"] --> B["Found in leaf: [20|25|30]"]
        B --> C["Scan: 25 ✓"]
        C --> D["Follow next → [35|40]"]
        D --> E["Scan: 35 ✓, 40 ✓"]
        E --> F["Follow next → [45|50|55]"]
        F --> G["Scan: 45 ✓, 50 ✓, 55 ✓"]
        G --> H["Follow next → [60|65|70]"]
        H --> I["Scan: 60 ✓, 65 ✓"]
        I --> J["Stop: 70 > 65"]
    end
    
    style A fill:#e3f2fd
    style J fill:#d4edda

Insertion

Insert(key):
  1. Find appropriate leaf node L
  2. Insert key into L in sorted order
  3. If L overflows:
     a. Split L into L1 and L2
     b. Copy middle key up to parent (not move — key stays in leaf)
     c. Update leaf chain pointers
     d. If parent overflows, split parent recursively
     e. If root splits, create new root

Key Difference: Copy Up vs Push Up

In B+ Trees, when splitting a leaf, the middle key is copied up to the parent (the key remains in the leaf). In B-Trees, the middle key is pushed up (moved out of the leaf).

B+ Tree leaf split (insert 25 into [10, 20, 30, 40]):
  Before: [10, 20, 30, 40]
  After insert: [10, 20, 25, 30, 40]
  Split: [10, 20] | 25 | [25, 30, 40]
  Copy 25 up to parent
  Leaf still contains 25

B-Tree leaf split (same scenario):
  Push 25 up to parent
  Leaf no longer contains 25

Deletion

Delete(key):
  1. Find key in leaf node L
  2. Remove key from L
  3. If L underflows:
     a. Try to borrow from sibling (redistribute keys)
     b. If sibling also minimal, merge with sibling
     c. Remove corresponding key from parent
     d. If parent underflows, rebalance recursively

Comparison: B+ Tree vs Other Structures

Disk Page Optimization

Fill Factor

The fill factor determines what percentage of each page is filled with data:

Fill factor 100%: Pages fully packed
  - Pros: Maximum space utilization
  - Cons: Immediate splits on insert

Fill factor 70%: Pages 70% full
  - Pros: Room for inserts without splitting
  - Cons: Wastes 30% space

PostgreSQL: CREATE INDEX ... WITH (fillfactor = 70);

Prefix Compression

For indexes with long, similar keys (e.g., URLs), prefix compression stores only the distinguishing prefix:

Without compression:
  "https://www.example.com/page1"
  "https://www.example.com/page2"
  "https://www.example.com/page3"

With prefix compression:
  "https://www.example.com/page" (common prefix stored once)
  "1" (suffix)
  "2" (suffix)
  "3" (suffix)

PostgreSQL B+ Tree Implementation

PostgreSQL’s B-Tree index implementation (which is actually a B+ Tree):

-- Create B-Tree index (default)
CREATE INDEX idx_users_email ON users(email);

-- With specific options
CREATE INDEX idx_users_email ON users(email)
  WITH (fillfactor = 90, deduplicate_items = on);

-- Check index structure
SELECT * FROM bt_metap('idx_users_email');
SELECT * FROM bt_page_stats('idx_users_email', 1);

Deduplication (PostgreSQL 13+)

PostgreSQL 13 introduced B-Tree deduplication, which merges duplicate keys into a single posting list:

Before deduplication:
  Key "alice" → [(page1, tuple1), (page2, tuple3), (page5, tuple2)]

After deduplication:
  Key "alice" → posting list [(1,1), (2,3), (5,2)]
  (Compressed representation)

Interview Questions

Beginner

Q1: What is a B+ Tree? A: A B+ Tree is a balanced tree where data records are stored only in leaf nodes, and internal nodes contain only keys for routing. Leaf nodes are linked together for efficient range queries.

Q2: How is a B+ Tree different from a B-Tree? A: In a B+ Tree, data is only in leaves (internal nodes are routing-only), and leaves are linked. In a B-Tree, data is in all nodes and leaves aren’t linked. B+ Trees are better for range queries and disk-based storage.

Q3: Why are B+ Trees good for range queries? A: Because leaf nodes are linked in a sorted chain. Once you find the starting point, you can scan sequentially through the leaves without going back up the tree.

Intermediate

Q4: What is the difference between “copy up” and “push up” during a B+ Tree split? A: Copy up: the middle key is copied to the parent but remains in the leaf. Push up: the middle key is moved to the parent and removed from the leaf. B+ Trees use copy up; B-Trees use push up.

Q5: What is the height of a B+ Tree with 1 billion records and order 100? A: h = ⌈log_100(1,000,000,000)⌉ = ⌈4.5⌉ = 5. This means at most 5 disk reads for any lookup.

Q6: How does PostgreSQL handle duplicate keys in B+ Tree indexes? A: PostgreSQL uses posting lists — multiple row pointers for the same key are stored together. Since version 13, deduplication merges these into a compressed posting list, significantly reducing space for low-cardinality columns.

Advanced / FAANG-Level

Q7: Design a B+ Tree that supports both forward and backward range scans. A: Maintain doubly-linked leaf nodes (both next and prev pointers). During splits and merges, update both pointers. PostgreSQL’s B-Tree implementation supports this — you can scan in both directions using the leaf chain.

Q8: A B+ Tree index on a timestamp column grows to 10GB. Queries are slow despite using the index. How do you optimize? A: (1) Check if the index is being used: EXPLAIN ANALYZE. (2) If returning many rows, consider partitioning the table by time range. (3) Use BRIN (Block Range Index) instead for naturally ordered data — much smaller. (4) Consider partial index if queries always filter by a recent time range. (5) If the index is fragmented, REINDEX.

Q9: How would you implement a B+ Tree that handles variable-length keys efficiently? A: (1) Use prefix compression to store common prefixes once. (2) Use suffix truncation — store only the minimum prefix needed for routing in internal nodes. (3) Use indirect keys — store a hash or short representation in internal nodes, full key in leaf. (4) PostgreSQL uses suffix truncation since version 13, which can significantly reduce internal node sizes.

Q10: Compare B+ Tree with LSM Tree for a database that needs both fast reads and fast writes. A: B+ Tree: Fast reads (O(log n)), slower writes (random I/O for updates). LSM Tree: Fast writes (sequential I/O), slower reads (multiple levels to check). For mixed workloads: (1) Use B+ Tree for read-heavy tables; (2) Use LSM for write-heavy tables (e.g., logs, time-series); (3) Consider using both — B+ Tree for primary index, LSM for secondary indexes. PostgreSQL uses B+ Trees; Cassandra/RocksDB use LSM Trees.

Common Mistakes

1. Not understanding that B+ Trees store data only in leaves — Internal nodes are routing structures only. This is why range queries work (scan leaves, not internal nodes).

2. Ignoring the leaf chain — The linked list of leaves is crucial for range queries. Without it, range queries would require traversing the tree for each key.

3. Using wrong fill factor — 100% fill factor causes immediate splits on random inserts. Use 70-90% for insert-heavy workloads.

4. Not considering index-only scans — If the index contains all columns needed, PostgreSQL can answer the query from the index alone. Design indexes to support this.

5. Creating too many B+ Tree indexes — Each index is a separate B+ Tree. Too many indexes slow down writes and consume storage. Choose indexes based on query patterns.

Summary

Cross-References

• B-Tree — The base structure B+ Tree extends
• Hash Index — Alternative for exact lookups
• Clustered vs Non-Clustered — How B+ Trees implement clustered indexes
• Covering Index — B+ Tree indexes that contain all needed columns
• Composite Index — Multi-column B+ Tree indexes
• Index Tuning — How to optimize B+ Tree indexes

Cross References

• B-Tree
• Buffer Pool
• Disk Scheduling (OS)
• File Organization
• SSD