An index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional storage space and slower writes.

Think of a Library:

1. You are looking for the book "Interstellar Gardening".
2. Without an Index: you have to walk through every shelf, checking every single book until you find it. (Full Table Scan - $O(n)$).
3. With an Index: You go to the Card Catalog. You look up 'I' and find exactly which shelf and row the book is on. (Index Scan - $O(\log n)$).

---

How it works?

Most databases use a B-Tree (Balanced Tree) to store indexes. This keeps the data sorted and allows for binary-search-like speed.

Primary vs. Secondary Index

• Primary Index: Usually on the Primary Key. The physical data is often sorted by this.
• Secondary Index: Any other index you create (e.g., on a "username" column). It points to the primary index.

The Cost of Speed

• Storage: Every index takes up disk space.
• Write Performance: Every time you INSERT or UPDATE a row, the database must also update every index on that table. This makes writes slower.

---

Use Case: Composite Index

If you often search for users by first_name AND last_name, a single index on (last_name, first_name) is much faster than two separate indexes. Pro Tip: Order matters! A composite index on (A, B) can be used for searches on A or (A, B), but NOT for searches on B alone.

When NOT to Index?

• Tables with very few rows (Scanning is faster than looking up the index).
• Columns that are updated thousands of times per second.
• Columns with "Low Cardinality" (e.g., a "Gender" column with only 2 values).

Common Question

"Why are my queries still slow even though I added an index?" Answer: Check if your query is "SARGable" (Search Argument Able). For example, WHERE name LIKE '%John' cannot use a standard index because it starts with a wildcard. 🔍