What an Index Is

Without an index, finding the rows matching WHERE dept_id = 1 means reading every row in the table and checking each one. That is a full table scan. On a thousand rows nobody notices. On fifty million it is the difference between a page that loads and a page that times out.

An index is a separate, sorted structure that maps values to the rows containing them — the index at the back of a book, for a database. The database consults it, finds the handful of matching row locations, and reads only those.

Seeing the difference

The playground can show this directly. dept_id has no index:

SQL
EXPLAIN QUERY PLAN SELECT * FROM employees WHERE dept_id = 1;

SCAN employees — every row read.

emp_id is the primary key, which is indexed automatically:

SQL
EXPLAIN QUERY PLAN SELECT * FROM employees WHERE emp_id = 4;

SEARCH employees USING INTEGER PRIMARY KEY — the database goes straight to the row. Same table, same shape of query, completely different amount of work.

SCAN means every row. SEARCH means an index was used. That one distinction is most of what a query plan tells you.

What the structure actually is

Almost every index you meet is a B-tree (strictly, a B+ tree): a balanced tree kept in sorted order. Lookups, range scans and ordered reads all cost roughly log(n) — doubling the table adds one level, not double the work. That is why an indexed lookup on fifty million rows is still fast.

Because it is sorted, a B-tree index serves more than equality:

WHERE x = 5 — exact match
WHERE x > 5, BETWEEN — range scan from a starting point
ORDER BY x — read in index order, no sort needed
MIN(x) / MAX(x) — the first or last entry

Other index types exist for other jobs: hash (equality only), GiST/GIN (PostgreSQL, for full-text and JSON), bitmap (Oracle, low-cardinality columns). B-tree is the default and the one to understand first.

Creating one

CREATE INDEX idx_employees_dept ON employees (dept_id);

A naming convention such as idx_<table>_<columns> pays off the first time you read a slow-query log and need to know what exists.

Unique indexes both speed up lookups and enforce a constraint:

CREATE UNIQUE INDEX idx_customers_email ON customers (email);

That one would fail on this dataset — two customers share an email address, which is exactly the kind of thing a unique index is for catching.

Those blocks have no Run button. The playground rebuilds its database for every request, so an index created in one query would be gone before the next — the lesson would show you a CREATE that appears to work and then a plan that has not changed, which teaches the opposite of the truth.

What you get for free

Most databases index some columns without being asked:

Primary keys — always indexed.
Unique constraints — implemented as a unique index.
Foreign keys — indexed automatically by MySQL/InnoDB, but not by PostgreSQL, SQL Server or Oracle. An unindexed foreign key is one of the most common causes of a slow join, precisely because people assume it is covered.

What an index costs

Indexes are not free, and this is the part that gets left out.

Writes get slower. Every INSERT, UPDATE and DELETE must update every affected index. A table with eight indexes does nine writes instead of one.
They take space. An index on a wide column can approach the size of the table.
The planner has more to consider, and more chances to choose badly.

So the rule is not "index everything". It is: index what you filter, join and sort on; then remove the ones nothing uses. Every mainstream database can report index usage statistics, and production systems routinely carry indexes nobody has read in years.

Where indexes help most

Columns in WHERE clauses, especially selective ones.
Foreign keys, both sides of a join.
Columns in ORDER BY, to avoid a sort.
Columns in GROUP BY, sometimes.

Where they help least

Small tables. Reading two hundred rows directly beats consulting an index first.
Columns with few distinct values. An index on a boolean that is 95% true will be ignored for the common value — reading the table is cheaper than reading most of the index and the table.
Columns that are written constantly and read rarely.

That second point has a name: selectivity. An index earns its keep when it eliminates most of the table. When it eliminates half, the planner will usually scan instead — and it is right to.

Common mistakes

Assuming foreign keys are indexed — only on MySQL.
Indexing every column — writes slow down and the planner gets worse choices.
Indexing a low-cardinality column and expecting a speed-up.
Adding an index without measuring — plans before and after, on realistic data volumes.

Interview question

What is an index and what does it cost?

A sorted structure that lets the database find rows without reading the whole table, usually a B-tree, giving log(n) lookups and free ordering. The cost is write amplification — every index must be maintained on every write — plus disk space. Mentioning that foreign keys are not automatically indexed outside MySQL is the detail that lands.

Check yourself

What is the difference between SCAN and SEARCH in a query plan?
Why can an index on a mostly-true boolean column be useless?
Name two costs of adding an index.