Indexing — B-Tree & Hash

In simple words

Finding one row by reading every row is slow when there are millions of them. An index is a separate, sorted list kept next to the table — like the index at the back of a book — that tells the database exactly where to look, so it jumps straight to the row instead of scanning everything. The price is that every write must also update the index, and the index takes up space. This note covers the two main kinds (B-Tree and Hash) and when an index actually helps.

What is an Index?

An index is a separate data structure that the database maintains to speed up data retrieval, at the cost of extra storage and slightly slower writes.

Think of a book's index at the back. Without it: read every page to find "normalization" → O(n) With it: look up "normalization → page 142" → jump directly → O(log n)

A database index works the same way.

Without index:
  SELECT * FROM users WHERE email = 'alice@email.com'
  → DB reads every single row from start to finish (full table scan)
  → 10 million rows = 10 million comparisons = SLOW

With index on email:
  → DB looks up 'alice@email.com' in the index structure
  → Gets the exact row location (page + offset)
  → Fetches that one row directly = FAST

The Problem Indexes Solve

Table: users (10 million rows)

Query: SELECT * FROM users WHERE email = 'alice@email.com'

Without index:
  Time complexity: O(n) — scan all 10M rows
  I/O operations: potentially thousands of disk reads
  Time: seconds to minutes on large tables

With index on email:
  Time complexity: O(log n) — B-Tree traversal
  I/O operations: 3-4 disk reads (tree height)
  Time: milliseconds

How Storage Works (Why Indexes Matter)

Data lives on DISK in fixed-size PAGES (typically 8KB or 16KB).
Each page holds ~100-1000 rows depending on row size.

Full table scan = read EVERY page → thousands of disk I/O operations
                                    disk I/O is the bottleneck, not CPU

Index = a separate structure that maps search values → page locations
      = fewer pages to read = much faster

B-Tree Index — The Default Index Type

B-Tree (Balanced Tree) is the most common index type in relational databases. Used by default in MySQL (InnoDB), PostgreSQL, Oracle, SQL Server.

Structure

B-Tree index on users.age

                    [30]
                  /      \
           [20, 25]        [40, 50]
          /   |   \        /   |   \
       [18] [22] [28]  [35] [45] [55, 60]

Each leaf node stores: (indexed value, pointer to actual row location)
Internal nodes store: key values that guide the search direction
All leaf nodes are linked → enables efficient range scans

How B-Tree Search Works

SELECT * FROM users WHERE age = 35

Step 1: Start at root [30]
Step 2: 35 > 30 → go right to [40, 50]
Step 3: 35 < 40 → go left to [35]
Step 4: Found! Follow row pointer → fetch actual row from table

Total comparisons: 3 (tree height = log n)
For 10 million rows: log₂(10,000,000) ≈ 23 comparisons max

B-Tree Supports Multiple Query Types

This is the key advantage of B-Tree over Hash indexes:

-- 1. Exact match ✅
SELECT * FROM users WHERE age = 30;

-- 2. Range queries ✅ (because leaf nodes are linked in sorted order)
SELECT * FROM users WHERE age BETWEEN 25 AND 40;
SELECT * FROM users WHERE age > 30;
SELECT * FROM users WHERE age < 25;

-- 3. Sorting (ORDER BY) ✅ (data is already sorted in the B-Tree)
SELECT * FROM users ORDER BY age;
-- With index: no sort needed, just traverse leaves in order

-- 4. Prefix matching on strings ✅
SELECT * FROM users WHERE name LIKE 'Ali%';
-- B-Tree is sorted alphabetically → can find prefix range

-- 5. IS NULL ✅ (NULLs are stored in B-Tree)
SELECT * FROM users WHERE age IS NULL;

B-Tree Does NOT Help With

-- Leading wildcard → can't use index, must scan all entries
SELECT * FROM users WHERE name LIKE '%Alice%';

-- Function on indexed column → breaks the index lookup
SELECT * FROM users WHERE YEAR(created_at) = 2024;
-- Fix: store year separately OR use range query:
SELECT * FROM users WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31';

-- OR conditions across different columns (usually)
SELECT * FROM users WHERE city = 'Mumbai' OR age = 25;
-- May require two separate index lookups + merge, or full scan

InnoDB B-Tree — Clustered vs Secondary Index

MySQL InnoDB uses a specific type of B-Tree: the clustered index.

Clustered Index (Primary Key Index)

The table data IS the B-Tree.
Rows are physically stored in primary key order.
The leaf nodes of the B-Tree contain the actual row data.

users table physically stored as:
Leaf: [user_id=1, Alice, alice@email.com, ...]
Leaf: [user_id=2, Bob, bob@email.com, ...]
Leaf: [user_id=3, Carol, ...]
...sorted by user_id on disk

Lookup by primary key:
→ traverse the B-Tree
→ leaf node IS the row — no extra lookup needed
→ very fast

Secondary Index (Non-Primary Key Index)

An index on any column other than the primary key.
Leaf nodes store: (indexed_value, primary_key_value)
                                   ↑ pointer back to clustered index

Index on email:
Leaf: [alice@email.com, 1]   ← stores user_id, not the actual row
Leaf: [bob@email.com, 2]
...sorted by email

Lookup by email:
Step 1: traverse email B-Tree → find [alice@email.com, 1]
Step 2: use user_id=1 to traverse PRIMARY KEY B-Tree → get actual row
→ TWO B-Tree lookups (called a "double lookup" or "bookmark lookup")

This is why covering indexes matter (Topic 05) — they avoid the second lookup.

Hash Index

A Hash Index uses a hash function to map a key directly to a location in a hash table. Think of it as a dictionary — key → value, O(1) lookup.

Structure

Hash index on users.email

Hash function: hash(email) → bucket number

"alice@email.com"  → hash → bucket 42 → [row pointer]
"bob@email.com"    → hash → bucket 17 → [row pointer]
"carol@email.com"  → hash → bucket 42 → [row pointer] (hash collision, chained)

Lookup: hash("alice@email.com") → bucket 42 → get row pointer → fetch row
Time complexity: O(1) average

Hash Index Supports

-- Exact match ONLY ✅
SELECT * FROM users WHERE email = 'alice@email.com';
-- O(1) average — fastest possible for exact lookup

Hash Index Does NOT Support

-- Range queries ❌ (hash destroys order — no way to find "next" value)
SELECT * FROM users WHERE age > 30;

-- Sorting ❌
SELECT * FROM users ORDER BY age;

-- Prefix matching ❌
SELECT * FROM users WHERE name LIKE 'Ali%';

-- IS NULL ❌ (in most implementations)

Where Hash Indexes Are Used

MySQL InnoDB: does NOT support explicit Hash indexes on disk
              (has an adaptive hash index in memory, automatic)
PostgreSQL:   supports Hash indexes explicitly
Memory tables: Hash index is default for MEMORY storage engine in MySQL
Redis:        Hash is the core data structure (key → value)

In practice:
Most developers use B-Tree even for exact lookups because:
- B-Tree is nearly as fast (O(log n) is still very fast)
- B-Tree also supports ranges and sorting
- Hash index has collision issues + doesn't work for range/sort

B-Tree vs Hash Index — Side-by-Side

How to Create Indexes in SQL

-- Default index (B-Tree in most databases)
CREATE INDEX idx_users_email ON users(email);

-- Unique index (enforces uniqueness + enables fast lookup)
CREATE UNIQUE INDEX idx_users_email ON users(email);

-- Explicit B-Tree index (PostgreSQL)
CREATE INDEX idx_users_age ON users USING BTREE (age);

-- Hash index (PostgreSQL only)
CREATE INDEX idx_users_email ON users USING HASH (email);

-- Drop index
DROP INDEX idx_users_email ON users;

-- Primary key index (auto-created)
ALTER TABLE users ADD PRIMARY KEY (user_id);

-- Check existing indexes
SHOW INDEX FROM users;          -- MySQL
SELECT * FROM pg_indexes        -- PostgreSQL
WHERE tablename = 'users';

The Cost of Indexes — What Nobody Tells You

Indexes speed up reads but slow down writes and consume storage.

Every INSERT:  new row → update every index on that table
Every UPDATE:  changed column → update index for that column
Every DELETE:  removed row → update every index

Table with 5 indexes + 1 million inserts per day:
→ Actually 6 million write operations per day (1 table + 5 indexes)

Indexes also consume disk space:
→ A B-Tree index on a VARCHAR(255) column ≈ 20-40% of table size
→ 10 indexes on a large table can double or triple total disk usage

Index Selectivity — Only Index Selective Columns

Selectivity = number of distinct values / total rows

High selectivity (good for indexing):
  email column: 10M rows, 10M unique values → selectivity = 1.0
  user_id:      10M rows, 10M unique values → selectivity = 1.0

Low selectivity (bad for indexing — often ignored by query planner):
  status column: 10M rows, 5 values (ACTIVE/INACTIVE/...) → selectivity = 0.0000005
  gender column: 10M rows, 2-3 values → selectivity ≈ 0.0000003
  is_deleted:    10M rows, 2 values (0/1) → selectivity ≈ 0.0000002

Why low selectivity indexes fail:
  "Get all active users" → status = 'ACTIVE' → 9.5M of 10M rows are ACTIVE
  → Index lookup finds 9.5M pointers → must fetch 9.5M rows
  → Full table scan would have been faster
  → Query planner detects this and ignores the index

EXPLAIN — Seeing if Your Index is Used

EXPLAIN SELECT * FROM users WHERE email = 'alice@email.com';

Output:
┌────────────────────────────────────────────────────────────────────────┐
│ id│select_type│table│type │possible_keys    │key             │rows│Extra│
├────────────────────────────────────────────────────────────────────────┤
│ 1 │ SIMPLE    │users│ref  │idx_users_email  │idx_users_email │ 1  │     │
└────────────────────────────────────────────────────────────────────────┘

type = 'ref'    → index being used ✅
type = 'ALL'    → full table scan  ❌ (no index used)
key  = NULL     → no index used    ❌
rows = 1        → estimated 1 row to scan ✅ (vs 10M without index)

Real-World System Design Examples

1. User Lookup by Email (Login)

-- Every login hits this query millions of times per day
SELECT user_id, password_hash FROM users WHERE email = ?

-- Without index: full table scan on every login = O(n) = disaster
-- With index:    B-Tree lookup = O(log n) = milliseconds

CREATE UNIQUE INDEX idx_users_email ON users(email);
-- UNIQUE index because email must be unique + gives fast lookup

2. Order History (Range + Sort)

SELECT * FROM orders
WHERE user_id = 123
  AND created_at >= '2024-01-01'
ORDER BY created_at DESC;

-- Index needed on (user_id, created_at) — composite index (Topic 05)
-- B-Tree supports: exact match on user_id + range on created_at + sort

3. Flipkart Product Search

SELECT * FROM products
WHERE category_id = 5
  AND price BETWEEN 500 AND 2000
ORDER BY rating DESC;

-- Index on (category_id, price, rating) — composite
-- B-Tree handles: exact category + price range + sort by rating

4. When NOT to Index

-- Small tables (< 1000 rows) — full scan is faster than index lookup overhead
-- Columns with very low cardinality (is_deleted, status with 2-3 values)
-- Tables with very high write rate where read is rare (logging tables, audit tables)
-- Temporary tables used for one-off queries

5. Index in Distributed Systems

Cassandra:   Primary key determines physical partition (node)
             Think of it as a hash-based distributed index
             → choose partition key carefully (determines data distribution)

MongoDB:     B-Tree indexes (called "indexes" not "B-Tree" in Mongo docs)
             _id field always indexed by default

Redis:       Hash data structure = O(1) key lookup = essentially a hash index
             ZADD/ZRANGE use a skip list internally (similar to B-Tree for range)

Elasticsearch: Inverted index (different type — maps terms → document IDs)
               Built for full-text search — not a B-Tree

Index Design — Interview Decision Framework

STEP 1: Identify your most frequent, most critical queries
        "What are the top 5 queries this service runs?"

STEP 2: Look at the WHERE clause columns → index candidates
        Look at ORDER BY columns → B-Tree can serve both

STEP 3: Check selectivity
        High cardinality (email, user_id, order_id) → index ✅
        Low cardinality (status, is_deleted) → skip ❌

STEP 4: Check query pattern
        Exact match only → B-Tree or Hash (B-Tree usually preferred)
        Range / sort / prefix → B-Tree mandatory

STEP 5: Consider write volume
        Write-heavy table → minimise indexes
        Read-heavy table → add indexes generously

STEP 6: Measure with EXPLAIN
        Always verify the index is actually being used

How This Connects

• Composite & Covering Indexes — the direct next step: multi-column indexes, the left-prefix rule, and covering indexes that skip the second lookup.
• Query Optimization & EXPLAIN Plans — EXPLAIN is how you confirm an index is actually used; the type and key columns tell you scan vs seek.
• Relational Model - Tables, Keys, Relationships — the primary key gets a clustered/unique index for free; foreign-key columns usually need one added by hand.
• SQL - Joins, Aggregations, Subqueries — a join is only fast if the join column on the "many" side is indexed; otherwise it's a nested full scan.
• Storage Engines - LSM-Tree vs B-Tree — B-Tree is read-optimised; LSM-tree (Cassandra, RocksDB) trades read amplification for much faster writes.
• Consistent Hashing / Geospatial Indexing — other index shapes: hash-partitioning for distribution, quadtree/geohash for 2-D range queries a B-Tree can't do.

In the Interview

When to say it. Whenever you name a query pattern ("look up user by email", "list a user's recent orders"), immediately state the index that serves it. And whenever asked "why is this slow?", reach for EXPLAIN + "is the column raw and selective?".

The ~20-second version:

"A B-Tree index is a balanced, sorted tree the database keeps beside the table. A lookup walks root-to-leaf in O(log n) — about 23 steps for 10 million rows versus 10 million for a full scan — and because the leaves are sorted and linked, the same index also serves range queries, ORDER BY, and prefix LIKE. A hash index is O(1) but exact-match only, so it's rarely worth giving up ranges for. In InnoDB the primary key is a clustered index — the row data lives in its leaves — and any secondary index stores the PK as its pointer, so a non-covering secondary lookup costs a second traversal. The cost of indexes is writes and storage: every insert updates every index. So I index high-cardinality columns that appear in WHERE and ORDER BY, avoid low-selectivity flags, and verify with EXPLAIN."

Follow-ups to expect:

1. "Why won't WHERE YEAR(created_at) = 2024 use the index?" — A function on the column means the index (which stores raw created_at) can't be traversed. Rewrite as a range: created_at >= '2024-01-01' AND created_at < '2025-01-01'. (Or add a function/expression index.)
2. "You have an index on status but the planner ignores it — why?" — Low selectivity. If 95% of rows are ACTIVE, the index returns millions of pointers and a full scan is cheaper; the planner knows this from statistics.
3. "Clustered vs secondary index?" — Clustered: rows stored in PK order, leaf = row. Secondary: leaf = (indexed value, PK); needs a second lookup unless the index covers the query.
4. "When would you NOT add an index?" — Tiny tables, write-heavy/rarely-read tables (audit logs), and columns with 2–3 distinct values.
5. "Leading vs trailing wildcard in LIKE?" — 'Ali%' uses the B-Tree (it's a prefix range); '%ali%' cannot — that needs a full-text or search index.

Mistake to avoid: "just add an index on every WHERE column". Each index taxes every write and can still be ignored if it's not selective or the column is wrapped in a function. Index deliberately, then confirm with EXPLAIN.

Quick Revision — 6 Lines

1. Index = separate data structure for fast lookup — trades write speed + storage for read speed
2. B-Tree = balanced tree, sorted, supports exact + range + sort + prefix — default in all RDBMS
3. Hash index = hash function → O(1) exact lookup, but NO range / sort / prefix support
4. Clustered index (InnoDB) = table data IS the B-Tree, sorted by PK on disk
5. Secondary index = stores (value, PK) → requires double lookup unless it's a covering index
6. Only index high-cardinality columns — low cardinality indexes are often ignored by the planner