Indexes — B-tree, Hash, GIN, BRIN — SQL & Relational Databases

An index is a data structure that the database maintains alongside a table to enable fast lookup of specific rows without scanning the entire table. Without an index, finding all innings where a player scored more than 100 runs requires reading every row in an innings table of 10 million rows and evaluating the condition for each one — an O(n) sequential scan. With a B-tree index on runs_scored, the database traverses a balanced tree to find the qualifying range in O(log n) steps, then reads only the matching rows. Indexes are the primary tool for transforming unacceptably slow queries into acceptably fast ones.

PostgreSQL provides four primary index types, each optimised for a different access pattern. B-tree indexes support equality and range comparisons and are the default and most widely applicable type. Hash indexes support only equality comparisons and are faster for exact lookups than B-tree on very large tables. GIN (Generalised Inverted Index) indexes support full-text search, JSONB containment, and array element lookups. BRIN (Block Range Index) indexes are extremely compact and suitable for naturally ordered large tables like time-series data. Choosing the right index type is as important as deciding to index at all.

Indexes are not free — every index adds write overhead to INSERT, UPDATE, and DELETE operations because the index must be updated alongside the table. An index also consumes disk space (often 10–40% of the indexed column's data size). In write-heavy OLTP tables (high insert rate), too many indexes slow down ingestion without proportionally improving query performance. In read-heavy analytical tables, insufficient indexes cause slow queries. Index design is a deliberate trade-off between read performance, write performance, and storage — not a 'more is always better' decision.

Analogy🏏Cricket

🏏 Think of it like cricket: A SELECT query is precisely how a selection committee picks a playing XI. FROM is the full list of centrally contracted players — the raw pool. WHERE is the fitness and eligibility screen: injured or unavailable players are removed before anyone debates merit, and the fewer names that survive this screen, the faster the meeting goes — exactly why a good WHERE clause matters more than anything downstream. ORDER BY is ranking the survivors by recent form, then by experience as the tiebreaker. LIMIT 11 takes the top of that ranked list and stops. The committee never ranks the entire national player pool and then discards thousands of names — and neither should your query force the database to sort millions of rows it will immediately throw away. The order of operations is the whole game: filter first, sort what remains, take only what you need.