Intro to SQL Indexes

In this reading, you’ll learn what SQL indexes are, why they can drastically improve lookup performance, and why they come with tradeoffs for insertion and deletion. By the end, you’ll be able to:

• Describe what a SQL index is
• Explain how SQL uses indexes under the hood, and how it impacts time complexity
• Decide when you should or should not use indexes

What is a SQL Index?

A SQL index is a special data structure used by SQL databases to speed up searches by reordering or sorting the data in specific columns. If you have a table with tens of thousands—or even millions—of rows, searching without an index becomes slow because the database must scan every row (an O(n) operation). With an index, the database uses a sorted structure (usually a B-tree) to find matching entries in O(log n) time.

For example, a primary key or UNIQUE constraint automatically creates an index on that column. If you query by the primary key, you benefit from the indexed structure.

Suppose you have a cookies table with a baker_id column, and you frequently query:

SELECT * FROM cookies WHERE baker_id = 3;

If baker_id is indexed, the lookup is much faster than if there were no index. This concept holds especially for more complex queries like:

SELECT * FROM cookies
WHERE type = 'sugar' AND chocolate IS TRUE;

If we frequently query by type and chocolate, a multi-column index can optimize these lookups further, as it sorts the table by both columns at once.

How Does SQL Use Indexes?

The power of indexing comes down to time complexity:

• Without an Index: Searching is O(n). The database must check each row sequentially until it finds matches.
• With an Index: Searching is O(log n). The database leverages a sorted structure (like a B-tree) for quick lookups.

Example #1: Lookup with NO Index

If you’re searching for baker_id = 3, the DB scans every row. That’s O(n) time as it compares each row’s baker_id.

Example #2: Lookup with Index

Once baker_id is indexed, the DB keeps the column values in a B-tree, each entry pointing to the row in the original table. That means:

With a sorted structure, finding “3” only needs log n comparisons, then the DB retrieves the matching row(s) efficiently.

When Should You Add Indexes?

While indexes make lookups faster, they also make insertions and deletions slower:

• Insertion/Deletion with No Index: O(1)
• Insertion/Deletion with Index: O(log n)

This overhead occurs because the database must update the B-tree structure whenever a new row is added or removed.

Example #1: Insertion with NO Index

Example #2: Insertion with Index

With an index on baker_id, the DB has to insert the new row normally and update the B-tree. That’s a cost of O(log n).

Over large data sets, O(log n) can be close to O(1), but there’s still some overhead. Therefore:

Only use indexes if you read/lookup more often than you insert/delete on those columns.

For example, if your cookies table rarely changes, but you search by type and chocolate constantly, indexing those columns is beneficial. If you frequently insert or delete rows in that table, the index overhead may not be worth it.

Big O Overview

Here’s a rough diagram comparing O(1) and O(log n). Notice that O(log n) grows slowly:

Hence, indexing is often a huge net gain for large datasets that see many lookups.

Wrapping Up

Key points:

• Indexes help SQL find matching rows in O(log n) time by maintaining a sorted data structure.
• They cost O(log n) for insertions and deletions because the index must be updated.
• Use them only on columns you frequently query, and where you can afford the overhead on inserts/deletes.

To learn more, check out this deep-dive on indexing. In the next reading, you’ll discover how to create a SQL index, whether single-column or multi-column, to optimize your queries further.