Database Indexing

An index is an additional maintained access path. It can reduce examined records, accessed pages, and sorting, while consuming storage, cache, and write resources. Begin with a concrete query rather than indexing every field.

Pages, scans, and selectivity

Tables are organized into pages processed in memory. An index narrows candidate records before necessary table access. Cache hits, sequential access, and random access differ, so one logical lookup does not imply one physical disk operation.

When a query returns much of a table, a sequential scan can beat many index-directed table fetches. Optimizers consider selectivity, statistics, distribution, and estimated costs.

B-trees and composite order

B-trees maintain ordered branching structures for equality, ranges, and ordering. Small tree height alone does not determine latency: caching, table fetches, and result count still matter.

CREATE INDEX jobs_by_experiment_recent
ON jobs (experiment_id, created_at DESC, id DESC);

SELECT id, state, created_at
FROM jobs
WHERE experiment_id = 42
ORDER BY created_at DESC, id DESC
LIMIT 20;

This index locates an experiment and follows the requested order. Time-only filtering is a different access path. Choose order from equality, range, ordering, and real distribution, not a universal “most selective first” rule. Some engines support skip-scan optimizations, so left-prefix limitations should not be stated as absolute for every implementation.

Covering, partial, and expression indexes

Covering indexes include returned fields and can reduce table access. PostgreSQL’s INCLUDE (state) adds a payload column, but efficient index-only scans also depend on visibility information.

Partial indexes retain a qualifying subset, such as active jobs, and require compatible query predicates. Expression indexes can support lower(email); a normal index does not automatically accelerate arbitrary expressions. See PostgreSQL’s index documentation.

LSM writes and compaction

LSM engines typically record writes in a WAL and memory structure before flushing sorted files. Compaction merges files and obsolete versions; exact ordering and durability depend on the implementation and configuration.

Batching can replace some random updates, but reads may inspect several files or levels. Bloom filters skip files that cannot contain a key. Compaction consumes background resources. Compare read, write, and space amplification and tail latency rather than calling B-trees read-only or LSM write-only.

Specialized structures

Geohash encodes spatial cells, but nearby locations can cross boundaries, requiring neighboring cells. Quadtrees recursively divide space; R-tree families organize bounding regions. PostGIS can use GiST-based indexes. Separate ordinary latitude and longitude indexes do not automatically make radius searches efficient.

Write and maintenance costs

Inserts, updates, and deletes can maintain several indexes, adding logs, cache pressure, and storage. Wide frequently changed covering fields can be costly. Unique indexes also enforce constraints and cannot be removed based solely on read usage.

Observe use and maintenance costs instead of prescribing a fixed maximum index count. Online creation must consider locking, extra space, and cleanup after failures.

Verify execution

EXPLAIN displays a plan. EXPLAIN ANALYZE actually executes the statement, so writes and expensive queries are not harmless inspections.

Check scans, estimated versus actual rows, filtered rows, sorts, temporary files, cache hits, and physical reads. Large estimate errors suggest statistics or skew problems. A faster individual query does not prove better overall performance under writes or cold caches.

Related notes and source

API queries · Data models · Caching · Sharding

Learning reference: Hello Interview · Database Indexing, reviewed through the authenticated written chapter. This guide is independently organized around execution and maintenance costs.