How indexing works internally: B-tree for range queries, hash index for exact match, clustered vs non-clustered

• B+tree – A shallow, high-fanout, self-balancing tree where internal nodes hold separator keys and leaf nodes store the indexed values in sorted order, chained together for efficient range scans.
• Hash index – Stores keys in hash buckets for average O(1) equality lookups, but provides no ordering, so it cannot serve range, sort, or grouping operations.
• Clustered index – The leaf nodes contain the actual table rows in key order, so the index is the table; reaching the key gives the full row with no extra hop.
• Non-clustered index – A separate B-tree whose leaf nodes hold only the key plus a locator (primary key or physical row id), requiring a second lookup to fetch the full row.
• Fanout – A single 8 KB page can hold hundreds of keys, so even hundreds of millions of rows form a tree only three or four levels deep.

What is a B+tree index?

A B+tree is a self-balancing tree data structure that keeps all data in sorted order. Every leaf node is at the same depth from the root, which guarantees that every lookup costs the same number of page reads regardless of the key value.

The key property is high fanout. A single 8 KB disk page can hold hundreds of separator keys, so a table with two hundred million rows forms a tree only three or four levels deep.

-- National Bank of India: 200 million transactions
-- B+tree on txn_id is ~4 levels deep
-- Each lookup reads 4 pages, not 200,000,000 rows

CREATE TABLE transactions (
    txn_id      BIGSERIAL PRIMARY KEY,
    account_id  VARCHAR(20) NOT NULL,
    amount      DECIMAL(15,2) NOT NULL,
    created_at  TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP
);

-- Primary-key lookup: 3-4 page reads
SELECT * FROM transactions WHERE txn_id = 987654321;

B+tree depth for various table sizes:
  1,000 rows       -> ~2 levels
  1,000,000 rows   -> ~3 levels
  200,000,000 rows -> ~4 levels
  1,000,000,000 rows -> ~4 levels

How does a B+tree serve range queries?

The leaf nodes of a B+tree are stored in sorted order and linked together in a doubly-linked list. This means the database can seek to the start of a range and then walk the linked leaves sequentially until it passes the end of the range.

-- Range query on the quarterly statement for Rajesh
-- The B+tree seeks to the first qualifying leaf
-- and walks forward until it passes the end date
SELECT txn_id, amount, created_at
FROM   transactions
WHERE  account_id = 'SAV2001'
  AND  created_at BETWEEN '2026-01-01' AND '2026-03-31'
ORDER BY created_at;

Execution plan:
Index Scan using ix_txn_acct_date on transactions
  Index Cond: (account_id = 'SAV2001'
    AND created_at >= '2026-01-01'
    AND created_at <= '2026-03-31')

This same sorted structure also supports ORDER BY, GROUP BY, and MIN/MAX without a separate sort step.

-- MIN uses the first entry in the index
SELECT MIN(created_at) FROM transactions WHERE account_id = 'SAV2001';
-- Plan: Index Scan (reads just the first leaf entry)

-- MAX uses the last entry in the index
SELECT MAX(created_at) FROM transactions WHERE account_id = 'SAV2001';
-- Plan: Index Scan Backward (reads just the last leaf entry)

What is a hash index?

A hash index applies a hash function to the key to pick a bucket. Equality lookups like WHERE account_id = 'SAV2001' are average constant time, often faster than a B-tree for pure point lookups.

-- PostgreSQL: create a hash index
CREATE INDEX ix_tokens_hash ON auth_tokens USING hash (token_value);

-- Fast exact-match lookup
SELECT user_id FROM auth_tokens WHERE token_value = 'abc123xyz';
-- Plan: Index Scan using ix_tokens_hash

But a hash index destroys all ordering. There is no concept of "the next key," so the following queries cannot use it.

-- These CANNOT use a hash index:
SELECT * FROM transactions WHERE amount > 50000.00;       -- range
SELECT * FROM transactions ORDER BY created_at;           -- sorting
SELECT branch_code, COUNT(*) FROM accounts GROUP BY branch_code; -- grouping

| Feature | B+tree Index | Hash Index |
|---|---|---|
| Equality lookup | O(log n) | O(1) average |
| Range query | Yes – sorted leaves | No |
| ORDER BY | Yes | No |
| GROUP BY | Yes | No |
| MIN / MAX | Yes – first/last leaf | No |
| Disk crash recovery | WAL-logged | WAL-logged (PostgreSQL 10+) |

How is a clustered index different from a non-clustered index internally?

In a clustered index, the leaf pages of the B-tree are the data pages themselves. The rows are physically stored in key order. This means reaching the leaf gives you the complete row with no extra lookup.

-- InnoDB: the PRIMARY KEY is the clustered index
-- Leaf pages contain: [account_id | customer_name | pan | balance | ...]
SELECT * FROM accounts WHERE account_id = 'SAV2001';
-- One traversal: root -> internal -> leaf (which IS the row)

In a non-clustered index, the leaf pages store only the indexed columns plus a pointer back to the row. To get the remaining columns, the engine performs a bookmark lookup.

-- Non-clustered index on pan
-- Leaf pages contain: [pan | account_id (the PK pointer)]
SELECT * FROM accounts WHERE pan = 'ABCDE1234F';
-- Two traversals:
--   1. pan index -> find account_id = 'SAV2001'
--   2. clustered index -> fetch full row for 'SAV2001'

Clustered Index Lookup:
Root -> Internal -> Leaf (= full row)
  Cost: 3-4 page reads, zero extra hops

Non-Clustered Index Lookup:
Secondary Root -> Secondary Leaf (= PK pointer)
  then: Clustered Root -> Clustered Leaf (= full row)
  Cost: 6-8 page reads (two traversals)

What is a bookmark lookup and how do you avoid it?

A bookmark lookup is the second traversal that happens when a non-clustered index does not contain all the columns the query needs. The database must go back to the clustered index (or the heap) to fetch the missing columns.

You avoid it with a covering index that includes all needed columns.

-- Without covering: bookmark lookup per row
SELECT account_id, balance FROM accounts WHERE pan = 'ABCDE1234F';
-- Plan: Index Scan on ux_accounts_pan -> then heap/clustered fetch

-- With covering: index-only scan, no bookmark lookup
CREATE INDEX ix_pan_covering ON accounts(pan) INCLUDE (balance);
SELECT account_id, balance FROM accounts WHERE pan = 'ABCDE1234F';
-- Plan: Index Only Scan on ix_pan_covering

How does InnoDB store secondary indexes internally?

In InnoDB, every secondary (non-clustered) index stores the primary key as its row locator. This has two consequences.

First, a secondary index lookup always does two B-tree traversals: one in the secondary index to find the primary key, then one in the clustered index to fetch the row.

Second, a wide primary key bloats every secondary index. If the primary key is a 36-character UUID string, every secondary index entry carries that 36-byte pointer.

-- Bad: 36-byte primary key bloats all secondary indexes
CREATE TABLE payments_bad (
    payment_id CHAR(36) PRIMARY KEY,  -- UUIDv4 as string
    account_id VARCHAR(20),
    amount     DECIMAL(15,2)
);

-- Good: compact 8-byte primary key
CREATE TABLE payments_good (
    payment_id BIGSERIAL PRIMARY KEY,  -- 8 bytes
    account_id VARCHAR(20),
    amount     DECIMAL(15,2)
);

-- Or: native UUID type (16 bytes, much better than 36-byte string)
CREATE TABLE payments_better (
    payment_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    account_id VARCHAR(20),
    amount     DECIMAL(15,2)
);

When should you use a hash index over a B-tree?

Use a hash index only when the workload is pure exact-match lookups with no ranges, sorting, or grouping. In practice this is rare.

-- Good use case: authentication token lookup
-- Only ever exact-match, millions of lookups per minute, never a range
CREATE INDEX ix_tokens_hash ON auth_tokens USING hash (token_value);

SELECT user_id, expires_at
FROM   auth_tokens
WHERE  token_value = 'eyJhbGciOiJIUzI1NiJ9.abc123';

For almost every other case, use the default B-tree because it handles equality, ranges, sorting, and grouping.

What should a senior engineer know?

• The fill factor of a B-tree page affects how much free space is left for future updates. A lower fill factor reduces page splits but wastes space.
• In PostgreSQL, CLUSTER reorders a heap table by an index once, but the order drifts with subsequent writes. InnoDB keeps the clustered order permanently.
• A GIN (Generalized Inverted Index) is used for full-text search and jsonb containment. A GiST (Generalized Search Tree) is used for geometric and range types.
• BRIN (Block Range Index) is a very compact index for naturally ordered data like timestamps in append-only tables.

-- BRIN index for append-only audit log
CREATE TABLE audit_log (
    log_id     BIGSERIAL PRIMARY KEY,
    event_time TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
    event_type VARCHAR(50),
    details    TEXT
);

-- BRIN is tiny: stores min/max per block range
CREATE INDEX ix_audit_brin ON audit_log USING brin (event_time);

What are common interview follow-up questions?

• What is the left-prefix rule for composite indexes?
• What is a covering index and when does it produce an index-only scan?
• Why does wrapping an indexed column in a function defeat the index?
• How does CREATE INDEX CONCURRENTLY differ from a normal CREATE INDEX?