SQL 72 🛢️ Database Indexes Concepts
A table without an index is a book without a table of contents. Every query that needs to find a specific row must read the entire table from the first row to the last. For a table with a thousand rows, that is unnoticeable. For a table with a hundred million rows, that is a disaster. Database indexes solve this problem by maintaining a separate, ordered data structure that maps column values to the physical locations of the rows that contain them. The database engine can then navigate directly to the matching rows instead of scanning everything. The concept is simple, but the design decisions around indexes are some of the most consequential choices a database developer makes, because every index accelerates reads while simultaneously taxing every write.
Key point: An index is not free. It is a permanent, automatically maintained data structure that the database must update on every insert, update, and delete. The question is never whether an index is “good” in the abstract, but whether the queries it accelerates justify the write cost it imposes.
Why indexes exist
The full table scan problem. Without an index, the database has exactly one way to answer a query with a filter: read every row, check the condition, and return the matches. This is called a sequential scan or full table scan. For a small table it is fine. For a large table it is catastrophic. A query that should take milliseconds can take minutes because the engine is spending nearly all its time reading rows it will ultimately discard.
The random I/O problem. Suppose the database did try to be clever and only read the pages that contained matching rows. Without an index, it has no way of knowing which pages those are. It would have to check every page. An index solves this by storing a sorted mapping from values to locations, so the engine can compute exactly which pages to read. This turns a page-by-page search into a directed lookup.
The sorted order problem. Many queries do not just filter; they also sort. ORDER BY price, ORDER BY created_at DESC, and paginated results all require data in a specific sequence. Without an index, the database must read all matching rows and then sort them in memory or on disk. A B-tree index stores its entries in sorted order, so the engine can walk the index and retrieve rows already in the requested sequence, eliminating the sort entirely.
The join problem. When two tables are joined, the database must find matching rows in one table for every row in the other. Without indexes on the join columns, each lookup becomes a full scan. With indexes, each lookup is a logarithmic descent. For a join between a million-row table and a ten-thousand-row table, the difference is between ten thousand full scans and ten thousand index lookups. The latter is orders of magnitude faster.
The constraint problem. Indexes do not only accelerate queries. A unique index enforces that no two rows share a value. A primary key is a unique index that also serves as the table’s primary identifier. When you declare a primary key or a unique constraint, the database creates an index to enforce it. This means the index is serving two purposes: correctness and performance.
The write amplification trade-off. Every index must be updated whenever the underlying table changes. An INSERT into a table with five indexes is not one write; it is six. The heap row is written once, and each index is updated separately. Each index update traverses the index structure, finds the correct position, and writes the new entry. If a page splits, the cost is higher. At high ingestion rates, this write amplification becomes the dominant cost of the database.
a. How B-tree indexes work
The B-tree is the default index structure in every major relational database. PostgreSQL, MySQL, SQL Server, and Oracle all use B-tree or its variant, the B+Tree, for their general-purpose indexes. The structure is chosen because it provides logarithmic lookup time, efficient range scans, and sorted traversal, all while remaining balanced as data grows.
The tree structure
A B+Tree is a balanced tree with a high branching factor. Each node holds many keys, not just one or two. The root node contains keys that partition the search space. Each internal node contains keys that further partition its subtree. The leaf nodes contain the actual entries, pointing to rows in the table. Crucially, the leaf nodes are linked together in a sorted linked list, so a range scan can walk from one leaf to the next without revisiting the internal nodes.
-- Conceptual B+Tree structure for an index on orders(order_date)
-- Root: [2023-01-01, 2024-01-01, 2025-01-01]
-- / | \
-- Internal: [...] Internal: [...] Internal: [...]
-- | | |
-- Leaf: 2022-12-01 → 2022-12-15 → 2023-01-03 → 2023-02-01 → ...
-- (each leaf entry points to the physical row location)A point lookup for order_date = '2024-06-15' starts at the root, compares the key, follows the appropriate child pointer, descends one level, repeats, and reaches the leaf containing the entry. The number of disk reads equals the tree height, typically three or four levels even for tables with hundreds of millions of rows.
Equality and range queries
The B-tree handles both equality and range queries efficiently. An equality lookup descends to the leaf and returns the match. A range query descends to the first matching leaf, then follows the leaf-to-leaf links until the range is exhausted.
-- Equality: fast descent to one leaf
SELECT * FROM users WHERE email = 'alice@example.com';
-- Range: descent to first matching leaf, then sequential walk
SELECT * FROM orders
WHERE order_date BETWEEN '2026-01-01' AND '2026-01-31';
-- Sorted retrieval: no sort needed, the index is already ordered
SELECT * FROM products ORDER BY price;This is why the B-tree is the default. It supports =, <, <=, >, >=, BETWEEN, IN, and IS NULL, and it can satisfy ORDER BY clauses without a separate sort step.
The high branching factor
The key to the B-tree’s shallow height is its high branching factor. Each node holds hundreds of keys, not just two. A node that fits in one 8 KB page might hold 200 key-pointer pairs. With a branching factor of 200, a tree of height four can index 200⁴ = 1.6 billion entries. This means that even for the largest tables, a lookup requires only three or four disk reads. The tree stays balanced because node splits and merges keep all leaves at the same depth.
The cost of writes
Inserting a row into a B-tree index is not free. The engine must descend to the correct leaf, insert the entry, and if the leaf is full, split it. A split creates a new leaf, moves half the entries into it, and updates the parent node’s pointer. If the parent is also full, the split cascades upward. In the worst case, a single insert can trigger splits all the way to the root, though this is rare because the tree is designed to keep nodes partially empty.
-- Inserting a row requires updating every index on the table
INSERT INTO orders (order_date, customer_id, total)
VALUES ('2026-06-15', 42, 99.99);
-- If indexes exist on order_date and customer_id:
-- 1. Heap insert: write the row.
-- 2. Index insert on order_date: descend, insert, maybe split.
-- 3. Index insert on customer_id: descend, insert, maybe split.
-- Total: three write operations, not one.b. How hash indexes work
A hash index takes a different approach. Instead of maintaining a sorted tree, it computes a hash value for each index key and stores entries in buckets based on that hash. The goal is O(1) average lookup time for exact equality matches, versus O(log n) for a B-tree.
The bucket structure
A hash index is an array of buckets. Each bucket contains a linked list of entries that hash to the same value. When a lookup specifies an exact key, the engine computes the hash, goes directly to the bucket, and scans the short list for the matching entry. If the bucket count is well-chosen, the list is short and the lookup is effectively constant time.
-- Hash index on users(username) for exact lookups
-- Hash('alice') → bucket 7
-- Hash('bob') → bucket 12
-- Hash('carol') → bucket 3
-- Lookup: O(1) average
SELECT * FROM users WHERE username = 'alice';
-- Engine hashes 'alice', goes to bucket 7, finds the entry.Why hash indexes are limited
A hash index has no concept of ordering. It cannot answer range queries. WHERE price > 100 is impossible because the hash values of 100, 101, and 102 are unrelated. A hash index cannot support ORDER BY. It cannot support BETWEEN. It cannot enforce a unique constraint in PostgreSQL’s implementation. Its only strength is exact equality.
-- These queries cannot use a hash index:
SELECT * FROM products WHERE price > 100; -- range
SELECT * FROM orders ORDER BY created_at; -- sorting
SELECT * FROM users WHERE age BETWEEN 20 AND 30; -- range
-- All of them fall back to a sequential scan or a different index.Hash collisions and bucket count
When two different keys hash to the same bucket, the bucket’s linked list grows. The lookup speed depends on the average chain length. Too few buckets means long chains and slower lookups. Too many buckets means wasted memory and slower full scans. Microsoft’s guidance suggests keeping the bucket count within ten times the actual number of distinct keys, and overestimating is safer than underestimating.
-- SQL Server hash index (memory-optimized tables only)
ALTER TABLE MyTable_memop
ADD INDEX ix_hash_Column2 UNIQUE HASH (Column2)
WITH (BUCKET_COUNT = 64);
-- BUCKET_COUNT should be roughly the number of distinct values.
-- 1000 distinct usernames → BUCKET_COUNT around 1000 to 10000.When hash indexes are appropriate
The B-tree is so versatile that hash indexes are rarely the right choice for general-purpose work. PostgreSQL’s own documentation notes that there is insufficient evidence that hash indexes are faster than B-trees even for equality comparisons. Hash indexes are primarily useful in memory-optimized tables where the entire index fits in memory and the workload is pure equality lookups with no range or sort requirements.
c. Index selectivity and cardinality
Not all indexes are equally useful. The value of an index depends on how many rows match a typical lookup. If an index returns half the table, the database may be better off scanning the table sequentially. If it returns one row out of a million, the index is immensely valuable. This concept is called selectivity.
What cardinality means
Cardinality refers to the number of distinct values in a column. A primary key column has high cardinality: every value is unique. A boolean column has cardinality two: true and false. A status column with five possible values has cardinality five. High cardinality means an index lookup on a specific value will match few rows. Low cardinality means many rows share the same value, and the index is less discriminating.
-- High cardinality: email column, nearly all values unique.
-- An index on email is highly selective.
SELECT * FROM users WHERE email = 'alice@example.com';
-- Likely returns 1 row.
-- Low cardinality: is_active column, only true/false.
-- An index on is_active alone is nearly useless.
SELECT * FROM users WHERE is_active = true;
-- Might return half the table. Sequential scan is faster.The selectivity calculation
The database’s query optimizer uses statistics to estimate how many rows a query will return. If the estimate is a small fraction of the table, the optimizer chooses an index scan. If the estimate is large, it chooses a sequential scan. The statistics include the number of rows, the number of distinct values, and histograms of value distribution.
-- Optimizer decision logic (simplified):
-- Estimated rows = Total rows × Selectivity
-- Selectivity of an equality predicate ≈ 1 / Cardinality
--
-- Table: 1,000,000 rows
-- Index on email (cardinality 1,000,000):
-- Estimated rows = 1,000,000 × (1/1,000,000) = 1
-- Optimizer chooses index scan.
--
-- Index on is_active (cardinality 2):
-- Estimated rows = 1,000,000 × (1/2) = 500,000
-- Optimizer chooses sequential scan.The partial index solution
When a column has low cardinality but queries always filter on a specific value, a partial index can help. A partial index only includes rows that match a WHERE condition. If a table has a status column and most rows are processed, but queries always look for pending, a partial index on status where status = 'pending' is far more selective than a full index.
-- Full index on status: low selectivity, mostly useless.
CREATE INDEX idx_status ON orders(status);
-- Partial index: only indexes the small subset that matters.
CREATE INDEX idx_pending ON orders(created_at)
WHERE status = 'pending';
-- Queries that filter on status = 'pending' can use the partial index.
-- The index is a fraction of the size and far more selective.
SELECT * FROM orders
WHERE status = 'pending' AND created_at > '2026-01-01';The partial index is smaller, cheaper to maintain, and fits more easily in memory. The optimizer uses it only when the query includes the matching predicate, which is exactly the case the index was designed for.
The write cost of low-selectivity indexes
A low-selectivity index is doubly bad. It rarely helps queries because the optimizer often ignores it in favor of a sequential scan. But it still imposes the full write cost on every insert, update, and delete. A boolean column index on a table with millions of rows is almost pure overhead: it slows down writes and accelerates almost nothing.
Complete Example Session
-- ============================================
-- PART 1: THE SCENARIO
-- ============================================
-- An orders table with realistic dimensions.
CREATE TABLE orders (
order_id BIGSERIAL PRIMARY KEY,
customer_id INT NOT NULL,
order_date DATE NOT NULL,
status VARCHAR(20) NOT NULL,
total DECIMAL(10,2) NOT NULL
);
-- Insert 1,000,000 rows (conceptually; in practice, generate_series).
-- Distribution:
-- customer_id: 50,000 distinct customers (high cardinality)
-- order_date: 5 years of dates (high cardinality)
-- status: 'pending', 'shipped', 'delivered', 'cancelled' (cardinality 4)
-- total: random values
-- ============================================
-- PART 2: NO INDEXES — SEQUENTIAL SCAN
-- ============================================
-- Find all orders for a specific customer.
EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 42;
-- Output (conceptual):
-- Seq Scan on orders (cost=0.00..45000.00 rows=20 width=50)
-- Filter: (customer_id = 42)
-- Rows Removed by Filter: 999980
-- Planning Time: 0.2 ms
-- Execution Time: 850.0 ms
-- The engine read 1,000,000 rows to find 20.
-- 99.998% of the work was wasted.
-- ============================================
-- PART 3: ADD A B-TREE INDEX
-- ============================================
CREATE INDEX idx_orders_customer
ON orders(customer_id);
-- Run the same query.
EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 42;
-- Output (conceptual):
-- Index Scan using idx_orders_customer on orders
-- (cost=0.43..8.45 rows=20 width=50)
-- Index Cond: (customer_id = 42)
-- Planning Time: 0.3 ms
-- Execution Time: 0.8 ms
-- The engine descended the B-tree, found the matching entries,
-- and fetched the rows. 0.8 ms instead of 850 ms.
-- Improvement: over 1000×.
-- ============================================
-- PART 4: RANGE QUERY ON THE SAME INDEX
-- ============================================
-- Find orders in a date range.
EXPLAIN ANALYZE
SELECT * FROM orders
WHERE order_date BETWEEN '2026-01-01' AND '2026-01-31';
-- Without an index on order_date: sequential scan.
-- With an index on order_date:
CREATE INDEX idx_orders_date ON orders(order_date);
EXPLAIN ANALYZE
SELECT * FROM orders
WHERE order_date BETWEEN '2026-01-01' AND '2026-01-31';
-- Output (conceptual):
-- Index Scan using idx_orders_date on orders
-- Index Cond: (order_date >= '2026-01-01' AND order_date <= '2026-01-31')
-- Execution Time: 2.1 ms
-- The B-tree descended to the first matching leaf and walked
-- the leaf chain until the range was exhausted.
-- ============================================
-- PART 5: THE LOW-CARDINALITY TRAP
-- ============================================
-- Create an index on the status column.
CREATE INDEX idx_orders_status ON orders(status);
-- Query for pending orders.
EXPLAIN ANALYZE
SELECT * FROM orders WHERE status = 'pending';
-- Output (conceptual):
-- Seq Scan on orders (cost=0.00..45000.00 rows=250000 width=50)
-- Filter: (status = 'pending'::text)
-- Rows Removed by Filter: 750000
-- Execution Time: 620.0 ms
-- The optimizer ignored the status index.
-- Reason: 'pending' matches 25% of the table.
-- An index scan would read 250,000 index entries
-- and then 250,000 heap pages (random I/O).
-- A sequential scan reads all 1,000,000 rows in order.
-- For 25% selectivity, sequential scan wins.
-- ============================================
-- PART 6: THE PARTIAL INDEX SOLUTION
-- ============================================
-- The problem: status has cardinality 4, and 'pending' is common.
-- But what if the application almost always queries pending orders
-- in date order, and pending orders are only 5% of the table?
-- Drop the useless full index.
DROP INDEX idx_orders_status;
-- Create a partial index.
CREATE INDEX idx_orders_pending_date
ON orders(order_date)
WHERE status = 'pending';
-- Query with the matching predicate.
EXPLAIN ANALYZE
SELECT * FROM orders
WHERE status = 'pending' AND order_date > '2026-06-01';
-- Output (conceptual):
-- Index Scan using idx_orders_pending_date on orders
-- Index Cond: (order_date > '2026-06-01')
-- Filter: (status = 'pending')
-- Execution Time: 1.5 ms
-- The index only contains pending orders (5% of the table).
-- It is 20× smaller than a full index.
-- It fits in memory.
-- Every lookup is highly selective.
-- ============================================
-- PART 7: COMPOSITE INDEXES
-- ============================================
-- A common query pattern: filter by customer AND sort by date.
SELECT * FROM orders
WHERE customer_id = 42
ORDER BY order_date DESC;
-- With separate indexes on customer_id and order_date:
-- The engine uses idx_orders_customer, finds 20 rows,
-- then sorts them by date.
-- A composite index on (customer_id, order_date) is better.
CREATE INDEX idx_orders_customer_date
ON orders(customer_id, order_date DESC);
-- Now the index stores entries sorted by customer_id first,
-- then by order_date within each customer.
-- The engine finds customer 42's entries already in date order.
-- No sort needed.
EXPLAIN ANALYZE
SELECT * FROM orders
WHERE customer_id = 42
ORDER BY order_date DESC;
-- Output (conceptual):
-- Index Scan using idx_orders_customer_date on orders
-- Index Cond: (customer_id = 42)
-- Execution Time: 0.5 ms
-- The "Order By" step is eliminated entirely.
-- ============================================
-- PART 8: THE WRITE COST OF INDEXES
-- ============================================
-- Measure the cost of inserts with different index counts.
-- Table with no indexes (except primary key):
-- INSERT 10,000 rows → 0.8 seconds.
-- Table with 3 indexes:
-- INSERT 10,000 rows → 2.1 seconds.
-- Table with 6 indexes:
-- INSERT 10,000 rows → 4.5 seconds.
-- The pattern: each index adds roughly 0.6 seconds per 10,000 inserts.
-- The insert rate scales inversely with index count.
-- 10,000 inserts/sec with 1 index → ~3,300 inserts/sec with 6 indexes.
-- ============================================
-- PART 9: COVERING INDEXES
-- ============================================
-- A query that only needs indexed columns.
SELECT customer_id, order_date
FROM orders
WHERE customer_id = 42;
-- With a covering index:
CREATE INDEX idx_orders_covering
ON orders(customer_id, order_date, total);
-- The index contains all three columns.
-- The engine can answer the query entirely from the index.
-- No heap access needed.
EXPLAIN ANALYZE
SELECT customer_id, order_date
FROM orders
WHERE customer_id = 42;
-- Output (conceptual):
-- Index Only Scan using idx_orders_covering on orders
-- Index Cond: (customer_id = 42)
-- Heap Fetches: 0
-- Execution Time: 0.3 ms
-- "Index Only Scan" means the heap was never touched.
-- The index itself contains all the data the query needs.
-- ============================================
-- PART 10: INDEX MAINTENANCE AND BLoat
-- ============================================
-- Over time, indexes accumulate bloat from updates and deletes.
-- PostgreSQL: REINDEX or pg_repack.
-- MySQL: OPTIMIZE TABLE.
-- SQL Server: ALTER INDEX ... REBUILD.
-- Check index size and usage (PostgreSQL):
SELECT
indexrelname AS index_name,
pg_size_pretty(pg_relation_size(indexrelid)) AS size,
idx_scan AS times_used
FROM pg_stat_user_indexes
WHERE relname = 'orders'
ORDER BY pg_relation_size(indexrelid) DESC;
-- Result:
-- index_name | size | times_used
-- ------------------------+--------+-----------
-- idx_orders_customer | 35 MB | 1250000
-- idx_orders_date | 42 MB | 890000
-- idx_orders_customer_date| 48 MB | 450000
-- idx_orders_covering | 55 MB | 12000
-- idx_orders_pending_date | 3 MB | 780000
-- The covering index is the largest but least used.
-- The partial index is tiny but heavily used.
-- This is the data needed to decide which indexes to keep.The ten parts walked through the full lifecycle of index design: the sequential scan problem, the B-tree solution for equality and range queries, the low-cardinality trap, partial indexes, composite indexes for sort elimination, write cost measurement, covering indexes, and maintenance. The same orders table and query patterns threaded through every part, showing how each design decision changes the outcome.
Quick Reference
Index Types and Their Query Support
| Index Type | Equality | Range | Sort | Unique | Typical Use |
|---|---|---|---|---|---|
| B-tree | Yes | Yes | Yes | Yes | General purpose, default |
| Hash | Yes | No | No | No | Memory-optimized, exact lookups |
| GIN | Yes | No | No | No | Full-text, JSONB, arrays |
| GiST | Yes | Yes | No | No | Spatial, ranges, KNN |
| BRIN | Yes | Yes | No | No | Large sequential tables |
| Partial | Yes | Yes | Yes | Yes | Filtered subsets |
| Composite | Yes | Yes | Yes | Yes | Multi-column filters and sorts |
Selectivity and Index Choice
| Cardinality | Selectivity | Index Usefulness |
|---|---|---|
| Unique (1:1) | Very high | Excellent for equality |
| Hundreds | High | Good for equality and range |
| Dozens | Medium | Marginal for equality |
| Few (boolean, status) | Low | Poor; use partial index |
| Half the table matches | Very low | Optimizer ignores index |
Write Amplification by Index Count
| Indexes | Write Ops per Insert | Relative Throughput |
|---|---|---|
| 1 | 2 (heap + index) | 1.0× |
| 3 | 4 | 0.5× |
| 5 | 6 | 0.33× |
| 7 | 8 | 0.25× |
| 10 | 11 | 0.18× |
Database-Specific Index Types
| Database | Default | Specialized Types |
|---|---|---|
| PostgreSQL | B-tree | GIN, GiST, SP-GiST, BRIN, Hash |
| MySQL InnoDB | B-tree | Full-text, Spatial |
| SQL Server | B-tree | Clustered, Nonclustered, Columnstore, Filtered |
| Oracle | B-tree | Bitmap, Function-based, Reverse key |
Best Practices
✅ Do This:
-- Create indexes on columns used in WHERE and JOIN clauses.
CREATE INDEX idx_orders_customer ON orders(customer_id); -- ✅
-- Use composite indexes when queries filter and sort.
CREATE INDEX idx_orders_cust_date ON orders(customer_id, order_date); -- ✅
-- Use partial indexes for low-cardinality filtered columns.
CREATE INDEX idx_pending ON orders(id) WHERE status = 'pending'; -- ✅
-- Use covering indexes to eliminate heap access.
CREATE INDEX idx_cover ON orders(customer_id) INCLUDE (total); -- ✅
-- Check query plans before and after adding indexes.
EXPLAIN ANALYZE SELECT ...; -- ✅
-- Monitor index usage and drop unused indexes.
SELECT idx_scan FROM pg_stat_user_indexes WHERE idx_scan = 0; -- ✅
-- Keep indexes narrow; wide indexes cost more to maintain.
CREATE INDEX idx_small ON orders(customer_id); -- ✅❌ Don’t Do This:
-- Don't index every column "just in case."
CREATE INDEX idx1 ON t(a); CREATE INDEX idx2 ON t(b); -- ❌
-- Don't create a full index on a boolean column.
CREATE INDEX idx_active ON users(is_active); -- ❌ Low selectivity
-- Don't forget the matching predicate for partial indexes.
SELECT * FROM orders WHERE status = 'pending'; -- ❌
-- (Index must have WHERE status = 'pending' to be used)
-- Don't assume the optimizer will use your index.
-- Always verify with EXPLAIN ANALYZE. -- ❌
-- Don't create duplicate or redundant indexes.
CREATE INDEX idx_a ON t(col1);
CREATE INDEX idx_b ON t(col1, col2); -- ❌ idx_a is redundant
-- Don't index columns that are rarely queried.
CREATE INDEX idx_notes ON orders(notes); -- ❌
-- Don't ignore the write cost of high-index tables.
-- 10 indexes = 11 writes per insert. -- ❌Common Pitfalls
| Pitfall | Why It Happens | Fix |
|---|---|---|
| Index never used | Low selectivity; optimizer chooses seq scan | Use partial index or accept seq scan |
| Partial index ignored | Query missing the matching WHERE predicate | Include the index’s predicate in queries |
| Too many indexes | Every index adds write cost and storage | Audit usage; drop unused indexes |
| Composite index wrong order | Leading column not in query filter | Reorder: equality first, range second |
| Index on boolean useless | Cardinality 2; matches half the table | Partial index on the rare value |
| Bloat from updates | Dead entries accumulate over time | REINDEX or OPTIMIZE TABLE periodically |
| Covering index too wide | Included columns enlarge every entry | Include only the columns queries need |
| Redundant indexes | Overlapping column combinations | Drop indexes whose columns are a prefix of another |
Real-World Examples
1. Email Lookup with Unique Index
CREATE UNIQUE INDEX idx_users_email ON users(email);
-- Enforces uniqueness and accelerates login lookups.2. Date Range Reporting
CREATE INDEX idx_orders_date ON orders(order_date);
SELECT * FROM orders WHERE order_date >= '2026-01-01';
-- B-tree range scan avoids full table scan.3. Soft Delete Pattern
CREATE INDEX idx_active_users ON users(email)
WHERE deleted_at IS NULL;
-- Only indexes active users; queries always filter deleted_at IS NULL.4. Composite for Filter and Sort
CREATE INDEX idx_cust_date ON orders(customer_id, order_date DESC);
SELECT * FROM orders WHERE customer_id = 42 ORDER BY order_date DESC;
-- Index satisfies both filter and sort; no separate Sort step.5. Covering Index for Index-Only Scan
CREATE INDEX idx_cover ON orders(customer_id) INCLUDE (total, status);
SELECT customer_id, total, status FROM orders WHERE customer_id = 42;
-- Query answered entirely from index; heap never touched.6. Partial Index for Pending Queue
CREATE INDEX idx_pending ON orders(created_at)
WHERE status = 'pending';
-- Small, fast index for the minority of rows that are pending.7. Expression Index for Case-Insensitive Search
CREATE INDEX idx_lower_email ON users(LOWER(email));
SELECT * FROM users WHERE LOWER(email) = 'alice@example.com';
-- Index on the expression; query must use exact same expression.8. BRIN for Time-Series Data
CREATE INDEX idx_logs_time ON logs USING BRIN (created_at);
-- Tiny index for naturally ordered data; each block range summarized.9. Foreign Key Index
CREATE INDEX idx_order_customer ON orders(customer_id);
-- Accelerates joins and enforces referential integrity checks.10. Monitoring Index Usage
SELECT indexrelname, idx_scan FROM pg_stat_user_indexes
WHERE idx_scan = 0;
-- Find indexes that have never been used; candidates for removal.Visual
The B-Tree Structure
┌────────────────────────────────────────────────────────────┐
│ B-TREE INDEX STRUCTURE │
│ │
│ ┌──────────────────┐ │
│ │ ROOT NODE │ │
│ │ [10 | 20 | 30] │ │
│ └────────┬─────────┘ │
│ │ │
│ ┌────────────────┼────────────────┐ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ ┌───────────┐ ┌───────────┐ ┌───────────┐ │
│ │INTERNAL │ │INTERNAL │ │INTERNAL │ │
│ │[5|7] │ │[15|18] │ │[25|28] │ │
│ └─────┬─────┘ └─────┬─────┘ └─────┬─────┘ │
│ │ │ │ │
│ ▼ ▼ ▼ │
│ ┌───────────┐ ┌───────────┐ ┌───────────┐ │
│ │LEAF │───▶│LEAF │───▶│LEAF │ │
│ │[1,3,5,7] │ │[11,15,18] │ │[21,25,28] │ │
│ └───────────┘ └───────────┘ └───────────┘ │
│ │
│ Height: 3 levels. Each leaf holds many entries. │
│ Leaf nodes linked left-to-right for range scans. │
│ Lookup for key=15: root→[15|18]→leaf[11,15,18] found. │
│ │
└────────────────────────────────────────────────────────────┘Equality Lookup vs Sequential Scan
┌────────────────────────────────────────────────────────────┐
│ EQUALITY LOOKUP: INDEX vs SEQUENTIAL SCAN │
│ │
│ SEQUENTIAL SCAN (no index) │
│ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │
│ │ 1 │ │ 2 │ │ 3 │ │ 4 │ │...│ │998│ │999│ │1M │ │
│ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ │
│ Read every row, check condition, discard non-matches. │
│ Rows read: 1,000,000. Matches: 1. │
│ │
│ INDEX LOOKUP (B-tree on id) │
│ ┌─────────┐ │
│ │ ROOT │ │
│ │ [500K] │ │
│ └────┬────┘ │
│ │ │
│ ▼ │
│ ┌─────────┐ │
│ │ LEAF │ │
│ │ [id=42] │───▶ Heap row 42 │
│ └─────────┘ │
│ Rows read: 3 index pages + 1 heap page. │
│ Total I/O: 4 pages vs 1,000,000 rows. │
│ │
└────────────────────────────────────────────────────────────┘Selectivity and Index Choice
┌────────────────────────────────────────────────────────────┐
│ SELECTIVITY: WHEN THE OPTIMIZER USES AN INDEX │
│ │
│ Query: WHERE column = value │
│ │
│ Selectivity = (Rows matching) / (Total rows) │
│ │
│ ┌────────────────────────────────────────────────────┐ │
│ │ Selectivity │ Optimizer Choice │ │
│ ├────────────────────────────────────────────────────┤ │
│ │ < 1% │ Index scan (very selective) │ │
│ │ 1% – 10% │ Index scan (usually) │ │
│ │ 10% – 25% │ Depends on I/O cost model │ │
│ │ > 25% │ Sequential scan (index ignored) │ │
│ └────────────────────────────────────────────────────┘ │
│ │
│ High cardinality column (email): selectivity ≈ 0.0001% │
│ → Index used. │
│ Low cardinality column (boolean): selectivity ≈ 50% │
│ → Sequential scan. Index is useless. │
│ │
└────────────────────────────────────────────────────────────┘Write Amplification
┌────────────────────────────────────────────────────────────┐
│ WRITE AMPLIFICATION BY INDEX COUNT │
│ │
│ One INSERT with 5 indexes: │
│ │
│ ┌─────────┐ │
│ │ INSERT │ │
│ │ orders │ │
│ └────┬────┘ │
│ │ │
│ ├────────────────────────────────────────────┐ │
│ │ │ │
│ ▼ ▼ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ Heap │ │ Index 1 │ │ Index 2 │ │ Index 3 │ │
│ │ Write │ │ Update │ │ Update │ │ Update │ │
│ └─────────┘ └─────────┘ └─────────┘ └─────────┘ │
│ │ │ │ │ │
│ ▼ ▼ ▼ ▼ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ Index 4 │ │ Index 5 │ │ WAL │ │ Page │ │
│ │ Update │ │ Update │ │ Record │ │ Splits │ │
│ └─────────┘ └─────────┘ └─────────┘ └─────────┘ │
│ │
│ 1 logical INSERT = 6+ physical writes. │
│ Each index adds a permanent tax on every write. │
│ │
└────────────────────────────────────────────────────────────┘Summary
| Item | Value |
|---|---|
| Index | Supplementary data structure mapping values to row locations |
| B-tree | Default index; supports equality, range, sort; O(log n) |
| Hash index | Equality only; O(1) average; no range or sort |
| Cardinality | Number of distinct values in a column |
| Selectivity | Fraction of table matched by a predicate |
| Partial index | Index on subset of rows matching a WHERE condition |
| Composite index | Index on multiple columns; leading column matters |
| Covering index | Index containing all columns needed by a query |
| Write amplification | Each index adds one write per DML operation |
| BRIN | Block-range index for large, naturally ordered tables |
| Full table scan | Reading every row; used when selectivity is low |
Key takeaways:
- B-tree is the default for good reason. It handles equality, range, and sorted queries in O(log n) time. It is the right choice for almost every general-purpose index.
- Selectivity determines usefulness. An index on a column that matches a large fraction of the table is rarely used by the optimizer. The index exists but the database ignores it.
- Partial indexes solve the low-cardinality problem. When queries always filter on a specific rare value, a partial index on that value is small, fast, and highly selective.
- Composite indexes serve filter-and-sort queries. The column order matters: equality columns first, range and sort columns after. The index can eliminate the sort step entirely.
- Covering indexes avoid heap access. When a query needs only indexed columns, the database can answer it entirely from the index. This is the fastest possible access path.
- Every index taxes every write. An INSERT into a table with ten indexes performs eleven write operations. At high ingestion rates, this tax becomes the dominant cost.
- Unused indexes should be dropped. An index that the optimizer never uses provides no benefit but imposes full write cost and storage overhead. Monitor usage and remove them.
Remember: Database indexes are a permanent trade: they accelerate specific read patterns at the cost of slowing every write and consuming storage. The B-tree is the workhorse because it handles the widest range of query patterns. The choice of which columns to index, and in what combination, is a query-driven decision, not a schema-driven one. The right process is to identify slow queries, examine their filters and sorts, design indexes that match, verify with execution plans, and periodically audit which indexes are actually being used. An index that exists but is never used is not a neutral asset; it is pure liability.
Stop using slow, ad-bloated tool sites! 🤮
🔎 Search “KandZ Tools” on Google to use many professional utilities for free.
KandZ.me is the ultimate minimalist hub for:
✅ Finance (Mortgage, Interest, Inflation)
✅ Tech (Base64, JSON, Dev Suite, IP)
✅ Health (BMI, BMR, TDEE)
✅ Productivity (Timer, Workspace, QR)
⚡️ Fast & Private
🔒 No data leaves your device
💎 100% Free
🔗 Use it now: https://tools.kandz.me
🔖 Bookmark it—you’ll need it later!