When you run a simple SELECT * FROM users WHERE email = 'test@example.com', response times feel instantaneous. But behind the scenes, the database engine executes a deeply optimized search operation. If it had to scan every row sequentially (a full table scan), performance would degrade linearly as data grows.
The Magic of B-Trees
Most relational databases (such as PostgreSQL and MySQL) use a self-balancing search tree data structure known as a B-Tree (or B+Tree variant) for their indexing subsystem. A B-Tree maintains sorted keys and enables logarithmic time operations for lookups, insertions, and sequential traversals.
CREATE INDEX idx_users_email ON users(email);
-- This constructs a B-Tree structure where the keys are sorted emails
-- and the values are tuples containing pointers to physical disk blocks (TID/ROWID).When an index is defined on the email column, the storage manager extracts column values, orders them, and constructs the tree topology. The search commences at the root page, evaluates target keys against node boundaries, and descends down appropriate child branches until landing at the target leaf node containing the tuple pointer.
Why Not Hash Maps Everywhere?
Hash maps provide constant time O(1) lookups, which theoretically outpaces a B-Tree's O(log n) performance. Why do general-purpose engines default to B-Trees?
- Range Queries: Hash indexes cannot service range scan operations efficiently (e.g.
WHERE created_at > '2026-01-01'). B-Trees natively handle sequential range scans because leaf nodes form a doubly linked list. - Prefix Matches & Sorting: Prefix pattern searches like
WHERE name LIKE 'Sm%'leverage sorted key order in B-Trees, whereas hash buckets offer zero ordering guarantees.