What is an Index & Why Do Databases Search So Fast?

What You Will Master in This Lesson:

The foundational pillar of high-performance database engineering:

Full Table Scan vs Index Seek: Why linear $O(N)$ searches fail on 100M rows
B-Tree & B+Tree Architecture: Why wide fan-out and page block matching defeat BSTs
Storage Pages & Buffer Pool: How in-memory caches make index traversals instantaneous
Range & ORDER BY: Eliminating sorting computational costs with pre-ordered leaf chains
Composite Indexes & Prefix Rule: The telephone directory analogy and column ordering
The Write Penalty & Selectivity: Hidden storage overhead and trade-offs

1 What is an Index? Analogy vs Database Reality

In straightforward terms: An Index is an auxiliary, specialized data structure maintained alongside the main table, designed to locate specific records rapidly without scanning the entire dataset.

The classical conceptual analogy is the index at the back of a 1,000-page textbook. Suppose you need to read about "Transaction". You do not start reading line-by-line from page 1. Instead, you flip directly to the alphabetical index at the back:

Database ................... Page 245
Index ...................... Page 411
SQL ........................ Page 520
Transaction ................ Page 680

The index gives you an immediate pointer to Page 680. The core philosophy of a database index is identical: help the engine jump straight to the exact storage page of the target record without scanning irrelevant data.

Critical Technical Distinction: Table vs Index

An index is NOT a clone or duplicate copy of the entire table. The actual table rows reside in physical data pages (often called the Table Heap). The index stores only (indexed column value + physical row address/pointer or Primary Key). As a result, the index structure is remarkably compact and can frequently fit entirely within RAM.

2 Full Table Scan vs Index Seek

Consider a production users table containing 10,000,000 (10 million) rows:

id	name	email	created_at
1	Salim	salim@example.com	2026-01-10
2	Rahim	rahim@example.com	2026-01-11
...	...	...	...
10000000	Zayed	zayed@example.com	2026-09-22

Scenario 1: No Index Present (Full Table Scan)

When we execute our query:

SELECT * FROM users WHERE email = 'salim@example.com';

Without an index on email, the storage engine must open every single physical storage page from disk and inspect all 10,000,000 rows row-by-row. This is known as a Full Table Scan (Sequential Scan).

Time Complexity: $O(N)$ — Doubling rows doubles scan time.
Disk I/O Cost: Assuming 50 rows per 16KB disk page, the engine must pull 200,000 disk pages into memory (over 3.2 GB of raw disk read!).
Production Impact: Query latency spikes from milliseconds to tens of seconds, bottlenecking server CPU and I/O threads.

Scenario 2: With an Index (Index Seek)

Now we create an index:

CREATE INDEX idx_users_email ON users(email);

The database engine constructs a balanced tree (B+Tree) ordered by email. When the query executes, the engine traverses directly to the target record:

SQL Query Query Optimizer Email B+Tree Index Target Leaf & Page ID Row Returned (1.2 ms!)

Time Complexity: $O(\log N)$ — A tree indexing 10M rows has a height of only 3 to 4 node levels.
Disk I/O Cost: At most 3 to 4 page reads (and since root nodes reside in RAM, often just 1 single physical disk read!).

3 B-Trees & B+Trees: Why Binary Search Trees Fail on Disk

In classic algorithms courses, we learn about Binary Search Trees (BST), AVL trees, and Red-Black Trees. A natural question arises: why do enterprise databases ignore BSTs in favor of B-Trees and B+Trees?

The Binary Search Tree Disk Problem

Narrow Fan-out ($b = 2$): Each node has only 2 children. For 100M items, tree height reaches $\log_2(100,000,000) \approx 27$ levels!
Severe Disk Latency: Reading a disk block takes milliseconds. Traversing 27 levels with random disk seeks takes $27 \times 5\text{ms} = 135\text{ms}$ on mechanical storage.
Block Waste: Disks read in 4KB to 16KB blocks. Loading a 16KB disk page just to read a tiny 32-byte BST node wastes 99.8% of I/O bandwidth.

The B+Tree Disk Superiority

Massive Fan-out ($b = 100 \text{ to } 500+$): A single 16KB page stores hundreds of keys and child pointers.
Remarkably Shallow Tree (Height = 3 to 4): Even with 100,000,000 records, the tree is only 3 to 4 levels deep!
Native Disk Page Alignment: Each node size is engineered to match the database page size (8KB in PostgreSQL, 16KB in MySQL InnoDB).

How Does B+Tree Architecture Work?

Modern relational engines (PostgreSQL, MySQL InnoDB, SQLite) standardize on the B+Tree variant. A B+Tree exhibits two critical design characteristics:

Internal Nodes Store Routing Keys Only

The root and internal branches contain no table row data. They store only discriminator keys and child page pointers. This allows internal nodes to pack hundreds of keys per page, keeping the entire tree shallow.

Leaf Nodes Form a Bidirectional Linked List

All actual data pointers reside exclusively at the lowest Leaf Nodes. Crucially, each leaf node contains pointers to its immediate left and right neighbor leaves. For range scans such as WHERE id BETWEEN 50 AND 150, the engine does not backtrack up the tree—it navigates horizontally across the linked leaves!

# B+Tree Physical Layout:

                   [ 50 | 100 ]                      <-- Root Page (Always in RAM Buffer Pool)
                  /     |      \
        [ 20 | 35 ]  [ 70 | 85 ]  [ 120 | 150 ]      <-- Internal Routing Pages
        /    |   \   /    |    \   /     |    \
     [Leaf1] <---> [Leaf2] <---> [Leaf3] <---> [Leaf4] <-- Doubly Linked Leaves (Range Scans)
       ↓             ↓             ↓             ↓
    [Data]        [Data]        [Data]        [Data]  <-- Table Rows on Disk

4 Storage Pages, Buffer Pool & ORDER BY Optimizations

Understanding database performance requires understanding how memory and storage interact.

1. Storage Pages and the Buffer Pool

Disks and SSDs do not transfer individual bytes; they transfer data in fixed units called Pages (typically 4KB, 8KB in PostgreSQL, or 16KB in MySQL InnoDB).

Databases reserve a large portion of system RAM for the Buffer Pool. Because the root page of a B+Tree is tiny (16KB), it permanently resides in RAM. When executing an index seek, the root and internal branch hops occur in-memory at nanosecond speeds. Only the terminal leaf page or heap table row may require physical disk access.

2. Range Queries

Indexes are not limited to equality checks (=). Because B+Tree leaves are sorted and linked, range queries execute with incredible efficiency:

SELECT * FROM products WHERE price BETWEEN 5000 AND 10000;

The engine traverses the tree once to find the first product priced at 5,000, and then sweeps horizontally along the leaf chain until it exceeds 10,000.

3. Eliminating Sort Costs in ORDER BY

Consider an ordered query:

SELECT * FROM products ORDER BY price LIMIT 20;

Without an index on price, the database must pull millions of rows into temporary memory or disk storage to execute a computational sort (such as External Merge Sort). With a B+Tree on price, the records are already physically sorted. The database reads the first 20 entries directly off the index—reducing sorting computational cost to zero!

5 When Does the Database Ignore an Index?

A common developer misconception is: "I created an index, so the database will definitely use it." — This is false.

The database's Cost-Based Optimizer (CBO) calculates the estimated cost (disk I/O and CPU cycles) of all execution paths. If a sequential scan is calculated to be cheaper than an index lookup, the engine deliberately ignores the index.

1. Small Tables (< 100-500 Rows)

If the entire table fits within one or two memory pages, scanning it sequentially in RAM is faster than traversing index pages and dereferencing row pointers.

2. Low Selectivity

If a query condition matches 30% to 80% of total table rows (e.g. WHERE is_active = true where 95% of users are active), random I/O pointer jumps are slower than a single continuous sequential block read.

3. Functions Wrapping Indexed Columns

Writing WHERE LOWER(email) = '...' invalidates standard indexes on email because the tree stores raw casing. An Expression/Functional Index is required instead.

4. Leading Wildcard Predicates (%)

Writing WHERE email LIKE '%gmail.com' renders the B+Tree useless because the search prefix is unknown. The engine must fall back to a full scan.

6 Primary Key, Clustered vs Secondary Indexes

Not all indexes store physical rows the same way.

1. Clustered Index (Primary Index)

In storage engines like MySQL InnoDB or SQL Server, the Primary Key forms the Clustered Index. This means: the actual table row data is physically stored directly inside the B+Tree's leaf pages! A table can have only one Clustered Index because data can only be physically ordered on disk in one arrangement.

2. Secondary Index (Non-Clustered Index)

Any index you explicitly create on non-PK columns (e.g. CREATE INDEX idx_users_email ON users(email);) is a Secondary Index. Leaf nodes do not contain full row data; they store the indexed column value plus a reference to the Primary Key.

The 2-Hop Secondary Lookup (Bookmark Lookup):
1. Search Email B+Tree to retrieve the Primary Key (e.g., id = 42).
2. Search Primary Key B+Tree to retrieve the full table row.

3. Unique Index

Defining a UNIQUE(email) constraint automatically generates a unique index. This guarantees both data integrity (preventing duplicate registrations at the storage level) and lightning-fast point lookups.

7 Composite Indexes & The Leftmost Prefix Rule

Real-world production queries frequently filter by multiple attributes simultaneously:

SELECT * FROM orders WHERE customer_id = 10 AND status = 'completed';

Rather than building two independent single-column indexes, we can define a Composite (Multi-Column) Index:

CREATE INDEX idx_orders_cust_status ON orders(customer_id, status);

The Telephone Directory & Leftmost Prefix Rule

Column order inside a composite index is crucial. The database sorts entries primarily by the first column (customer_id), and then within identical customer IDs, sorts by the second column (status).

Think of a traditional Telephone Directory organized by (Last Name, First Name):

Query Filter Predicate	Index Used?	Explanation
WHERE customer_id = 10 AND status = 'completed'	Full Index Seek	Both columns matched in exact leading order. Maximum efficiency.
WHERE customer_id = 10	Partial Index Seek	Leftmost prefix column is present. Equivalent to looking up all "Khan"s in a phonebook.
WHERE status = 'completed'	Failed (Full Table Scan)	Prefix skipped! Looking for first name "Salim" without a last name requires reading the entire book.

8 Selectivity & Cardinality: Deciding What to Index

Database engineers examine two statistical properties before creating an index:

1. Cardinality

The total count of distinct (unique) values in a column. In a 10M row table, email has cardinality ~10,000,000. In contrast, gender has a cardinality of 2 or 3.

2. Selectivity

Selectivity is defined as: $\text{Selectivity} = \frac{\text{Distinct Values}}{\text{Total Rows}}$. Values close to $1.0$ indicate High Selectivity. Values close to $0.0$ indicate Low Selectivity.

The Golden Rule of Indexing: High-selectivity columns (e.g. email, uuid, phone_number) are prime candidates for B+Tree indexing. Low-selectivity columns (e.g. boolean flags, gender) should rarely be indexed alone as the optimizer will ignore them in favor of sequential scans.

9 The Dark Side of Indexing: The Write Penalty & Storage Overhead

Beginner engineers often ask: "If indexes speed up searches so dramatically, why not index every single column?"

This is a classic anti-pattern because: Indexes are never free.

Storage Amplification

Every index generates an independent physical B+Tree on disk. Indexing 6 columns on a 10 GB table can swell total storage consumption to 25 GB or more!

The Write Penalty

Whenever a row is inserted (INSERT), updated (UPDATE), or removed (DELETE), the database cannot simply touch the table—it must traverse and update every single index tree, perform B-Tree Page Splits, and log WAL records. Having 5 indexes turns 1 row insert into 6 distinct write operations!

Core Engineering Trade-Off

Index = Faster READS ⚡ vs Slower WRITES ⏳ & Higher Storage 💾

10 EXPLAIN: Inspecting How the Database Runs Queries

Senior engineers never guess query execution performance. By prefixing a query with EXPLAIN or EXPLAIN ANALYZE, you inspect the exact plan chosen by the query planner:

Danger: Seq Scan (Missing Index) Cost: 38,450.00

EXPLAIN SELECT * FROM users WHERE email = 'salim@example.com';

-> Seq Scan on users (cost=0.00..38450.00 rows=1 width=84)
Filter: (email = 'salim@example.com'::text)
Rows Removed by Filter: 9999999

Success: Index Scan (B+Tree Active) Cost: 8.44

EXPLAIN SELECT * FROM users WHERE email = 'salim@example.com';

-> Index Scan using idx_users_email on users (cost=0.42..8.44 rows=1 width=84)
Index Cond: (email = 'salim@example.com'::text)

Hands-On Laboratory

B+Tree & Indexing Interactive Lab

Use the tabs below to simulate linear scanning vs B+Tree seeks across 1,000,000 records.

1,000,000 (1 Million) Rows Dataset Search

Looking for: email = 'salim@example.com' (located at Row #781,420)

Full Table Scan (No Index) Idle

Rows Examined 0 / 1,000,000

Disk Pages Read 0 pages

Data Read from Disk 0 MB

Elapsed Time 0 ms

B+Tree Index Seek (With Index) Idle

Tree Hops (Height) 3 levels

Disk Pages Read 1 page (rest in RAM)

Data Read from Disk 16 KB

Elapsed Time 1.1 ms

Self-Assessment

Knowledge Check: Indexing & B+Trees

Validate your understanding by choosing the correct answers below:

1. Why do database storage engines prefer B+Trees over standard Binary Search Trees (BST)?

2. A table has a Composite Index on `(country_id, city, postal_code)`. Which query CANNOT use this index for a direct seek and will fall back to a Full Table Scan?

3. When will a Cost-Based Optimizer deliberately choose a Full Table Scan even though an index is present?

Key Takeaways

Index: An auxiliary balanced tree structure mapping indexed values to physical row pointers, turning $O(N)$ table scans into $O(\log N)$ seeks.
B+Tree Superiority: High fan-out (100-500 keys/page), shallow 3-4 level height, and linked leaf nodes deliver optimal performance on block-based disk storage.
Leftmost Prefix Rule: To utilize a composite index, the query's WHERE clause must include the leading (leftmost) column of the index definition.
The Write Penalty: Indexes accelerate reads at the cost of slower INSERT, UPDATE, and DELETE operations due to multiple B-Tree rebalances and WAL logs.
EXPLAIN: When debugging slow queries, use EXPLAIN or EXPLAIN ANALYZE to verify whether the engine is using Index Scan or falling back to Seq Scan.