Database Indexing Strategy: B-Trees, Hash Indexes, and More

An index is an extra data structure that the database maintains alongside the main table — much like the index at the back of a book. Think about looking up a word in a thick dictionary without one: you would have to flip through every page one by one. With an index, you jump straight to the right page.

The same idea applies to databases. Without an index, the database has to read every row from top to bottom to find what you are looking for — a process called a full table scan. An index lets the database jump directly to the right location, turning a query that once took several seconds into one that finishes in milliseconds.

However, indexes are not free. Every index you create stores a copy of part of your data in an optimized structure, which means it uses extra storage. More importantly, every INSERT, UPDATE, or DELETE forces the database to update not just the table but every index on it too. The more indexes you have, the heavier your write operations become. A table buried under rarely-used indexes can actually slow your application down. The practical rule is simple: create indexes only for queries you actually run. Start with the slowest and most frequent queries — your database’s slow query log is the best place to find them. Columns that appear in WHERE, JOIN ON, or ORDER BY clauses are your primary candidates. Measure first, then decide.

Table of Contents

• Start with evidence
• Common index types
• Composite indexes follow query order
• Covering, partial, and unique indexes
• Keep indexes healthy
• Read the execution plan first
• Column order in a composite index
• Selectivity and low-cardinality columns
• Indexes enforce correctness too
• Write cost, maintenance, and safe rollout
• Pagination and index-friendly queries
• FAQ

Start with evidence

Capture a real slow query and inspect its execution plan with your database tooling, such as EXPLAIN ANALYZE. Check how many rows are read, which filters and joins are used, and whether the result must be sorted. Measure before and after adding an index; a plan is more trustworthy than intuition.

Common index types

B-tree indexes are the default in most relational databases. They support equality, ranges, and ordered results, so they fit WHERE created_at >= ..., primary keys, and many foreign keys. Hash indexes are specialized for equality lookups and usually do not help range queries. Databases also provide types such as full-text, JSON, spatial, or inverted indexes for specific data and operators.

Composite indexes follow query order

Suppose the common query is:

SELECT id, total
FROM orders
WHERE customer_id = ? AND status = ?
ORDER BY created_at DESC
LIMIT 20;

An index beginning with (customer_id, status, created_at) can support the filter and ordering. The leftmost columns matter: the same index is much less useful for a query that filters only by status. Prefer a small number of indexes that match important access paths over every possible combination.

Covering, partial, and unique indexes

A covering index may include all columns needed by a frequent query, avoiding table reads. A partial index stores only rows matching a condition, such as active accounts, and can be smaller and faster. A unique index is not just an optimization: it makes a business invariant—such as one subscription per customer—enforceable under concurrency.

Keep indexes healthy

Review unused and duplicate indexes, especially after feature changes. Index selective predicates first when possible, avoid wrapping indexed columns in functions unless you have an expression index, and paginate deep lists with a cursor rather than a large offset. Finally, test on production-like data: an index that looks useful on 1,000 rows may not help at 10 million.

Conclusion

Treat indexing as an ongoing feedback loop: observe a workload, inspect the plan, make one change, and measure its cost. That discipline prevents both slow reads and an over-indexed write path.

Read the execution plan first

An index is only useful when the optimizer can use it for the actual query. Before adding one, capture the query with realistic parameters and inspect the plan. In PostgreSQL, EXPLAIN (ANALYZE, BUFFERS) is especially useful because it shows what really happened, not only what the planner predicted.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, total, created_at
FROM orders
WHERE customer_id = 42
  AND status = 'paid'
ORDER BY created_at DESC
LIMIT 20;

Look for four signals:

• Rows scanned versus rows returned. Reading 100,000 rows to return 20 is usually a warning.
• Scan type. A sequential scan can be correct for a small table, but may be expensive on a large selective query.
• Sort and join work. An index can sometimes provide the order required by ORDER BY or make a join cheaper.
• Estimated versus actual rows. A large mismatch suggests stale statistics or a data distribution the optimizer does not understand.

Do not treat every sequential scan as a failure. If a query returns most of a small table, reading the whole table can be cheaper than bouncing through an index and fetching many scattered rows.

Column order in a composite index

Composite indexes are where many otherwise sensible indexing attempts fail. A B-tree index is ordered from left to right. For an index on (customer_id, status, created_at), the database can efficiently use the leading customer_id, then narrow by status, then read matching rows in created_at order.

The best order depends on the query shape, not a universal “most selective column first” rule. Equality conditions commonly come first; a range condition such as created_at >= ... generally ends the useful ordered prefix; columns used only for display may be included rather than placed in the key.

For example, these two access patterns usually deserve different indexes:

-- customer history
WHERE customer_id = ? ORDER BY created_at DESC

-- operational queue
WHERE status = 'pending' ORDER BY created_at ASC

Trying to satisfy both with one wide index often produces a compromise that helps neither enough. Confirm with plans and workload frequency before keeping both.

Selectivity and low-cardinality columns

Selectivity describes how much a condition reduces the candidate rows. A boolean column such as is_active often has low selectivity: if 90 percent of rows are active, a plain index on it may not help. A partial index can be better when the minority set matters:

CREATE INDEX CONCURRENTLY idx_orders_pending_created_at
ON orders (created_at)
WHERE status = 'pending';

This index is smaller than indexing every order and directly supports a worker that repeatedly asks for pending orders. The condition must match the query predicate closely, so verify it with an execution plan.

Indexes enforce correctness too

Use unique indexes for invariants that must survive concurrent requests. Application-level “check, then insert” code can race; two requests can both see no existing row. A unique constraint makes the database arbitrate the conflict.

CREATE UNIQUE INDEX users_email_unique
ON users (lower(email));

The expression index above also makes case-insensitive email lookup efficient when the query uses the same expression. Decide how to translate a uniqueness violation into a user-facing response, rather than assuming validation before the write is enough.

Write cost, maintenance, and safe rollout

Every insert writes to every relevant index. Updates may also rewrite index entries, and deletes leave work for vacuuming or maintenance. Wide indexes cost more memory and storage; redundant indexes make writes slower with little benefit. Review indexes after feature changes and remove duplicates only after confirming they are not supporting another query or constraint.

On a busy production table, index creation itself can block or consume substantial resources. Use the online or concurrent index-creation mechanism provided by your database, schedule the operation carefully, and monitor its progress. Test migration time on a production-like copy of the data. An index that is correct technically can still be an unsafe deployment if it locks a critical table at peak traffic.

Pagination and index-friendly queries

Large OFFSET values force the database to find and discard earlier rows. The first few pages may look fine, but page 500 can become expensive because the database still has to walk through the previous rows before returning the next 50.

-- Easy to write, but increasingly expensive for deep pages.
SELECT id, created_at, message
FROM events
WHERE account_id = $1
ORDER BY created_at DESC, id DESC
LIMIT 50 OFFSET 25000;

For an activity feed, use keyset pagination with a stable cursor instead. The cursor is usually the last row from the previous page, such as created_at plus id:

SELECT id, created_at, message
FROM events
WHERE account_id = $1
  AND (created_at, id) < ($2, $3)
ORDER BY created_at DESC, id DESC
LIMIT 50;

An index on (account_id, created_at DESC, id DESC) matches this query well. The extra id creates a stable order when timestamps tie, so the next page does not skip or duplicate rows with the same created_at value.

CREATE INDEX CONCURRENTLY idx_events_account_feed
ON events (account_id, created_at DESC, id DESC);

At the API layer, return the last row as an encoded cursor:

{
  "items": [
    { "id": 8842, "created_at": "2026-09-09T10:15:00Z", "message": "..." }
  ],
  "next_cursor": "2026-09-09T10:15:00Z|8842"
}

Cursor-based pagination is best for feeds, audit logs, notifications, and other “next page” flows. Keep OFFSET for small admin tables or cases where users truly need to jump to an exact page number.

FAQ

Should every foreign key have an index?

Usually, yes—especially when parent rows are deleted or updated and the database must find referencing rows. Check the database documentation and query plans, because some systems or schemas create supporting indexes automatically while others do not.

Can I rely on an ORM to create the right indexes?

An ORM can declare indexes, but it cannot know which application queries are slow or important. Keep index definitions in migrations, then validate them against real workloads.

When should I remove an index?

Remove it when monitoring shows it is unused or duplicated and it is not enforcing a constraint. Make the change deliberately, observe the workload afterward, and keep a rollback plan.