Database Index — Explained with Examples

A database index is a data structure (like a B-tree or hash table) that speeds up data retrieval operations at the cost of additional storage and write overhead.

Database Index is a structure that improves the speed of data retrieval on a table. Without an index, the database performs a full table scan (reading every row). With an index, it uses a B-tree, hash map, or bitmap to locate data directly.

Why Indexing Matters

As tables grow, full table scans become prohibitively slow. A query on 10 million rows without an index might take seconds. With an index, the same query executes in milliseconds. Indexes are the single most impactful performance optimization in database systems.

Real-World Analogy

A book’s index at the back. Without it, you’d read every page to find “cap theorem.” With the index, you look up “cap theorem” and go directly to page 187. The index takes extra pages (storage) and needs updating when the book changes (write overhead), but the search speed gain is massive.

Example: Index in SQL

-- Create an index on frequently queried columns
CREATE INDEX idx_users_email ON users (email);

-- Without index: full table scan
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'alice@example.com';
-- Result: Seq Scan on users (cost=0.00..1000.00 rows=1)

-- With index: index scan
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'alice@example.com';
-- Result: Index Scan using idx_users_email (cost=0.28..8.29 rows=1)

# Simulating B-tree index lookup
class BTreeIndex:
    def __init__(self):
        self.index = {}

    def insert(self, key, row_id):
        self.index[key] = row_id

    def lookup(self, key):
        return self.index.get(key)  # O(1) average

# Compare: full scan vs index
rows = {"alice@example.com": 42, "bob@test.com": 99}
# Index lookup (fast)
row_id = rows.get("alice@example.com")  # Instant
# Full scan (slow)
for i, row in enumerate(all_rows):
    if row.email == "alice@example.com":
        print(f"Found at row {i}")  # O(n)

Related Terms

Partitioning, Sharding, Replication, N+1 Query