Finding one row without scanning the table

A buyer opens product 27 in our shop. The application asks for its name:

SELECT name FROM products WHERE product_id = 27;

If the database has no suitable index, it may inspect rows until it finds the product. With a large table, that can mean reading many rows just to return one name.

The page lesson introduced blocks of stored data. The sorted-search lesson showed why one packed sorted list makes insertion costly. Here we follow the alternative: a small set of routing pages guiding a lookup toward a sorted group of entries. Read those bridges first if pages or binary search are unfamiliar.

The table is not a search guide

Here is a small part of our example table, shown in an arbitrary physical order. Other rows are omitted.

The ID tells us which product we want. It does not tell us where its row is stored. Even if IDs are numbers, product 27 is not necessarily the twenty-seventh row.

An index stores an additional structure that helps locate entries by a key. Here the key is product_id. Our example index keeps keys sorted and records a row location beside each leaf entry. The table itself does not need to be rearranged into that order.

Choose a branch, then find the entry

A B+ tree has routing pages above leaf pages. The routing pages tell a search which child to visit. The leaves contain the entries we are looking for.

Our tiny tree has one routing page and three leaves. Its two separator keys are 20 and 40. In this example, equality goes to the branch on the right: 20 belongs in the middle branch, and 40 belongs in the last branch.

Follow the lookup yourself:

1. Read the routing page. Compare 27 with 20 and 40. It belongs in the middle range.
2. Read that leaf. Find 27 among its sorted entries. An implementation can use binary search within a page instead of checking every entry.
3. Follow the row reference. Entry 27 points to row C, where the table stores “Canvas tote.”

The other two leaves did not need to be searched. In this constructed tree, we visited two index pages and then fetched the table row. That does not necessarily mean three disk reads: some or all of the relevant pages may already be in memory.

Why the same idea works for a larger table

A real routing page usually points to many children. When the tree grows, more routing levels can sit between the root and the leaves. At each level, one decision narrows the remaining key range.

The number of children a routing page can have is called its fanout. High fanout lets a tree cover many entries with relatively few levels. The exact height depends on page size, key size, and how full the pages are. We do not need those calculations to follow today’s lookup; the deeper reading derives them separately.

The important relationship is visible in our small tree: a separator rules out whole groups of entries at once. Larger trees repeat that operation at additional levels.

Change the request: find a range

Now the shop needs products with IDs from 27 through 46, including both endpoints.

The tree first routes to 27 exactly as before. It then reads forward through the ordered leaf entries. Our example uses links between neighboring leaves, so the scan can continue into the next leaf.

A hash index takes a different approach: it uses a hash function to choose a bucket for an equality lookup. It does not provide this key order for a range scan. PostgreSQL documents B-tree support for equality and ranges, while its hash indexes support equality comparisons. PostgreSQL index types

An index has a maintenance cost

When the shop inserts product 29, the table gains a row and the index must gain an entry in the middle range. If a leaf is full, the tree may need to split it and update the routing information.

So an index makes selected reads easier by creating work during writes. It also occupies space. A query returning most of the table may be better served by scanning the table, especially if following many scattered row references would be expensive.

This lesson’s row references are one teaching model. Engines may store different kinds of references or values, and a transaction still needs to check whether a found row is visible to it. The index locates candidates; it does not decide every rule about reading them.

Try a boundary key

Using the exact tree above, which leaf should a lookup for 40 visit? Which entries should a range from 33 through 40 return?

Carry this picture forward

For product 27, the index guided us to one leaf and then to one table row. Ordered leaves also let us continue across a range. Those two capabilities explain why ordered indexes are useful for both individual product pages and lists of products.

The next lesson introduces log-structured storage, which organizes updates differently and does more work later when merging data. Keep asking the same questions: how does a read find its entry, and what work does a write create?

Go deeper when you need it

• Ordered indexes, ranges, and pagination
• Index splits, maintenance, and storage costs
• Hash indexes and query tradeoffs

Sources and further reading

• PostgreSQL 18: index types and supported queries
• PostgreSQL 18: B-tree implementation
• PostgreSQL 18: multicolumn indexes