# Database indexing > A database index is an extra data structure that helps the database find rows without scanning the whole table. In system design interviews, choosing indexes connects your API queries to a realistic storage design, and exposes the read speed, write cost, and storage trade-offs. Source: https://sysround.com/concepts/database-indexing Updated: 2026-11-05 ## How database indexing works Start with a query, not a list of columns to index. For example, a photo library might run SELECT id, created_at FROM photos WHERE owner_id = ? ORDER BY created_at DESC, id DESC LIMIT 50. The useful index follows that access pattern: (owner_id, created_at DESC, id DESC). A typical B-tree-family index keeps keys in sorted order across database pages. Internal pages direct a lookup toward the right leaf page; the database then reads matching entries in order. Finding the starting point takes roughly logarithmic work, but returning many matches still requires scanning those entries. Index entries contain indexed values plus a way to locate the row, such as a primary key or physical row reference, depending on the engine. Fetching columns outside the index can require additional table reads. A covering index contains all the values a query needs, potentially avoiding those reads, although some engines still need visibility checks. Composite indexes are ordered lexicographically: first by the first column, then by the second within equal first-column values, and so on. In the photo index, one owner's entries form a contiguous ordered range. Queries on created_at alone generally cannot use it as efficiently; equality conditions on leading columns followed by a range or sort key are a useful starting pattern. The optimizer decides whether an index is cheaper than a table scan using statistics and estimated costs. An index that matches only a few rows can save substantial work, while one matching most of a table may not. Use EXPLAIN and representative data to check the chosen plan, rows scanned, sorting, and table lookups. Writes must maintain relevant index entries as well as the table. Different index structures serve different queries: B-trees support ordered lookups and ranges, hash indexes support equality, inverted indexes support text retrieval, and spatial indexes support geographic queries. Ordinary transactional indexes are usually maintained with the row write; a separate search index updated asynchronously has a different freshness contract. ## Worked example: Paging through a large photo library Suppose a photos table has 100 million rows, and one owner has 80,000 photos. The API returns 50 photos ordered by created_at DESC, id DESC. An index on (owner_id, created_at DESC, id DESC) lets the database seek to that owner's range and read entries in the requested order rather than scan the table and sort the matches. The next-page cursor contains the last photo's timestamp and ID; a matching keyset predicate resumes below that pair. The ID breaks timestamp ties. Fetching captions and object keys may still require table reads, but only for the selected rows. Each new photo also adds an index entry. ## Trade-offs - **Faster reads, more expensive writes.** Every additional index adds maintenance to inserts and deletes, while updates to indexed values also change index entries. - **Storage and memory pressure.** Indexes consume disk space and compete with table data for cache capacity, especially when keys or included columns are wide. - **Coverage versus index size.** Including projected columns can reduce table reads, but makes the index larger and more expensive to maintain. - **Query-specific benefits.** A composite index supports particular filters and ordering, so one index rarely serves every endpoint efficiently. - **Selectivity and result size.** An index cannot make returning millions of matching rows cheap, and broad queries may be faster with a scan. - **Operational rollout cost.** Building an index on a large live table consumes I/O, CPU, and temporary space, and may affect locking or replication lag depending on the engine and build method. ## When to use it in a system design interview - An endpoint needs bounded lookups or ordered pages from a table that will grow large, such as a user's photo history. - A worker repeatedly searches for a small eligible subset, such as pending jobs whose scheduled time has arrived. - Queries filter by several fields, and you need to explain which composite index serves the dominant access pattern. - The design needs database-enforced uniqueness, such as one compatibility edge per pair or one idempotency key per customer. - A slow query is prompting proposals for caching or sharding before anyone has checked its scan and sort costs. ## How to bring it up in the interview - Write the critical query and proposed index together. Explain which predicates narrow the scan, how the index supplies ordering, and whether fetching the result needs table reads. - Justify column order from the query shape rather than saying 'put the most selective column first.' Interviewers may change a filter or introduce a range predicate to test whether the index still works. - Explain what you would validate with EXPLAIN and representative data: estimated versus actual rows, scanned entries, residual filters, sorting, and table fetches. - State the write and storage costs before adding more indexes. Expect follow-ups about frequent updates, wide keys, index builds, and whether a partial index could cover only active rows. - Separate indexing from partitioning. An index reduces work within a shard, but a query that omits the routing key may still contact every shard; interviewers often probe this boundary. ## Common mistakes - Indexing every filtered column separately and assuming the database can combine those indexes as efficiently as a suitable composite index. - Treating composite indexes as unordered sets of columns, or claiming a non-leading column is always either fully usable or completely unusable. - Claiming every indexed query is O(log N) while ignoring matching entries, row fetches, residual filtering, and result size. - Using deep OFFSET pagination and assuming an index avoids walking past the skipped entries; use a stable keyset cursor when the access pattern permits it. - Assuming an index provides concurrency control: a unique index can enforce uniqueness, but preventing double booking or overspending still requires appropriate atomic operations or transactions. ## Interview questions where it comes up - [Design Google Calendar](https://sysround.com/questions/design-google-calendar): Bounded free/busy queries need indexes that narrow by calendar and time while accounting for interval overlap and recurring occurrences. - [Design a price alert system](https://sysround.com/questions/design-price-alert-system): Matching a price change against many alert thresholds requires an ordered access path by instrument and threshold rather than scanning every alert. - [Design a distributed tracing system](https://sysround.com/questions/design-distributed-tracing): Trace-ID lookup and searches by span attributes require distinct index choices with explicit ingestion, storage, and freshness costs. - [Design Google Photos](https://sysround.com/questions/design-google-photos): Browsing and filtering a large personal library depends on metadata indexes that support owner-scoped queries and stable pagination. - [Design a parts compatibility feature](https://sysround.com/questions/design-parts-compatibility): Fast compatibility checks and discovery in both directions require deliberate composite indexes over sparse relationship data. - [Design a distributed job scheduler](https://sysround.com/questions/design-job-scheduler): Finding due occurrences without scanning all scheduled work requires an index aligned with eligibility state and execution time. ## FAQ ### How do database indexes make queries faster? They provide a smaller, organized access path to matching rows instead of requiring a full table scan. An ordered index can also supply the requested sort order, and a covering index may avoid fetching table rows. The benefit depends on how many entries and rows the query still needs to read. ### What is the difference between a single-column and a composite index? A single-column index organizes entries by one value; a composite index organizes them by an ordered tuple of values. For example, (owner_id, created_at) supports looking up one owner's photos in time order. It generally does not serve a global time-range query as efficiently as an index beginning with created_at. ### When should you not add a database index? Avoid adding one without an important query or constraint that benefits from it. Small tables, queries returning most rows, and write-heavy workloads may gain little relative to the maintenance cost. Check for an existing index that already serves the access pattern, and validate the plan before adding another. ## Related concepts - [B-trees](https://sysround.com/concepts/b-tree) - [LSM trees](https://sysround.com/concepts/lsm-tree) - [Inverted index](https://sysround.com/concepts/inverted-index) - [Pagination](https://sysround.com/concepts/pagination) --- SysRound (https://sysround.com) is an AI practice tool for system design interviews: a voice or typed AI interviewer, a shared whiteboard, then feedback on every skill and a model answer. Its feedback is AI-generated and can be wrong.