Why indexes, and the B+ tree idea

Part of the free LogicWiz SQL & Databases course, Module 14: Indexes and query plans. The queries and practice run in the app on real Postgres.

Aarav and Meher's food app now has 30,000 orders. The "My orders" page reads all 30,000 to find a customer's 5. One line of SQL makes it read about five. What does that line build?

You'll learn to

• Read a Seq Scan in EXPLAIN and say why it is slow on big tables
• Create an index and see the plan change
• Explain how a B+ tree finds a key in 3-4 page reads
• Know which indexes Postgres creates for you

Learn

Reading every row

Imagine finding Riya's marks in an attendance register with no order: you read every page until the end, because another Riya might be on the last page. That is a sequential scan (Seq Scan): the database reads the whole table.

For 20 rows nobody notices. For 30,000 orders, or 3 crore UPI payments, it is the reason a page takes seconds.

An index is like the index at the back of a textbook: a separate, sorted list of values with the page each one is on. Postgres looks the value up there and jumps straight to the right rows.

Without an index: Seq Scan

EXPLAIN (COSTS OFF)
SELECT * FROM orders WHERE customer_id = 42;
SELECT COUNT(*) FROM orders WHERE customer_id = 42;

EXPLAIN shows the plan: how Postgres will run the query, without running it. Seq Scan on orders with Filter: (customer_id = 42) means "read all 30,000 rows and keep those that match". Only 5 match.

Add an index, ask again

CREATE INDEX idx_orders_customer ON orders (customer_id);
EXPLAIN (COSTS OFF)
SELECT * FROM orders WHERE customer_id = 42;

Now the plan uses idx_orders_customer: an Index Cond instead of a Filter. Postgres looks up 42 in the index, gets the 5 row addresses, and reads only those. (The "Bitmap" words are explained in the next lesson.)

The B+ tree inside

A Postgres index is a B+ tree: a short, wide tree of pages (8 KB blocks on disk).

• Leaf pages (the bottom) hold every key in sorted order, each with the address of its row. Leaves are linked left to right.
• Internal pages above hold only "signposts": keys that say which child to go down.
• One page holds hundreds of signposts, so the tree is very wide and very short.

To find 42, Postgres reads the root, follows a signpost, and lands on the right leaf: 3 or 4 page reads, even for millions of rows.

A tiny B+ tree on customer_id

Search for 42: root says "< 2000, go left", internal says "< 500, first leaf", the leaf has 42 and the addresses of its 5 orders. A range like BETWEEN 40 AND 900 finds 40, then walks the linked leaves to the right.

B tree vs B+ tree (a favourite question): a B tree stores keys and data pointers in every node; a B+ tree keeps all data pointers in the leaves, internal nodes hold only keys, and leaves are linked, so range scans are a simple walk. Height: with fan-out f (children per node), h levels reach about f^h keys. With f = 300, 3 levels cover 300³ = 2.7 crore keys. Height ≈ ⌈log_f N⌉.

Indexes you already have

SELECT tablename, indexname, indexdef
FROM pg_indexes
WHERE tablename IN ('customers', 'orders')
ORDER BY tablename, indexname;

Every PRIMARY KEY and UNIQUE constraint gets a B+ tree index automatically: that is how Postgres checks for duplicates quickly. orders has a FOREIGN KEY to customers, but no index on customer_id.

Postgres does not index foreign key columns for you. orders.customer_id is used in almost every join and lookup, so it usually needs its own CREATE INDEX. Forgetting this is one of the most common causes of slow apps.

MySQL (InnoDB) stores the table itself as a B+ tree ordered by the primary key (a clustered index), and every secondary index points to the primary key. Postgres keeps rows in a separate unordered heap, and every index points to a row address. InnoDB also creates an index on foreign key columns automatically.

In one line

An index is a sorted B+ tree of values and row addresses: a lookup reads 3-4 pages instead of the whole table; PK and UNIQUE are indexed for you, foreign keys are not.

Interview corner

What is an index and how does it speed up a query?

A separate sorted structure (in Postgres, a B+ tree) mapping column values to row addresses. Instead of scanning every row, the database descends the tree in a few page reads and fetches only the matching rows. The cost is extra disk space and slower writes.

Why B+ trees and not hash tables or binary trees?

B+ trees have huge fan-out, so they are only 3-4 levels deep even for crores of rows (few disk reads), and their sorted, linked leaves support ranges, ORDER BY and prefix searches. A hash index only does equality; a binary tree is far too deep on disk.

Does a foreign key create an index?

In Postgres, no: only PRIMARY KEY and UNIQUE do. You usually add an index on the foreign key column yourself, because joins and lookups use it and deleting a parent row has to search it. MySQL InnoDB creates one automatically.