Database Indexing: B-Tree, Hash, GIN, & GiST

Without an index, executing SELECT * FROM users WHERE email = 'alice@example.com' forces the database query planner to execute a Sequential Scan (Seq Scan), checking every row from disk page 0 to page $N$.

Index Lookups create a pre-sorted self-balancing tree structure mapping column keys to disk physical row location pointers (TIDs - Tuple IDs).

The query engine traverses the index tree in sub-millisecond time ($O(\log N)$), fetches the exact TID, and retrieves the row page directly (Index Scan). For query performance optimization, review optimizing postgresql query performance explain analyze and postgres partitioning vs sharding.

PostgreSQL provides specialized index data structures tailored for distinct data types and search operators:

1. B-Tree (Default): Balanced tree handling equality (=) and range queries (<, <=, >, >=, BETWEEN, ORDER BY). 2. Hash Index: Optimized exclusively for exact equality (=) lookups with smaller index sizes than B-Trees. 3. GIN (Generalized Inverted Index): Designed for composite values containing multiple elements, such as JSONB documents, arrays, or full-text search tsvector columns (WHERE data @> '{"status": "active"}'). 4. GiST (Generalized Search Tree): Handles geometric data, PostGIS spatial queries (ST_DWithin), and overlapping range types (daterange).

Advanced indexing patterns reduce disk I/O and index footprint sizes:

- Covering Indexes (INCLUDE): Includes non-search payload columns inside the B-Tree leaf nodes (CREATE INDEX idx_user_email ON users(email) INCLUDE (first_name)). This enables Index-Only Scans, fetching results directly from the index without reading table heap pages. - Partial Indexes: Indexes only a filtered subset of rows (CREATE INDEX idx_active_orders ON orders(user_id) WHERE status = 'PENDING'). Reduces index storage size by 90%+. - Expression Indexes: Indexes computed function results (CREATE INDEX idx_lower_email ON users(LOWER(email))) to support case-insensitive lookups.

Over time, frequent row updates and deletions cause Index Bloat (fragmented, half-empty B-Tree pages that waste memory and disk IOPS).

### 1. Identifying Unused Indexes Query pg_stat_user_indexes to find indexes with zero scans (idx_scan = 0) that waste write performance:

1SELECT relname, indexrelname, idx_scan, pg_size_pretty(pg_relation_size(indexrelid))2FROM pg_stat_user_indexes3WHERE idx_scan = 0 AND idxname NOT LIKE '%_pkey';

### 2. Zero-Downtime Reindexing Rebuild bloated indexes concurrently without locking concurrent table reads or writes: REINDEX INDEX CONCURRENTLY idx_orders_user_id;