SQL Indexing

Index behaviour depends on the database, index type, selectivity, and query plan. B-tree, hash, clustered, and covering indexes do not all work the same way, and a low-cardinality column can still be useful in a suitable composite or covering index.

What is an Index in a Database?

1. What is an Index?

An Index in a database is a special data structure (most commonly a B-Tree) built on one or more columns of a table to make data retrieval faster.

Its job is simple:

Help the database find data quickly without scanning every row.

Instead of reading the entire table row by row, the database uses the index to jump directly to the matching rows.

This makes queries much faster, especially on large tables.

2. Real-World Analogy — Index in a Book

Imagine you have a 1,000-page book and want to find the topic:

“Binary Search Tree”

Without a Book Index

You start flipping pages one by one until you find it.

This is slow.

This is exactly how a Full Table Scan works in a database.

The database checks row after row until it finds the match.

With a Book Index

Now imagine the book has an index at the back.

You look up:

Binary Search Tree → Page 742

You directly jump to page 742.

This is how a Database Index works.

Instead of checking every row, SQL jumps directly to the matching location.

3. What Problem Does an Index Solve?

Without an index, the database has to scan every row.

This becomes extremely slow as data grows.

For example:

• 100 rows → okay
• 10,000 rows → slower
• 1,000,000 rows → very slow

Indexes solve this by reducing search work dramatically.

4. How Indexing Works Internally

When you create an index, the database creates a separate hidden structure (think of it like a mini-table).

This hidden structure stores:

1. A sorted copy of the indexed column
2. A pointer to the actual row in the main table

Example

If you create an index on email:

CREATE INDEX idx_user_email ON users(email);

The database builds something like this internally:

This structure is sorted alphabetically.

Because it is sorted, the database can search it extremely fast.

5. Why Indexes Are Fast

Indexes are fast because they are sorted.

This allows the database to use Binary Search.

Instead of checking rows one by one:

• Full scan on 1,000,000 rows → may check nearly all rows
• Binary search using index → may check only ~20 steps

That is the power of indexing.

6. Practical Example — Global Users Table

Imagine a users table with 100,000 records.

Now let us see how indexes help.

7. Case 1 — Finding an Email

Query

SELECT * FROM users WHERE email = 'amit@sample.org';

Without an Index

The database starts at row 1 and checks every row:

• row 1
• row 2
• row 3
• …
• row 99999

This is slow.

This is called a Full Table Scan.

With an Index

CREATE INDEX idx_user_email ON users(email);

Now the database uses the index.

Instead of checking 99,999 rows, it jumps directly to:

amit@sample.org

Then follows the pointer to the actual row.

This is much faster.

Output

8. Case 2 — Sorting Data (ORDER BY)

Indexes also help with sorting.

Query

SELECT full_name, email
FROM users
ORDER BY full_name;

Without an Index

The database:

1. reads all rows
2. sorts them in memory
3. returns result

This becomes expensive on large tables.

With an Index

CREATE INDEX idx_user_name ON users(full_name);

Now the data is already sorted inside the index.

The database can read rows in sorted order directly.

This avoids expensive sorting work.

Output

9. Case 3 — Composite Index

Sometimes queries filter using multiple columns.

Example:

• full_name
• city

This is where Composite Indexes help.

Query

SELECT *
FROM users
WHERE full_name = 'Raj Patel'
AND city = 'Mumbai';

Composite Index

CREATE INDEX idx_name_city ON users(full_name, city);

Now SQL can search using both values together.

This is faster than searching one column at a time.

Output

10. Hidden Cost of Indexing

Indexes make reads faster.

But they also make writes slower.

This is called the Write Penalty.

Why?

Every time you:

• INSERT
• UPDATE
• DELETE

The database must:

1. update the main table
2. update every related index

So if a table has 10 indexes:

Every insert must update 10 extra structures.

That makes writes slower.

Trade-Off

Indexes improve:

• SELECT
• WHERE
• ORDER BY

But they slow down:

• INSERT
• UPDATE
• DELETE

That is why indexing must be used carefully.

11. Full Table Scan vs Index Lookup

12. When Should You Create Indexes?

Indexes are most useful on columns used frequently in:

• WHERE
• JOIN
• ORDER BY
• GROUP BY

Good candidates:

• email
• user_id
• city
• created_at
• foreign keys

13. Common Mistakes to Avoid

1. Indexing Low-Selectivity Columns

Do not index columns with very few distinct values.

Example:

• gender
• status (active/inactive)
• yes/no flags

Why?

Because SQL still has to scan a large part of the table.

Index gives little benefit.

2. Over-Indexing

Too many indexes make writes slower.

More indexes = more maintenance cost.

Only create indexes that are actually useful.

3. Indexing Frequently Updated Columns

Avoid indexing columns that change constantly.

Example:

• last_seen
• live_status
• heartbeat_time

Why?

Because the index must be constantly updated.

This adds heavy load.

4. Forgetting to Verify with EXPLAIN

Just creating an index is not enough.

You must verify whether SQL is actually using it.

Use:

EXPLAIN SELECT * FROM users WHERE email = 'amit@sample.org';

This shows the execution plan and confirms whether SQL used the index.

14. Summary

An index is a special data structure that helps SQL find data faster.

It works like a book index:

• find the keyword
• jump to the location

Indexes improve:

• searching
• filtering
• sorting
• joins

Internally, they store:

• sorted values
• row pointers

They make reads much faster, but writes slower.

Use indexes carefully and only where needed.

Final Mental Model

Without index:

Read everything, then find the answer.

With index:

Jump directly to the answer.