How database indexes actually work?

A lookup in one million users can mean checking rows one by one, or following a compact tree that narrows the email range. Both find the same user. Where does the saved work come from, and what does the index still need to fetch?

Without a usable index, the database starts at the Users table and reads a row, then compares its email with the one you requested. It keeps moving to the next row until it finds a match. If that email is late—or absent—it may examine all one million rows.

Sorted email keys let each page direct the lookup to the child range that could contain the target. The Root page narrows the choices to a Branch page, then a Leaf page. Many ranges per page keep the tree shallow, even with a million keys.

The leaf page gets you to the matching email entry, but that isn't necessarily the user row itself. The entry points to the corresponding row in the Users table, where the database fetches the requested columns. The tree finds the address; the table supplies the record.

For this selective email lookup, a scan may check up to one million rows. The index reads a few tree pages, then fetches the user row; actual cost depends on page layout and cache.

Let's think this through. For the known email in this example, what does the B-tree leaf help the database do? A: Locate the matching user row. B: Check every user row in order. C: Return every column without accessing the table. Choose an answer, or just think it through. I'll explain in a moment.

The answer is A: Locate the matching user row. The leaf holds the matching email entry and information for locating its user row. It avoids checking unrelated rows, but this query still fetches the row for the requested data.

For one email match, the B-tree leads to one user row, leaving most of the table untouched. With a broad predicate, fetching many matching rows through the index can cost more than scanning the table, so the optimizer estimates which path is cheaper.

A new user has to be written to both the Users table and the Email index. If that user's email changes, the index entry must change too. Each additional index uses storage and adds work to writes.

Favor indexes on selective columns you filter frequently, like email. Check the query plan to confirm the database chooses index access rather than a scan. Indexes also add storage and write work, so don’t assume every query benefits.

Narrow first, fetch the row. For a selective email lookup, the index avoids checking unrelated users, but the database still fetches the matching row and maintains the index as data changes.