How Database Indexes Actually Work — A Visual Deep Dive

Every developer has written CREATE INDEX at some point. Most know it “makes queries faster.” But few actually understand why — or when an index makes things worse.

This post tears the black box open. We’ll walk through the data structures, the math, the tradeoffs, and the real-world decisions that separate someone who guesses at indexing from someone who knows.

The Problem: Why We Need Indexes

Imagine a users table with 10 million rows. You run:

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

Without an index, PostgreSQL does a sequential scan — it reads every single row, checks the email column, and returns matches. That’s 10 million comparisons for a single lookup.

The time complexity? $O(n)$ — linear. Double your data, double your query time.

With a B-Tree index on email, that same query does $O(\log n)$ comparisons. For 10 million rows, that’s roughly:

$$\log_2(10{,}000{,}000) \approx 23 \text{ comparisons}$$

Twenty-three. Not ten million. Twenty-three.

B-Tree: The Workhorse

95% of the indexes you’ll ever create are B-Tree indexes¹. They’re the default in PostgreSQL, MySQL, and SQLite.

A B-Tree is a self-balancing tree where:

• Every node can hold multiple keys (not just one like a binary tree)
• All leaf nodes are at the same depth
• Data is sorted, so range queries are efficient

Structure

Loading diagram...

When you search for email = 'kushagra@example.com':

1. Start at root — is “kushagra” before or after the keys?
2. Follow the correct pointer down one level
3. Repeat until you hit a leaf node
4. The leaf contains a pointer to the actual row on disk

Each level eliminates a large fraction of the remaining data. With a branching factor of $b$, the height of the tree is:

$$h = \lceil \log_b(n) \rceil$$

For $b = 100$ (typical for PostgreSQL) and $n = 10{,}000{,}000$:

$$h = \lceil \log_{100}(10{,}000{,}000) \rceil = \lceil 3.5 \rceil = 4$$

Four disk reads. That’s it.

Hash Indexes: The Specialist

Hash indexes use a hash function to map keys directly to row locations. The lookup is $O(1)$ — constant time, regardless of table size.

Sounds better than B-Trees, right? So why aren’t they the default?

Hash indexes are only useful for exact equality on high-cardinality columns — like UUIDs or API keys. For everything else, B-Trees win.

-- Hash index: only good for exact matches
CREATE INDEX idx_api_keys_hash ON api_keys USING hash (key);

-- B-Tree: the default, handles everything
CREATE INDEX idx_users_email ON users (email);

Composite Indexes: Order Matters

A composite index covers multiple columns. But the column order is critical.

CREATE INDEX idx_posts_status_date ON posts (published, created_at);

This index is useful for:

-- ✅ Uses index (leftmost prefix)
SELECT * FROM posts WHERE published = true;

-- ✅ Uses index (both columns, left to right)
SELECT * FROM posts WHERE published = true AND created_at > '2024-01-01';

-- ❌ Cannot use index (skips the first column)
SELECT * FROM posts WHERE created_at > '2024-01-01';

This is called the leftmost prefix rule. Think of a composite index like a phone book sorted by last name, then first name. You can look up “Sharma” efficiently. You can look up “Sharma, Kushagra” efficiently. But you cannot look up just “Kushagra” — the book isn’t sorted that way.

When to Use Composite Indexes

Loading diagram...

The Cost of Indexes

Indexes aren’t free. Every index you add:

1. Slows down writes — every INSERT, UPDATE, and DELETE must also update the index
2. Uses disk space — an index on a text column can be 30-50% the size of the table
3. Requires maintenance — VACUUM and REINDEX become necessary as data changes

The write penalty per index is roughly:

$$T_{write} = T_{table} + \sum_{i=1}^{k} T_{index_i}$$

Where $k$ is the number of indexes. Five indexes on a table means every insert does six writes (one for the table, five for indexes).

A Real-World Example

Here’s a schema I recently indexed for a portfolio site:

// Drizzle ORM — adding indexes to a posts table
export const posts = pgTable("posts", {
  id: text("id").primaryKey(),
  userId: text("user_id").notNull(),
  username: text("username").notNull(),
  title: text("title").notNull(),
  slug: text("slug").notNull().unique(),
  published: boolean("published").notNull(),
  trashed: boolean("trashed").notNull().default(false),
  createdAt: timestamp("created_at").defaultNow().notNull(),
}, (table) => [
  index("posts_published_idx").on(table.published),
  index("posts_user_id_idx").on(table.userId),
  index("posts_username_idx").on(table.username),
  index("posts_created_at_idx").on(table.createdAt),
]);

Four indexes. Every public query filters on published and trashed. User profile pages filter on username. Listing pages sort by created_at. Each index serves a specific query pattern — nothing speculative.

Partial Indexes: The Secret Weapon

Most tutorials skip this one. A partial index only indexes rows that match a condition:

CREATE INDEX idx_posts_published ON posts (created_at)
WHERE published = true AND trashed = false;

This index is smaller, faster to update, and only covers the rows you actually query. If 90% of your queries are for published, non-trashed posts, this index is perfect — and it’s a fraction of the size of a full index.

Loading diagram...

For a table with 1,000 posts where 850 are published, the partial index is 85% the size — or more accurately, it only contains the 850 rows that matter.

Measuring Impact

Theory is nice. Numbers are better. Here’s how to actually measure whether your index helps:

-- Before: check the query plan
EXPLAIN (ANALYZE, BUFFERS) 
SELECT * FROM posts 
WHERE published = true 
ORDER BY created_at DESC 
LIMIT 20;

-- Look for:
-- Seq Scan         → bad (reading whole table)
-- Index Scan       → good (using your index)
-- Bitmap Index Scan → okay (using index, then heap)
-- Index Only Scan  → best (data is in the index itself)

Key metrics to watch:

• Seq Scan → Index Scan: query is using the index
• actual time: real execution time in milliseconds
• Buffers: shared hit: pages read from cache (lower = better)
• Buffers: shared read: pages read from disk (this is the slow part)

Rules of Thumb

After years of indexing production databases, here’s what I’ve learned:

1. Index what you WHERE, JOIN, and ORDER BY — not what you SELECT
2. The leftmost prefix rule is non-negotiable — always query from left to right
3. Partial indexes are underused — if you always filter on a condition, make it partial
4. Covering indexes eliminate heap lookups — include all selected columns with INCLUDE
5. EXPLAIN ANALYZE is your best friend — never guess, always measure
6. Monitor pg_stat_user_indexes — delete indexes with idx_scan = 0

Conclusion

Indexes aren’t magic. They’re B-Trees — balanced, sorted, pointer-based data structures that trade write speed for read speed. Understanding how they work gives you the ability to make informed decisions instead of cargo-culting CREATE INDEX and hoping for the best.

The next time you add an index, ask yourself:

• What queries does this serve?
• Is the column selective enough?
• Would a partial index be better?
• Am I willing to pay the write cost?

If you can answer all four, you’re not guessing anymore. You know.

Want more deep dives like this? Subscribe to my newsletter – I write about systems, performance, and the things they don’t teach you in tutorials.