Indexes: Faster Data Lookup Without Scanning Every Row

Suppose a table contains ten million customers and an application needs the record for one email address.

Without a suitable access structure, the database may compare the requested email with row after row until it finds a match. That is a full table scan.

A database index stores selected values in an additional structure designed to locate matching rows more quickly.

The original table remains the source of data. The index acts as an efficient path to it.

A concrete example: a book index

To find a discussion of "transactions" in a 900-page textbook, you could read every page. A book's index instead lists the topic and relevant page numbers.

A database index follows a similar idea:

customer email                row location
---------------------------   ------------
alex@example.com              ...
mira@example.com              ...
zoe@example.com               ...

The database searches the ordered index, finds a pointer or row identifier, and retrieves the record.

Unlike a printed book, a database must keep this index synchronized whenever data changes.

B-tree indexes support ordered lookup

The most common general-purpose database index is based on a balanced tree, usually a B-tree or related structure.

Values are organized into sorted pages with branching paths. The database can repeatedly choose the branch containing the desired range rather than inspect every entry.

B-tree indexes support operations such as:

• Exact equality: email = 'mira@example.com'
• Ranges: price BETWEEN 10 AND 50
• Prefix ordering
• Minimum and maximum values
• Ordered result retrieval

The structure remains balanced as records are inserted and removed, keeping search depth relatively small.

Indexes can support sorting

Consider:

SELECT id, created_at
FROM orders
WHERE customer_id = 1042
ORDER BY created_at DESC
LIMIT 20;

An index on (customer_id, created_at DESC) may let the database jump to that customer's newest orders and return twenty records already in the required order.

Without it, the database might find all matching orders and sort them afterward.

An index can therefore help filtering, ordering, or both.

Composite indexes contain multiple columns

A composite index includes more than one column:

CREATE INDEX orders_customer_status_idx
ON orders (customer_id, status);

Column order matters. This index naturally supports queries beginning with customer_id, including:

• WHERE customer_id = 1042
• WHERE customer_id = 1042 AND status = 'unpaid'

It may not efficiently support WHERE status = 'unpaid' alone because status is not the leading part of the ordered key.

Think of a phone book sorted by surname and then given name. It helps search by surname, but not by given name alone.

Unique indexes enforce identity rules

A unique index prevents duplicate values:

CREATE UNIQUE INDEX customers_email_unique
ON customers (email);

This can support fast lookup and enforce a data rule.

Uniqueness details matter. Should email comparison ignore letter case? Can multiple null values exist? Should deleted accounts reserve old addresses?

The index definition must express the business rule the application actually intends.

Covering indexes can avoid table reads

If an index contains every value required by a query, the database may answer directly from the index.

For example, an index on (customer_id, created_at, total) may cover a query that selects only those fields.

This can reduce storage reads, but wider indexes consume more space and require more maintenance. Adding every potentially useful column would defeat the purpose.

Some databases support included columns that are stored in index leaves without participating in key ordering.

Specialized indexes fit specialized data

Databases may provide:

• Hash indexes for equality lookup
• Full-text indexes for language search
• Spatial indexes for geographic geometry
• Inverted indexes for arrays or document fields
• Bitmap indexes for analytical categories

The exact options depend on the database.

A normal B-tree index is not automatically useful for searching whether a paragraph contains a concept or whether a map shape intersects another. Those operations need data-specific structures.

Every index has a cost

When a row is inserted, updated, or deleted, affected indexes must also change.

Indexes cost:

• Additional storage
• More write operations
• Memory for useful cached pages
• Maintenance during vacuuming or compaction
• Longer backups and restores
• Extra planning choices

A table with too many indexes may read quickly but write slowly. Duplicate or unused indexes create cost without benefit.

Selectivity affects usefulness

Selectivity describes how narrowly a value identifies rows.

An index on a unique email is highly selective. An index on a Boolean active column may divide ten million rows into only two enormous groups.

If a query needs most of a table, reading the table sequentially may be cheaper than jumping between the index and many scattered rows.

The database estimates this tradeoff using statistics about value distribution.

Functions can prevent ordinary index use

This query may not use a normal index on email:

WHERE LOWER(email) = 'mira@example.com'

The query asks about the result of a function rather than the stored value.

Possible solutions include:

• Store normalized email values
• Create an expression index on LOWER(email)
• Use a case-insensitive data type or collation

The right choice depends on database behavior and the intended comparison rules.

Similarly, a leading wildcard such as LIKE '%example.com' cannot usually use an ordinary ordered prefix efficiently.

The query planner decides whether to use an index

Creating an index does not force every matching query to use it.

The planner estimates:

• Number of matching rows
• Cost of table and index reads
• Data distribution
• Available memory
• Sort and join costs

Use EXPLAIN or an equivalent tool to inspect the chosen plan. With an analyzed execution plan, also compare estimated and actual row counts.

Poor estimates may indicate stale statistics or correlated values the planner does not understand.

Design indexes from real queries

A useful workflow is:

1. Identify an important slow query.
2. Measure its current execution plan and timing.
3. Study its filters, joins, ordering, and returned columns.
4. Design the narrowest useful index.
5. measure the new plan with realistic data.
6. Monitor write and storage impact.

Do not create an index for every column by default. Indexes should serve demonstrated access patterns or integrity requirements.

Knowledge check

1. How does an index differ from the original table?
2. Why can a B-tree support both exact and range searches?
3. Why does column order matter in a composite index?
4. What costs occur when a table has more indexes?
5. Why might a database choose a table scan even when an index exists?

The one idea to remember

An index is an additional, maintained path to table data. It can turn expensive scans and sorts into targeted lookups, but it trades storage and write work for those faster reads.