Overview

I was in an interview. The question started simply enough: “How would you make this user search faster?”

I knew the answer. Add an index. I walked through it confidently — indexes avoid full table scans, they use B-Trees, lookups go from O(n) to O(log n). The interviewer nodded and kept going.

Then the question shifted: “What if the query filters by country, sorts by age, and searches across a range of signup dates — how do you design the index for that?”

I knew indexes used B-Trees. I had worked with MongoDB indexes for two years. I had even used PostgreSQL indexes at work. But the moment the question moved from “add an index” to “design the right compound index,” I hit a wall.

I did not know what value was actually stored in a B-Tree node. I had learned B-Trees and indexes as separate concepts that I had connected loosely. When the question required me to reason from the internals, that loose connection was not enough.

I got through the interview. But I went home and filled the gap properly. This post is what I learned — covering both MongoDB and PostgreSQL, from the basics through compound index design, the ESR Rule, and how the two databases implement the same structure differently in ways that matter in practice.

---

What Happens Without an Index

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

// MongoDB
db.users.find({ email: "dhyey@example.com" })

-- PostgreSQL
SELECT * FROM users WHERE email = 'dhyey@example.com';

Without an index, the database has no idea where this row lives. It reads the first row, checks if the email matches. It does not. Reads the second row. Checks. Continues until it either finds the match or reads all 10 million rows.

This is called a sequential scan (Postgres) or collection scan (MongoDB) — SEQSCAN and COLLSCAN in each database’s query planner output respectively. It is not a failure. It is the only option when there is no index. And it is slow enough to break your application at scale.

The mental model: finding a name in a phone book by reading every entry from page one. You will eventually find it. You will also be there all day.

---

What an Index Actually Is

An index is a separate data structure the database maintains alongside your table or collection. It maps field values to the physical location of rows on disk.

Instead of reading all 10 million rows, the database consults the index, finds the location of the matching row, and jumps there directly.

The mental model: the index at the back of a textbook. You do not read every page to find a term — you look it up in the index, get a page number, and jump there. The index is smaller than the book. Looking something up in it is fast.

Both MongoDB and PostgreSQL use the same underlying data structure for their standard indexes: the B-Tree.

---

The B-Tree: What Is Actually in the Node

This is the gap I had in the interview. I knew indexes used B-Trees. I did not know what was stored at each node.

A B-Tree is a sorted tree structure. Each internal node contains keys and pointers to child nodes — nothing else. Each leaf node contains the actual indexed value and a pointer to where the full row lives on disk.

For a MongoDB collection with a { age: 1 } index, a leaf node looks like:

{ value: 25, recordId: <pointer to document on disk> }

For PostgreSQL with an index on age, a leaf node contains:

{ key: 25, TID: (page_number, slot_number) }

TID stands for Tuple Identifier — Postgres’s way of pointing to a specific row in the heap (the table data on disk).

The internal nodes above the leaf level store copies of keys used purely for navigation — they tell the database which branch to follow to get closer to the target value. Internal nodes do not store pointers to actual rows. Only leaf nodes do.

This distinction matters when you get to the MongoDB vs PostgreSQL comparison later.

How a lookup works:

To find age: 25 in a collection of 10 million documents:

1. Start at the root — say it contains age: 5000
2. 25 is less than 5000 — follow the left pointer
3. Hit an internal node containing age: 100 — 25 is less — go left again
4. Hit a leaf node containing { value: 25, recordId: ... } — found it
5. Follow the recordId pointer to the actual document on disk

Four steps. Not 10 million. At 10 million documents, a B-Tree is only about 23 levels deep. You find any value in at most 23 comparisons. This is O(log n) in practice.

---

Why Range Queries Are Fast

Because the B-Tree is sorted, range queries work efficiently.

db.users.find({ age: { $gt: 25 } })

MongoDB finds the leaf node for `age: 25`, then **walks rightward** through the sorted leaves collecting 26, 27, 28, and so on. No scanning — sequential traversal of sorted data.

This is the key insight behind everything that follows: the B-Tree maintains sorted order, and sorted data can be read sequentially. Sequential reads are fast. Random reads are slow.

---

The Cost of Indexes

Indexes are not free.

The index is a separate file on disk. Every time you insert, update, or delete a row, the database must update both the table file and every index file for that table.

More indexes means slower writes. This is the core tradeoff: indexes speed up reads at the cost of write performance and disk space.

The practical rule: only create indexes on fields your actual query patterns use. An index nobody queries is pure write overhead.

---

Compound Indexes: One Tree, Multiple Fields

This is where the interview question became hard.

A compound index is a single B-Tree built on multiple fields together — not multiple separate trees. One tree, composite key.

// MongoDB
db.users.createIndex({ country: 1, age: 1, email: 1 })

-- PostgreSQL
CREATE INDEX idx_users_country_age_email ON users(country, age, email);

Each leaf node in this tree holds a composite key:

("IN", 22, "a@example.com")  →  recordId
("IN", 25, "dhyey@example.com")  →  recordId
("IN", 30, "b@example.com")  →  recordId
("US", 19, "c@example.com")  →  recordId
("US", 45, "d@example.com")  →  recordId

The tree is sorted first by country, then by age within each country, then by email within each age group. Age is not globally sorted — ("IN", 22) comes before ("US", 19) even though 19 is less than 22.

This single observation explains both the Prefix Rule and why compound index field order is not arbitrary.

---

The Prefix Rule

MongoDB and PostgreSQL both enforce a version of the Prefix Rule: a compound index can only be used if your query starts from the leftmost field and moves right without skipping.

Given the index (country, age, email):

db.users.find({ country: "IN" })
// Uses index — leftmost field

db.users.find({ country: "IN", age: 25 })
// Uses index — leftmost two fields

db.users.find({ age: 25 })
// Cannot use index — skipped country

db.users.find({ email: "dhyey@example.com" })
// Cannot use index — skipped country and age

Why does skipping break it?

Nodes are sorted by country first. If you query age: 25 without specifying country, the matching nodes — ("IN", 25), ("US", 25), ("UK", 25) — are scattered across the entire tree with no contiguous region to walk. The database falls back to a full scan. The index is useless for that query.

The Prefix Rule is not a database quirk. It follows directly from how the composite key tree is sorted.

---

The ESR Rule: Designing Compound Indexes That Actually Perform

Knowing what queries an index can serve is one thing. Knowing how to order fields for maximum performance is another. This is where the ESR Rule comes in.

ESR = Equality, Sort, Range

Position	Field Type	Example
First	Equality fields	WHERE status = 'active'
Middle	Sort fields	ORDER BY created_at DESC
Last	Range fields	WHERE amount > 1000

Why Equality First

Equality fields immediately carve the tree into the smallest possible subset. If your table has 1 million orders and 10,000 have status = 'active', specifying equality on status eliminates 990,000 rows in a single step. Everything else operates on 10,000 rows.

Why Sort in the Middle

Within the equality subset, the tree is already sorted by the next field. Results emerge pre-sorted — no extra work, no in-memory sort, no memory limits to worry about.

If sort fields come after range fields, the sort order breaks inside the range region and the database must sort results in memory after the index scan. It works. It is slower and in MongoDB hits a 32MB limit.

Why Range Last

Range fields span a region of the tree rather than a point. Once equality has narrowed scope and sort has established order, range does final filtering. Range before sort disrupts the pre-sorted property.

A Concrete Example

Query: orders where status is active, sorted by created_at descending, where amount is greater than 1000.

SELECT * FROM orders
WHERE status = 'active'
  AND amount > 1000
ORDER BY created_at DESC;

Wrong index — Range before Sort:

CREATE INDEX idx_wrong ON orders(status, amount, created_at DESC);

The database uses the index for status and amount, but within the matched range created_at is out of order. In-memory sort required. For large result sets this becomes expensive.

Correct ESR index:

CREATE INDEX idx_correct ON orders(status, created_at DESC, amount);

The database pins status = 'active', walks the pre-sorted created_at descending subtree, filters amount > 1000 as it goes. Results come back sorted. No extra work.

Same query. Different field order. Completely different performance profile.

---

Index Direction

When you define an index field, you specify direction: ascending or descending.

For single-field indexes, direction does not matter. The tree can be traversed in either direction at identical speed.

For compound indexes with mixed sort directions, direction matters.

If your query sorts ORDER BY created_at DESC, status ASC — descending on one, ascending on another — your index must either match exactly or be the exact inverse:

(created_at DESC, status ASC)  -- exact match, works
(created_at ASC, status DESC)  -- exact inverse, tree walked backwards, works
(created_at ASC, status ASC)   -- mismatch, in-memory sort required
(created_at DESC, status DESC) -- mismatch, in-memory sort required

Mental model: a folder sorted by date descending, then name ascending. Flip the whole folder upside down — still valid. Flip only the date dividers but not the name dividers — chaos.

---

MongoDB vs PostgreSQL: Same Principle, Different Implementation

This is where my earlier confusion lived. I had learned B-Trees from MongoDB, then started working with PostgreSQL indexes and noticed things behaved slightly differently. I connected them loosely but never understood why.

The difference is precise and worth knowing.

MongoDB: B-Tree

MongoDB uses a standard B-Tree where leaf nodes are the bottom level of the tree. To read a range of values, MongoDB finds the starting leaf node and walks the tree rightward through sibling nodes.

The leaf nodes are connected, but the connection is at the tree structure level.

PostgreSQL: B+ Tree

PostgreSQL implements a B+ Tree — a variant with one critical structural difference.

In a B+ Tree:

• Internal nodes contain only keys used for navigation — no data pointers
• Leaf nodes contain the actual data (key + TID pointer to the heap row)
• All leaf nodes are connected as a doubly-linked list

That last point is the key difference. In PostgreSQL’s B+ Tree, leaf nodes at the bottom level form a linked list connecting every leaf to its neighbours in sorted order, in both directions.

What this changes in practice:

Range queries become linked list walks. Once PostgreSQL finds the starting leaf node for a range query, it does not need to navigate the tree at all for the remaining values. It simply follows the doubly-linked list from leaf to leaf until the range is exhausted. No tree traversal for the continuation — pure sequential list walking.

Each internal page holds hundreds of pointers. Because internal nodes contain only keys (not data), they are compact. A single 8KB page holds hundreds of child pointers. This means the tree stays extremely shallow — PostgreSQL can index 108 million rows in just 3 levels. Even the most massive tables rarely exceed 4-5 levels deep.

Ordered results are nearly free. Because the leaf linked list is already sorted, a query with ORDER BY on an indexed column often requires no additional sort step at all — the database just walks the leaf list in the requested direction.

The Interview Confusion Explained

When I learned MongoDB B-Trees, I internalised: “leaf node contains value + pointer, tree traversal finds value, follow pointer to document.” That is correct for MongoDB.

When I started with PostgreSQL, EXPLAIN output showed different behavior — range scans that felt faster than I expected, sort operations that sometimes disappeared entirely. I attributed it to PostgreSQL being “more optimised” without understanding the structural reason.

The structural reason: the B+ Tree leaf linked list. Range scans in PostgreSQL after the first lookup are linked list traversals, not tree traversals. That is a genuinely different access pattern.

Both approaches build on the same principle — sorted data read sequentially. The implementation detail is where the sorted reading happens: through the tree itself (MongoDB B-Tree) or through the leaf linked list (PostgreSQL B+ Tree).

---

Text Indexes: A Completely Different Structure

Both MongoDB and PostgreSQL support full-text search through a different index type entirely — the inverted index.

MongoDB Text Index

db.articles.createIndex(
  { title: "text", body: "text" },
  { weights: { title: 10, body: 2 } }
)

MongoDB tokenizes text fields, removes stop words, stems words so “running” and “run” both match, and builds a token-to-documents map:

"mongodb"  →  [doc1 (score: 10), doc4 (score: 2)]
"index"    →  [doc1 (score: 2),  doc3 (score: 10)]

Weights control the relevance score contribution per field. A match in title with weight 10 counts five times more than a match in body with weight 2.

Constraints: one text index per collection, does not follow Prefix Rule or ESR Rule, large storage footprint.

PostgreSQL Full-Text Search

PostgreSQL uses tsvector and tsquery types with a GIN (Generalized Inverted Index) index:

CREATE INDEX idx_articles_fts ON articles
USING GIN(to_tsvector('english', title || ' ' || body));

Query:

SELECT * FROM articles
WHERE to_tsvector('english', title || ' ' || body)
      @@ to_tsquery('english', 'mongodb & index');

PostgreSQL’s GIN index is also an inverted index under the hood — same fundamental structure as MongoDB’s text index, different syntax and configuration.

For serious full-text search at scale, Elasticsearch or MongoDB Atlas Search are more capable tools. These built-in options work well for moderate use cases.

---

The Things Worth Remembering

An index is built once and then surgically maintained on every write forever. It is never rebuilt per query.

A compound index is one tree with a composite key — not multiple trees. This is why the Prefix Rule exists and why field order matters.

The ESR Rule — Equality, Sort, Range — is the field ordering that lets the tree serve your query without extra in-memory work. Equality narrows, sort pre-orders, range filters last.

MongoDB uses a B-Tree. PostgreSQL uses a B+ Tree where leaf nodes form a doubly-linked list. Both are fast. The B+ Tree structure makes PostgreSQL range scans and ordered reads slightly more efficient because after the first lookup, the database walks the leaf list rather than traversing the tree.

Direction only matters for compound indexes with mixed sort directions.

Every index slows writes. Only index what your actual query patterns need.

And the thing I wish I had known going into that interview: the node in a B-Tree leaf contains the indexed field value and a pointer to the actual row on disk. That is it. Internal nodes contain only navigation keys. Once you know what is in the node, everything about how indexes behave — range queries, compound keys, the Prefix Rule — follows logically from there.