What is Indexing in Database: Delete the Scan

What is indexing in database? It's a data structure that prevents your DBMS from scanning every single row when you query. Without indexes, your database performs full table scans—reading millions of rows to find one record. With proper indexing, that same query hits 3-4 disk blocks and returns in milliseconds.

Most developers write CREATE INDEX once during schema setup and never think about it again. Then they blame the database when queries take 8 seconds. The problem isn't PostgreSQL or MySQL. The problem is you don't understand how indexes actually work at the disk level.

This article deletes the surface-level explanations. We're covering B-tree internals, covering indexes, composite key strategies, and when indexes actively hurt performance. No metaphors about library card catalogs. Just production-grade database optimization.

Table of Contents

• ▹The Mechanics: How Database Indexes Actually Work
• ▹B-Tree Index Architecture
• ▹Hash Indexes and Their Limitations
• ▹Composite Indexes: Key Order Matters
• ▹Covering Indexes Delete Extra Lookups
• ▹When Indexes Kill Performance
• ▹Index Maintenance and Fragmentation
• ▹Real Optimization Strategies
• ▹FAQ

The Mechanics: How Database Indexes Actually Work

An index is a sorted data structure mapping column values to physical row locations. When you execute SELECT * FROM users WHERE email = 'user@example.com', the database can either:

1. ▹Full table scan: Read every row sequentially until it finds matches
2. ▹Index seek: Use the email index to jump directly to matching rows

The performance difference is exponential. A table with 10 million rows might require 10 million comparisons without an index. With a B-tree index, it requires log₂(10,000,000) ≈ 23 comparisons.

Here's the raw performance data from PostgreSQL documentation:

-- No index: Sequential scan
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;
-- Seq Scan on orders (cost=0.00..180000.00 rows=1 width=128) (actual time=1834.291..1834.292 rows=1 loops=1)

-- With index: Index scan
CREATE INDEX idx_orders_customer ON orders(customer_id);
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;
-- Index Scan using idx_orders_customer on orders (cost=0.43..8.45 rows=1 width=128) (actual time=0.034..0.035 rows=1 loops=1)

1834ms reduced to 0.035ms. That's a 52,000x performance improvement.

B-Tree Index Architecture

B-trees are the default index structure in PostgreSQL, MySQL, Oracle, and SQL Server. They're self-balancing trees with nodes sorted by key values.

Structure breakdown:

• ▹Root node: Contains pointers to child nodes
• ▹Internal nodes: Navigation layer with key ranges
• ▹Leaf nodes: Actual data pointers to table rows

         [50]
        /    \
    [25]      [75]
   /   \      /   \
[10][35] [60][90]

Each node holds multiple keys (typically 100-200 depending on page size). When you search for a value, the tree traverses log-height levels instead of scanning linearly.

Key characteristics:

• ▹Balanced: All leaf nodes are at the same depth
• ▹Sorted: Enables range queries (BETWEEN, >, < operators)
• ▹Page-based: Nodes align with disk block size (4KB-16KB)

PostgreSQL uses a variant called B+ tree where leaf nodes are linked, enabling faster sequential scans. The MySQL documentation provides detailed internals on how InnoDB implements B-tree pages at the physical storage level.

Hash Indexes and Their Limitations

Hash indexes use a hash function to map keys to bucket locations. They're faster for exact-match lookups but useless for range queries.

CREATE INDEX idx_user_email_hash ON users USING HASH (email);

When to use hash indexes:

• ▹Exact equality checks only (WHERE email = 'value')
• ▹Uniformly distributed data
• ▹Memory-constrained environments (smaller than B-trees)

Fatal limitations:

• ▹No range queries: WHERE age > 25 forces a full scan
• ▹No sorting: Can't satisfy ORDER BY clauses
• ▹Collision overhead: Poor hash functions degrade to O(n)

PostgreSQL added WAL-logging to hash indexes in version 10, but most production systems still default to B-trees because range queries are too common. For distributed systems, AWS DynamoDB uses hash-based partition keys for horizontal scaling, demonstrating where hash indexes excel.

Composite Indexes: Key Order Matters

Composite indexes cover multiple columns. The column order in the index definition determines query optimization effectiveness.

CREATE INDEX idx_orders_composite ON orders(customer_id, order_date, status);

This index optimizes queries with these WHERE patterns:

1. ▹WHERE customer_id = 42
2. ▹WHERE customer_id = 42 AND order_date > '2026-01-01'
3. ▹WHERE customer_id = 42 AND order_date > '2026-01-01' AND status = 'shipped'

But it cannot optimize:

• ▹WHERE order_date > '2026-01-01' (skips first column)
• ▹WHERE status = 'shipped' (skips first two columns)

This is why understanding query patterns matter. The leftmost column must be in the WHERE clause for the index to activate. If you frequently query by order_date alone, create a separate index.

Real example from a production e-commerce schema:

-- Bad: Forces index on individual columns
CREATE INDEX idx_product_sku ON products(sku);
CREATE INDEX idx_product_warehouse ON products(warehouse_id);

-- Good: Single composite matching query patterns
CREATE INDEX idx_product_inventory ON products(warehouse_id, sku, stock_quantity);

The composite index handles inventory lookups, stock checks, and warehouse filtering with one structure instead of three separate indexes competing for cache space.

Covering Indexes Delete Extra Lookups

A covering index includes all columns referenced in a query, eliminating the need to access the table heap.

-- Query needs: customer_id, order_date, total_amount
SELECT customer_id, order_date, total_amount 
FROM orders 
WHERE customer_id = 42;

-- Covering index includes all query columns
CREATE INDEX idx_orders_covering ON orders(customer_id) INCLUDE (order_date, total_amount);

PostgreSQL syntax uses INCLUDE, MySQL achieves the same with composite key structure. The database reads only the index pages—no table lookups required.

Performance impact:

• ▹Standard index: 2 disk seeks (index + table heap)
• ▹Covering index: 1 disk seek (index only)

For queries executing thousands of times per second, eliminating one disk seek per query saves hundreds of milliseconds of aggregate latency.

This ties directly into database optimization tools that automatically suggest covering indexes based on query patterns. Modern cloud platforms like Amazon RDS Performance Insights analyze query execution and recommend index strategies for covering scenarios.

When Indexes Kill Performance

Indexes aren't free. Every index adds write overhead because INSERT, UPDATE, and DELETE operations must maintain index structures.

Write amplification example:

-- Table with 5 indexes
INSERT INTO users (email, name, created_at, country, status) VALUES (...);

This single INSERT triggers:

1. ▹Main table write (1 disk operation)
2. ▹Primary key index update (1 disk operation)
3. ▹Email index update (1 disk operation)
4. ▹Country index update (1 disk operation)
5. ▹Status index update (1 disk operation)
6. ▹Created_at index update (1 disk operation)

Total: 6 disk operations for one logical insert.

Modern SSDs handle this better than spinning disks, but the CPU overhead from B-tree balancing still accumulates. For write-heavy applications, over-indexing reduces throughput.

When to avoid indexes:

• ▹Small tables (< 10,000 rows): Sequential scan is faster than index overhead
• ▹Columns with low cardinality: status IN ('active', 'inactive') doesn't benefit from indexing
• ▹Bulk insert operations: Drop indexes before bulk load, recreate after

Index Maintenance and Fragmentation

B-trees fragment over time as rows are inserted, updated, and deleted. Fragmented indexes increase disk I/O because leaf nodes aren't sequentially stored.

PostgreSQL fragmentation check:

SELECT schemaname, tablename, indexname, 
       pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM pg_stat_user_indexes
WHERE schemaname = 'public'
ORDER BY pg_relation_size(indexrelid) DESC;

Maintenance commands:

-- PostgreSQL
REINDEX INDEX idx_orders_customer;

-- MySQL
OPTIMIZE TABLE orders;

-- Oracle
ALTER INDEX idx_orders_customer REBUILD;

Run these during maintenance windows. Reindexing locks tables depending on DBMS and version. PostgreSQL's REINDEX CONCURRENTLY (version 12+) allows online rebuilds without blocking writes.

Real Optimization Strategies

1. Analyze query patterns first:

-- PostgreSQL query statistics
SELECT query, calls, total_exec_time, mean_exec_time
FROM pg_stat_statements
ORDER BY total_exec_time DESC
LIMIT 20;

Index the slowest queries, not random columns. Measure with EXPLAIN ANALYZE before and after index creation.

2. Use partial indexes for filtered queries:

-- Only index active users
CREATE INDEX idx_users_active ON users(email) WHERE status = 'active';

Smaller index, faster lookups, less disk space.

3. Expression indexes for computed columns:

-- Index lowercase email for case-insensitive searches
CREATE INDEX idx_users_email_lower ON users(LOWER(email));

Standard indexes don't optimize function calls in WHERE clauses. Expression indexes do.

4. Monitor index usage:

-- PostgreSQL unused indexes
SELECT schemaname, tablename, indexname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0 AND indexrelname NOT LIKE 'pg_toast%'
ORDER BY pg_relation_size(indexrelid) DESC;

If idx_scan = 0, the index has never been used. Delete it.

5. Understand cardinality impact:

High cardinality (unique values) = effective indexes. Low cardinality (few unique values) = wasted space. A boolean column with two possible values doesn't need an index. A UUID primary key does.

This connects to how AI agent architecture systems handle database optimization—automated query analysis identifies missing indexes faster than manual inspection. Our managed database services implement these strategies across PostgreSQL, MySQL, and MongoDB deployments.

FAQ

What happens if I create too many indexes on a single table?+

Write performance degrades exponentially. Every INSERT/UPDATE/DELETE must maintain all indexes, multiplying disk I/O. The query planner also slows down because it evaluates more index options. Keep indexes under 5-7 per table unless you have read-heavy analytics workloads where write latency doesn't matter.

Can I index a column that's already part of a composite index?+

Yes, but it's usually redundant. If you have INDEX(customer_id, order_date), creating a separate INDEX(customer_id) wastes disk space because the composite index already optimizes single-column queries on customer_id. The exception is when single-column queries dominate and you want a smaller index for cache efficiency.

Why does my query ignore the index and force a sequential scan?+

Three common causes: (1) The optimizer estimates sequential scan is faster (small tables or queries returning > 15% of rows), (2) Type mismatch between query value and indexed column (comparing VARCHAR to INTEGER), (3) Function calls on indexed columns (WHERE LOWER(email) = ... instead of pre-computed lowercase index). Run EXPLAIN ANALYZE to see the optimizer's cost calculation.