Sharon Ben-Moshe is the founder of sqlfmt, a browser-based SQL formatter and validator with misspelled-keyword suggestions across PostgreSQL, MySQL, SQLite, SQL Server, and BigQuery.
Understand database indexing from first principles. Compare B-Trees, Hash, GiST, and GIN index structures, composite column ordering, and write costs.
Quick answer
A database index is an auxiliary data structure (most commonly a self-balancing B-Tree) that allows the database engine to find specific rows in O(log N) logarithmic time rather than performing a full O(N) sequential table scan. Secondary index structures store sorted search keys alongside tuple identifiers (pointers) that reference the underlying table heap.
A B-Tree (balanced tree) organizes data into 8KB disk pages arranged in a hierarchy of root, branch, and leaf nodes. Leaf nodes contain ordered key values and physical row pointers (TIDs/RIDs), connected via a doubly-linked list. Searching navigates from root to leaf in O(log N) time, while range scans traverse the leaf linked list directly.
What is the difference between a clustered and non-clustered index?
A Clustered Index (InnoDB primary key or SQL Server clustered index) dictates the physical storage order of the actual table rows on disk. A table can have only ONE clustered index. Non-clustered (secondary) indexes store key columns alongside pointers back to the clustered key or heap row.
What is write amplification in database indexing?
Every time application code executes an INSERT, UPDATE, or DELETE, the database must update not only the table heap but every single index containing modified columns. Adding 10 indexes to a table multiplies write I/O ten-fold, slows down transactions, and creates index bloat.
When should you use a GIN index instead of a B-Tree?
Use a Generalized Inverted Index (GIN) when indexing composite or multi-valued types—such as PostgreSQL JSONB documents, arrays, or full-text search tsvector columns. GIN maps internal elements back to parent rows, enabling high-performance containment (@>) queries.
Indexes are the single most critical architectural component dictating whether a database responds in 2 milliseconds or crashes under traffic spikes. Understanding physical index mechanics allows engineers to design lean, surgical schemas without wasteful index proliferation.
Key takeaways
B-Trees offer logarithmic O(log N) search and O(log N + K) range scans via leaf-node linked lists.
Clustered indexes define the physical table row order on disk; secondary indexes store pointers back to rows.
In composite indexes, the leftmost prefix rule dictates query usability: Equality first, Range second.
Every index incurs write amplification, WAL generation, disk storage, and memory buffer pool consumption.
The index family across modern database engines
Relational databases provide multiple specialized index access methods designed for distinct data topologies:
B-Tree (Default): The standard workhorse. Handles equality (=), range comparisons (<, <=, >, >=), and sorting (ORDER BY).
Hash Index: O(1) exact equality lookups. Does not support range queries, sorting, or multi-column partial matches.
GIN (Generalized Inverted Index): Essential for JSONB, array elements, and full-text search containment.
GiST (Generalized Search Tree): Geometric, spatial (PostGIS), and range data types (e.g. overlapping timestamp ranges).
BRIN (Block Range Index): Compact metadata indexes for massive append-only tables (storing min/max values per disk block).
Anatomy of an Index-Only Scan (Covering Indexes)
When a query requires columns that are not part of the search key, the database must execute an expensive 'Heap Fetch' or 'Bookmark Lookup' for every matching row. By storing extra columns in the leaf nodes using `INCLUDE`, the engine never touches the table heap:
Eliminating heap fetches with covering index
-- Without INCLUDE: Engine finds customer_id in index, then visits table heap for order_totalCREATE INDEX idx_orders_cust ON core.orders (customer_id);-- WITH INCLUDE: Eliminates table heap lookup completely (Index Only Scan)CREATE INDEX idx_orders_cust_coveringON core.orders (customer_id)INCLUDE (order_date, order_total);-- Queries executed entirely in memory from index leaf pages:SELECT customer_id, order_date, order_totalFROM core.ordersWHERE customer_id = 42;
The hidden cost of indexing: Write amplification
Indexes are not free. Consider a high-velocity telemetry table with 12 indexes: an insert of 1 row generates 13 random write operations across distinct disk blocks. Best practices dictate:
Audit unused indexes using pg_stat_user_indexes or sys.dm_db_index_usage_stats.
Drop redundant single-column indexes covered by existing composite indexes.
Prefer partial indexes (WHERE is_active = true) for skewed distributions.