What an Index Really Is

From lesson 8-1, every table in this course carries an id INTEGER PRIMARY KEY because a stable, meaningless identifier gives each row a permanent address that foreign keys can point to.

The id never changes even when the name, email, or price does, which is what makes it a safe target for a reference.

This lesson adds the performance half of the story. Keys and indexes are also how the database finds a row without reading the whole table.

How a query actually finds rows

Run SELECT * FROM users WHERE email = 'ben@example.com' on a plain table and the database does the only thing it can: read every row and test each one. That is a full table scan. With 3 rows it is instant. With 50 million rows it reads 50 million rows to find one, and it does that on every such query.

An index fixes this. An index on users(email) is a separate structure the database maintains alongside the table: all the email values, kept in sorted order, each with a pointer to its row. Sorted order is the entire trick: to find one email among 50 million, the database can check the middle value and instantly discard the half of the list the target cannot be in, then repeat, 50 million → 25 million → 12.5 million ... reaching one row in about 26 steps instead of 50 million. A phone book gives you the same power: because it is sorted by name, you jump near the right spot and narrow down instead of reading every page. In practice indexes are stored as B-trees, wide trees a few levels deep, so a lookup is 3-4 hops even for huge tables.

Creating an index and reading the plan

Creating an index takes one statement:

CREATE INDEX idx_users_email ON users(email);

The name is arbitrary, and idx_table_column is a widespread convention that makes indexes easy to recognize in a schema dump.

Knowing whether the database actually uses it is a separate matter. Putting EXPLAIN QUERY PLAN in front of a query makes SQLite report its plan without running the query, and the plan turns on one keyword:

The next block plans the same query before and after the index exists. The exact wording of plans varies between SQLite versions, so this block has no pass or fail check attached, and reading it is the whole exercise.

The same query, planned twice

The two plans differ in one word that matters: SCAN before the index exists, SEARCH ... USING INDEX afterwards.

CREATE TABLE users (
  id INTEGER PRIMARY KEY,
  email TEXT,
  name TEXT
);

INSERT INTO users (email, name) VALUES ('ana@example.com', 'Ana');
INSERT INTO users (email, name) VALUES ('ben@example.com', 'Ben');
INSERT INTO users (email, name) VALUES ('cara@example.com', 'Cara');

-- Before: no index on email
EXPLAIN QUERY PLAN
SELECT * FROM users WHERE email = 'ben@example.com';

CREATE INDEX idx_users_email ON users(email);

-- After: same query, new plan
EXPLAIN QUERY PLAN
SELECT * FROM users WHERE email = 'ben@example.com';

The data here is three rows, so both versions return instantly and the timing tells you nothing. The plan is the thing to watch, because it is the same plan the database would choose at 50 million rows, where the difference is a coffee break against a few milliseconds.

This is the habit worth building. Reading plans on small development data catches missing indexes before production traffic finds them for you.

Why a few hops are enough

A lookup in a B-tree index over 50 million rows takes only a handful of hops because the entries are kept in sorted order, and sorted order lets every comparison discard a large fraction of what remains.

Halving 50,000,000 repeatedly reaches a single row in about 26 steps, since 2²⁶ ≈ 67 million. A real B-tree does better still, splitting into hundreds of branches per level rather than two, which brings typical lookups down to three or four levels.

The important property is how the cost grows. Doubling the table adds one more halving rather than doubling the work, which is what "logarithmic" means in practice:

A full scan over the same table grows in a straight line, so the gap between the two widens with every row you add.