indexing • Intermediate

B+ Tree Indexes & Leaf Page Traversals

B+ Trees are balanced multi-way search trees used by PostgreSQL, MySQL (InnoDB), and SQLite to provide O(log N) point lookups and efficient sequential range scans.

Intuitive Mental Model

The Multi-Tier Library Directory: Wall signs point to corridors (Root), aisle signs point to bookshelves (Branch), and the bookshelf lists titles alphabetically with doubly linked bookmarks to adjacent shelves (Leaf pages).

SQL DDL / DML QueryPostgreSQL / MySQL

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

-- Point Lookup (O(log N)):
SELECT * FROM users WHERE email = 'alex@example.com';

-- Range Scan (Navigates to first leaf, then traverses linked list):
SELECT * FROM users WHERE created_at BETWEEN '2026-01-01' AND '2026-06-01';

Key Architectural Takeaways

•All user data pointers reside strictly in Leaf pages; Internal Branch nodes only store routing search keys.
•Leaf pages are linked with bidirectional pointers (prev/next), making range queries (BETWEEN, >=) blazingly fast without re-traversing the root.
•Shallow height: A B+ Tree with order 100 and height 3 can index 1,000,000+ records in just 3 disk page reads.

Common Production Mistake

Applying functions to indexed columns (e.g. WHERE LOWER(email) = "alex@test.com"), disabling the B+ Tree index.