Database indexes: B-trees, composite keys and query access

01Database index: definition and tradeoff

A database index is a maintained data structure that maps searchable keys to records or contains data needed by a query. A key is the field or ordered combination of fields used for lookup, such as author and title. Think of a library catalog: to find books by Ursula Le Guin, you consult the author catalog rather than walking past every shelf. The catalog points to books; it is not a second copy of every page inside them.

Suppose our database has Book(id, author, title, publishedYear). Without a useful index, a query for one author may inspect every book row. With an author index, the engine can locate the relevant author entries and then fetch their rows. An index trades extra stored structure and write work for less work on selected reads.

02Worked example: author and title lookup

Consider a Book table containing the following four rows. We want to find Le Guin’s books and return them in title order:

The query is:

SELECT id, author, title
FROM Book
WHERE author = 'Le Guin'
ORDER BY title, id;

It returns IDs 11 and 13, in that order. Adding id makes the order deterministic if two books have the same title. For this example, assume an ordinary alphabetical collation; the database's configured collation determines the actual text ordering.

A simplified ordered index on (author, title, id) contains (Butler, Kindred, 12), (Butler, Parable..., 14), (Le Guin, A Wizard..., 11), and (Le Guin, The Dispossessed, 13).

1. The query asks for author = 'Le Guin' ordered by title and ID.
2. The database seeks to the first index entry with that author.
3. It scans the adjacent Le Guin entries in title order.
4. It reads rows 11 and 13 if the requested output needs fields unavailable from the index.
5. It stops when the author changes or the requested limit is met.

A seek navigates directly to a relevant key range; a scan then walks entries. Here the index has converted a whole-table search into a narrow seek and scan. If the table is tiny, a scan may still be cheaper; the query optimizer estimates these costs rather than treating any existing index as mandatory.

Selectivity describes how narrowly a predicate filters records. State the matched fraction to avoid terminology ambiguity: 100 matching rows out of one million is 0.01%, while 900,000 matches is 90%. The first query may avoid much table work with an index; the second may be cheaper as a sequential scan. Physical row placement, cached pages and which columns are returned still affect the decision. The mere existence of an index cannot establish the faster plan.

03B-tree, hash and inverted indexes

The book example needs both an author lookup and title ordering. Index structures organize searchable keys differently, so a structure that narrows an exact lookup may not support an ordered range or a word search. Compare the structures by how they reach the candidate records.

A B-tree index keeps search keys in sorted order inside a balanced tree of storage pages. It lets a database find a key without checking every row, and it can scan a consecutive range of keys.

To read the tree below, start with three terms:

1. A page is a block of data that the storage engine manages as a unit. One page can contain many keys.
2. The root is the entry page. Keys in internal pages act as signposts to the next page. For example, a separator at 40 sends a search for 50 to the side containing keys 40 and above.
3. A leaf is a page at the bottom. Balanced means every root-to-leaf path has the same number of levels. The example is a B+ tree, a common B-tree variant: its searchable record entries are in the leaves, which are linked for scans.

An equality query asks for one exact value, such as id = 42. A range query asks for values between bounds, such as years 2000 through 2010. A B-tree can answer both: descend to the first matching key, then follow the ordered entries if more matches are needed.

A hash index applies a hash function to a search key to choose a bucket, a group of candidate entries. Different keys can share a bucket, so the engine still checks which entry actually matches. Hash buckets group by hash value, not by the original key’s order; they do not naturally support scanning consecutive years.

An inverted index maps a term to the documents containing it. Its postings list contains document IDs and may also include counts or positions. For example, green → [D1, D3] means documents D1 and D3 contain “green.” It is called inverted because it goes from term to documents, reversing the document-to-terms view.

Interview tip: start with the query, then justify the index. Equality does not automatically make a hash index better than a B-tree; consider the database’s supported operations, measurements and other query needs.

An index does not necessarily sort the underlying table the same way. Some engines cluster table records around a primary key; others keep index entries separate from table pages. An index-only scan also depends on coverage and visibility rules in the chosen database.

Composite means the key contains several fields; it is not a competing tree algorithm. Covering means the index contains the fields needed by a query; it is not a separate universal storage structure.

04Composite indexes, key order and covering queries

The author/title example used several fields to group related records and order them within a group. Apply the same idea to customer order history: first isolate one customer, then return only that customer’s newest orders. Consider this query:

SELECT orderId, createdAt, total
FROM Orders
WHERE customerId = 'C27'
ORDER BY createdAt DESC, orderId DESC
LIMIT 20;

The leftmost prefix rule says that a composite B-tree index most directly supports lookups using its first column, or its first several columns together. It is a useful starting point for B-tree reasoning, not a universal claim that an engine can never use a later column. Optimizers may use skip scans or combine indexes depending on data distribution and implementation. In an interview, explain why your selected leading columns narrow the work directly, then inspect a plan in a real system.

A covering index includes fields needed by the query, such as total, to reduce row fetches where the engine allows it. The cost is a larger index and more updates when those fields change.

For PostgreSQL, the concrete candidate is:

CREATE INDEX orders_customer_newest
ON Orders (customerId, createdAt DESC, orderId DESC)
INCLUDE (total);

The query expression must match the access path too. An ordinary index on email does not provide the same ordered keys as lower(email). PostgreSQL supports an expression index on lower(email) when case-normalized lookup is the intended rule. That normalization has to match the product’s equality semantics; adding an index does not decide which spellings should count as the same address. See expression indexes.

05Index maintenance and write amplification

An index must stay consistent with changes to the records it describes. Write amplification is the additional physical write work created by one logical application change. Index maintenance contributes to that cost because changing one row can require updating several stored structures.

Insert book 15: (Le Guin, The Left Hand of Darkness, 1969). The database writes the row and adds entries to each maintained index: the primary-key index, author/title index, and perhaps a publication-year index. Updates of indexed fields remove or supersede old entries and install new ones; deletes must maintain the indexes too.

The engine also writes recovery logs. Index pages may split, use more cache memory and add disk writes. Ten indexes do not make every read ten times faster; a write affecting all ten must maintain ten extra structures.

Measure actual query use before removing an index: a rare month-end report or constraint may still depend on it. An index used to enforce uniqueness is part of correctness as well as read performance.

06Keyset pagination versus OFFSET

Pagination returns a bounded portion of a result instead of every matching row at once. After C27’s newest orders have been returned, the next request needs a continuation rule. An offset skips a count of earlier results; keyset pagination continues after the last ordering key that the client received.

For C27's next page, a cursor can encode the last seen (createdAt, orderId). The next query continues below that tuple in the same ordering. A cursor is a position in a chosen ordering, not necessarily a database transaction kept open between requests.

In a sharded database, first find the shard holding C27’s orders. A local index finds rows within that shard; it does not tell the client which shard to contact. Global searches need a distributed index or queries to several shards. Explain the API query, shard key and local index together.

For a compact example, use two rows per page instead of twenty. Assume createdAt is non-null and never changes, orderId is unique, and all four orders belong to C27:

After returning O402 and O400, the next PostgreSQL query is:

SELECT orderId, createdAt, total
FROM Orders
WHERE customerId = 'C27'
  AND (createdAt, orderId) <
      (TIMESTAMPTZ '2026-09-22 10:00:00+00', 'O400')
ORDER BY createdAt DESC, orderId DESC
LIMIT 2;

It returns O399 and O398. The strict tuple comparison handles the timestamp tie without repeating O400 or skipping O399. This assumes createdAt has type timestamptz and the ID comparison orders O399 before O400; use matching types and ordering in the real schema.

An order inserted with a newer timestamp belongs before this boundary and appears when the user refreshes the first page. A backdated insert may appear on a later page. That is why a stable cursor prevents shifts from newer inserts but does not freeze the dataset. See PostgreSQL's LIMIT and OFFSET documentation.

07Interview example: index customer order history

Interviewer: “How would you make customer order history fast?”

Candidate: “The request filters one customer and returns the newest twenty orders. I would use a composite index with customer first, then descending creation time and an order-ID tie breaker. The database seeks into that customer's range and reads a small ordered slice. A cursor carries the last timestamp and ID for the next page. I accept extra index writes and space, and verify the plan and latency using realistic customer sizes.”

This is more useful than saying “add a B-tree”: it explains which keys the tree contains and which work the query avoids.

A query plan describes the operations the database intends to use, such as an index seek, a table scan or a sort. Inspecting that plan tests whether the engine actually uses the access path the design relies on.

To verify the candidate in PostgreSQL, begin with EXPLAIN on the exact SELECT, including its filter, sort and limit. On a representative test workload, EXPLAIN (ANALYZE, BUFFERS) executes that query and reports actual work. Compare estimated and actual row counts, rows discarded by filters, sort work, buffers touched and table fetches. If estimates are poor, inspect statistics and skew before assuming another index is the answer. Repeat for a large customer and for cold versus warm cache conditions, then measure write cost. These observations test why the index helps; an “Index Scan” label alone is not a success criterion. See using EXPLAIN.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.