Indexing and B+ Trees

What this lesson covers

An index is an extra data structure that lets the database find rows without reading the whole table, the same way a book's index lets you jump to page 212 instead of reading every page. Indexes are the single biggest lever for query performance, and they are also a common cause of slow writes and wasted storage when used carelessly.

This topic is tested in two styles. Conceptual questions: "Clustered versus non-clustered index?", "Why do databases use B+ trees and not binary search trees or hash tables?", "Why is my index not used?", "What is a covering index?". Numerical questions, common in written tests: "Block size 4 KB, key 8 bytes, pointer 8 bytes: what is the order of the B+ tree?", "How many disk accesses to find a record?", "Insert these keys and show the tree after each split". Both are covered below, with every number computed step by step and checked.

Why indexes: the disk is the bottleneck

Databases store tables on disk (SSD or spinning disk) in fixed-size blocks, also called pages, typically 4 KB, 8 KB (PostgreSQL) or 16 KB (MySQL InnoDB). The database reads and writes whole blocks, never single rows. A block read from disk is far slower than work done in memory, so the cost of a query is usually measured as the number of block reads (disk I/Os).

Some definitions used throughout:

• Blocking factor (bfr): records per block = floor(block size / record size).
• Search key: the attribute(s) used to look things up. It need not be the primary key.
• Record pointer: the disk address of a record (block number plus offset), or in some systems the row's primary key.

Worked example: the cost without an index

A table has 1,000,000 records of 200 bytes each, and the block size is 4096 bytes.

• bfr = floor(4096 / 200) = 20 records per block.
• Number of blocks = 1,000,000 / 20 = 50,000 blocks.

Finding one record by a unique key with a linear scan reads, on average, half the blocks: 25,000 I/Os, and 50,000 in the worst case (or if the key is not unique, since you must read everything).

If the file is sorted on the key, binary search needs ceil(log₂ 50,000) = ceil(15.6) = 16 block reads.

An index can bring this down to 3 or 4 reads, as the rest of the lesson shows.

File organization

How rows are arranged in the data file determines what indexes can do.

Heap file

Records are stored in no particular order; new rows go wherever there is space, usually at the end.

• Insert: fast (append).
• Search by any key: linear scan, unless there is an index.
• PostgreSQL stores every table as a heap; all its indexes are separate structures pointing into it.

Sorted (sequential) file

Records are kept physically ordered by a key.

• Search by that key: binary search, and range queries read consecutive blocks.
• Insert and delete: expensive, because order must be maintained. Systems use free space in each block and overflow blocks, then periodically reorganize.

Hashed file

A hash function on a key decides which bucket (one or more blocks) each record goes into.

• Equality search on that key: about 1 I/O (plus overflow chains).
• Range queries and sorting: useless, because hashing scatters neighboring keys.

Index basics and classification

An index is a file of index entries, each (search key value, pointer), kept in sorted order (or hashed). Index entries are much smaller than records, so many more fit in a block, and searching the index is far cheaper than searching the data.

Dense versus sparse

• A dense index has an entry for every search key value (every record, for a unique key).
• A sparse index has entries for only some values, typically one per data block: the first (anchor) key of each block. To find key k, find the largest index entry not greater than k, go to that block, and search inside it.

 sparse index            data file (sorted by roll_no)
 +-----+----+            block 1: 101 102 103 104
 | 101 | ---+-------->   block 2: 105 106 107 108
 | 105 | ---+-------->   block 3: 109 110 111 112
 | 109 | ---+-------->
 +-----+----+
 one entry per block

 dense index
 +-----+    +-----+    +-----+
 | 101 |    | 102 |    | 103 |  ... one entry per record
 +-----+    +-----+    +-----+

A sparse index requires the data file to be sorted on the search key, since it relies on keys between two anchors being in one block. Sparse indexes are smaller; dense indexes can answer "does key k exist?" without touching the data file and work on unsorted files.

Primary, clustering and secondary indexes (textbook classification)

The classic textbook classification (as in Elmasri and Navathe) is:

• Primary index: defined on the ordering key field of a sorted file, where that field is unique (a key). Usually sparse: one entry per block.
• Clustering index: defined on the ordering field of a sorted file where that field is not unique (say, dept_id). One entry per distinct value, pointing to the first block containing it.
• Secondary index: defined on any non-ordering field. Because the file is not sorted on it, it must be dense. For a non-unique field, each entry points to a block of record pointers (an extra level of indirection) or the index stores repeated entries.

A file can have at most one primary or clustering index (it can be physically sorted only one way) but many secondary indexes.

Clustered versus non-clustered (practical classification)

In industry and in most interviews, the terms are:

• Clustered index: the table's rows are stored in the order of the index key, or the index is the table. There can be only one.
• Non-clustered (secondary) index: a separate structure holding keys and pointers to the rows. There can be many.

How real systems do it:

• MySQL InnoDB: every table is a B+ tree clustered on the primary key; leaf pages hold the complete rows. Secondary index leaves hold the indexed columns plus the primary key, so a secondary lookup first finds the primary key, then searches the clustered index again (a "double lookup"). This is one reason long primary keys (like random UUID strings) make every secondary index larger.
• SQL Server: you choose one clustered index per table (by default the primary key); non-clustered indexes point to the clustered key or, for heap tables, to a row id.
• PostgreSQL: tables are heaps; all indexes are secondary and point to a physical tuple id. The CLUSTER command sorts the table once by an index, but the order is not maintained for later writes.
• SQLite: ordinary tables are B-trees keyed by rowid (an INTEGER PRIMARY KEY is an alias for it), so they are effectively clustered on it.

 Clustered (InnoDB):                 Secondary index on email:
 B+ tree on id                       B+ tree on email
   leaves = full rows                  leaves = (email, id)
 [1|Asha|...] [2|Ravi|...]             [a@x|7] [b@x|2] [c@x|9]
                                              |
                                              +--> look up id 2 in
                                                   the clustered tree

Multi-level indexes

If the index itself is large, searching it with binary search still takes many reads. The fix: index the index. Build a sparse index over the first-level index's blocks, then another over that, until the top level fits in one block. This is a multi-level index, and a B+ tree is a dynamic, self-balancing version of the same idea.

The number of index entries per block is the fan-out (fo). Each level reduces the number of blocks by a factor of fo.

Worked example: dense, sparse and multi-level

Same table: 1,000,000 records, 50,000 data blocks sorted on the key, block size 4096 bytes. An index entry is a key of 8 bytes plus a block pointer of 8 bytes = 16 bytes.

• Index fan-out = floor(4096 / 16) = 256 entries per block.

Single-level dense index (one entry per record):

• Index blocks = ceil(1,000,000 / 256) = 3,907.
• Binary search on the index: ceil(log₂ 3,907) = ceil(11.93) = 12 reads.
• Plus 1 data block read. Total: 13 I/Os.

Single-level sparse (primary) index (one entry per data block):

• Entries = 50,000; index blocks = ceil(50,000 / 256) = 196.
• Binary search: ceil(log₂ 196) = ceil(7.61) = 8 reads.
• Plus 1 data block. Total: 9 I/Os.

Multi-level index over that sparse index:

• Level 1: 196 blocks (as above).
• Level 2: ceil(196 / 256) = 1 block. This is the top.
• Search reads one block per level, then the data block: 2 + 1 = 3 I/Os.

In general, a multi-level index with fan-out fo over b blocks has about ceil(log_fo b) levels, compared with log₂ b for binary search. With fo = 256, each level is worth 8 levels of binary search.

B-trees and B+ trees

A static multi-level index is hard to maintain under inserts and deletes. The B-tree (Bayer and McCreight, 1970s) and its variant the B+ tree solve that: they are balanced multi-way search trees that stay balanced automatically as data changes, with nodes sized to fit one disk block.

Order and node rules

Definitions vary between textbooks, so always state yours. In this lesson, a B+ tree of order p means:

• An internal node has at most p child pointers and p − 1 keys.
• Every node except the root is at least half full: an internal node has at least ceil(p / 2) children.
• The root has at least 2 children (unless it is a leaf).
• All leaves are at the same depth. That is what "balanced" means here, and it guarantees every search costs the same number of node reads.
• Keys inside a node are sorted. In an internal node with keys K1 < K2 < ... and pointers P1, P2, ..., subtree P1 holds keys less than K1, subtree P2 holds keys from K1 up to but not including K2, and so on.

B-tree versus B+ tree

 B-tree: keys and record pointers in every node
              [ 40 *r ]
             /         \
   [ 15 *r  25 *r ]   [ 50 *r  60 *r ]
   each key appears once; *r = record pointer

 B+ tree: internal nodes are only a road map;
 all keys and record pointers live in the leaves
              [ 40 ]
             /      \
        [ 15 25 ]   [ 50 ]
       /    |    \     |   \
 [5 10]->[15 20]->[25 30 35]->[40 45]->[50 55 60]
 leaves linked left to right for range scans

Why databases use B+ trees

1. Higher fan-out, fewer levels. Internal nodes hold only keys and child pointers, so more fit per block. More children per node means a shallower tree and fewer disk reads per lookup.
2. Fast range scans. Leaves are linked in key order. WHERE price BETWEEN 100 AND 500 finds the first leaf once, then reads leaves sequentially. A B-tree must walk up and down the tree.
3. Predictable cost. Every lookup goes root to leaf, the same depth every time.
4. Upper levels stay in memory. The internal levels are small (often well under 1% of the index), so the database's buffer cache usually holds them, and a lookup costs about one or two real disk reads for the leaf and the row.
5. Good for sequential and bulk operations, such as ORDER BY on the indexed key and building an index from sorted data.

Why not other structures?

• Binary search tree (including AVL and red-black trees): each node has two children, so a million keys need about 20 levels, meaning 20 random disk reads. They are designed for memory, not blocks.
• Hash table: excellent for equality but cannot do ranges, prefix matches, or ordered output.
• Sorted array: binary search is fine, but inserts shift everything.

Order and fan-out math

These calculations appear in nearly every written test on indexing. Set up the inequality "everything in the node must fit in one block" and solve for the largest integer.

B+ tree order

Block size B = 4096 bytes, search key V = 8 bytes, child (block) pointer P = 8 bytes, record pointer Pr = 8 bytes.

Internal node: p child pointers and p − 1 keys.

p * P + (p - 1) * V  <=  B
8p + 8(p - 1)        <=  4096
16p                  <=  4104
p                    <=  256.5     ->  p = 256

Leaf node: m (key, record pointer) pairs and one pointer to the next leaf.

m * (V + Pr) + P  <=  B
16m + 8           <=  4096
m                 <=  255.5        ->  m = 255

B-tree order (for comparison)

In a B-tree, each internal node holds p child pointers, p − 1 keys and p − 1 record pointers:

p * P + (p - 1) * (V + Pr)  <=  B
8p + 16(p - 1)              <=  4096
24p                         <=  4112
p                           <=  171.3   ->  p = 171

Same block, fan-out 171 instead of 256. That is the B+ tree's advantage in numbers.

Height and search cost

How many levels does a B+ tree need for 10,000,000 records, using p = 256 and 255 entries per leaf?

If nodes are completely full:

leaves      = ceil(10,000,000 / 255) = 39,216
level above = ceil(39,216 / 256)     = 154
level above = ceil(154 / 256)        = 1     <- root

Three levels: root, one internal level, leaves. A lookup reads 3 index blocks, then 1 data block (if the leaf holds record pointers rather than rows): 4 I/Os.

If nodes are about two-thirds full, a common average after many random inserts (fan-out about 171 for both internal nodes and leaves):

leaves = ceil(10,000,000 / 171) = 58,480
next   = ceil(58,480 / 171)     = 342
next   = ceil(342 / 171)        = 2
root   = 1

Four levels, so 4 index reads + 1 data read = 5 I/Os. Either way, a handful of reads to find one row among ten million.

Capacity check: a three-level tree with fan-out 256 and 255 entries per leaf can index up to 256 × 256 × 255 = 16,711,680 records. A four-level tree, about 4.3 billion. This is why real B+ tree indexes are rarely deeper than 3 or 4 levels.

If the root and the internal level are cached in memory (they total 155 blocks, about 620 KB, in the full-node case), a lookup costs just 2 disk reads: one leaf and one data block.

Search, insertion and deletion

Search

search(key):
    node = root
    while node is not a leaf:
        find the smallest i with key < node.keys[i]
        node = node.children[i]      (last child if no such i)
    look for key in the leaf

Range search low <= key <= high: search for low, then read forward through linked leaves until a key exceeds high.

Insertion

1. Search for the leaf where the key belongs.
2. If the leaf has room, insert the key in sorted position. Done.
3. If the leaf overflows, split it into two leaves and copy the first key of the new right leaf up into the parent as a separator. (The key stays in the leaf, since leaves hold all keys.)
4. If the parent overflows, split it too, but move (push up) the middle key to its parent rather than copying it. Internal separators do not need to stay in both places.
5. If the root splits, create a new root. This is the only way the tree grows taller, so all leaves stay at the same depth.

Worked insertion

Use a small B+ tree where every node holds at most 3 keys (order 4: at most 4 children). Conventions for this example:

• An overflowing leaf with 4 keys splits 2 + 2, and the right leaf's first key is copied up.
• An overflowing internal node with 4 keys keeps the first 2, pushes the 3rd up, and moves the 4th to a new right node.

Insert, in order: 25, 10, 40, 5, 30, 50, 15, 35, 45, 60, 20, 55.

Insert 25, 10, 40. One leaf, which is also the root, sorted:

[10 25 40]

Insert 5. The leaf would hold 5 10 25 40, four keys, so it overflows. Split into [5 10] and [25 40], copy 25 up. The root splits, so a new root is created and the tree grows to two levels.

        [25]
       /    \
 [5 10]      [25 40]

Insert 30. Goes right of 25. The leaf [25 40] has room.

        [25]
       /    \
 [5 10]      [25 30 40]

Insert 50. The right leaf would be 25 30 40 50: overflow. Split into [25 30] and [40 50], copy 40 up. The root becomes [25 40].

          [25 40]
        /    |    \
 [5 10]  [25 30]  [40 50]

Insert 15, 35, 45. Each fits in its leaf without splitting.

               [25 40]
           /      |       \
 [5 10 15]  [25 30 35]  [40 45 50]

Insert 60. The right leaf would be 40 45 50 60: overflow. Split into [40 45] and [50 60], copy 50 up. The root becomes [25 40 50] (three keys, still fits).

                 [25 40 50]
          /       |        |       \
 [5 10 15]  [25 30 35]  [40 45]  [50 60]

Insert 20. It belongs in the first leaf, which would be 5 10 15 20: overflow. Split into [5 10] and [15 20], copy 15 up. Now the root would be 15 25 40 50: four keys, overflow at the internal level. Split it: keep [15 25], push 40 up into a new root, and move [50] to a new right internal node. The tree grows to three levels.

                     [40]
                 /          \
          [15 25]            [50]
         /   |   \          /    \
   [5 10] [15 20] [25 30 35] [40 45] [50 60]

Note that 40 now appears only in the root and in its leaf; it was moved up from the internal node, not copied, while 15 was copied up from a leaf.

Insert 55. Path: 55 ≥ 40, go right; 55 ≥ 50, go right. The leaf [50 60] has room.

                     [40]
                 /          \
          [15 25]            [50]
         /   |   \          /    \
   [5 10] [15 20] [25 30 35] [40 45] [50 55 60]

 leaves linked:
 [5 10] -> [15 20] -> [25 30 35] -> [40 45] -> [50 55 60]

Every leaf is at depth 3, every non-root node is at least half full, and an in-order walk of the leaves gives the keys sorted. A search for 35: root 40 says go left; node [15 25] says 35 ≥ 25, take the third child; the leaf [25 30 35] contains it. Three node reads.

Deletion

1. Find the leaf and remove the key.
2. If the leaf is still at least half full, done. (A separator key in an internal node may stay even if its leaf copy is deleted; it still routes correctly.)
3. If the leaf underflows, try to borrow (redistribute) a key from an adjacent sibling that has more than the minimum, and update the parent's separator.
4. If no sibling can lend, merge the leaf with a sibling and remove the separator from the parent.
5. If the parent underflows, repeat at the next level. If the root is left with a single child, that child becomes the new root, and the tree shrinks by one level.

Many real systems are lazier than the textbook: they allow under-full pages and rely on later inserts or periodic rebuilds (REINDEX in PostgreSQL, OPTIMIZE TABLE in MySQL), because merging on every delete costs more than it saves.

Hash indexes

A hash index stores entries in buckets chosen by a hash function h(key). An equality lookup computes h(key), reads that bucket, and scans it: typically one or two I/Os regardless of table size.

Static hashing

The number of buckets M is fixed: bucket = h(key) mod M. When a bucket fills, extra entries go into overflow blocks chained to it. If the data grows far beyond what M buckets can hold, chains get long and lookups degrade; if it shrinks, space is wasted. Fixing that means rehashing everything into a new M.

Extendible hashing

Extendible hashing grows gracefully using a directory of 2^d pointers to buckets, where d is the global depth. The directory is indexed by the first (or last) d bits of the hash value. Each bucket has a local depth d' ≤ d: the number of bits its entries actually share.

• When a bucket overflows and d' < d, split just that bucket into two (d' + 1 bits) and redirect half of the directory pointers that pointed to it. The directory does not grow.
• When d' = d, first double the directory (d increases by 1, each pointer copied), then split the bucket.

 global depth 2
 directory     buckets
  00 ------->  [A] local depth 2
  01 ------->  [B] local depth 2
  10 --+
  11 --+---->  [C] local depth 1   (shared by 10 and 11)

Only one bucket is split at a time, and lookups need one directory access plus one bucket read.

Linear hashing (brief)

Linear hashing avoids a directory: it splits buckets one by one in a fixed round-robin order (bucket 0, then 1, then 2...), triggered by a load-factor threshold rather than by which bucket overflowed. Overflow chains are tolerated temporarily. It gives smooth growth with no directory doubling.

Where hash indexes are used

PostgreSQL offers CREATE INDEX ... USING HASH (crash-safe since version 10), useful only for pure equality lookups. MySQL InnoDB does not let you create persistent hash indexes (the MEMORY engine does), but it builds an internal adaptive hash index on hot B+ tree pages automatically. Hash tables are also used internally for hash joins and in key-value stores.

Composite indexes and the leftmost-prefix rule

A composite (multi-column) index is built on several columns, such as (customer_id, created_at). Entries are sorted by the first column, then by the second within equal first values, and so on, like a phone book sorted by surname, then first name.

 index on (customer_id, created_at)
 (41, 2025-03-02)
 (42, 2025-01-15)  <-+
 (42, 2025-06-09)    |  all rows of customer 42 are adjacent,
 (42, 2025-11-30)  <-+  and sorted by date within them
 (43, 2025-02-11)

Leftmost-prefix rule: the index can be used for conditions on a leftmost prefix of its columns. For an index on (a, b, c):

Some systems can still use a non-prefix index in special ways: Oracle and MySQL 8.0.13+ have index skip scan, which jumps through each distinct value of a when a has few distinct values; and any system may scan the entire index if that is cheaper than scanning the table. But "the index cannot seek without the leading column" is the rule to state.

Column order guidelines:

1. Put columns compared with equality first, then the column used for a range or sort.
2. Among equality columns, consider which other queries can reuse the index's prefix.
3. Selectivity matters less than often claimed: for pure equality on all columns, the order hardly changes the cost. It matters more for which prefixes other queries can use.

For a query WHERE status = 'PAID' AND created_at >= '2026-01-01' ORDER BY created_at, the index (status, created_at) supports both the filter and the sort. The reversed index (created_at, status) can only seek on the date range and must check status on every entry in it.

Covering indexes

A query is covered when every column it needs (in SELECT, WHERE, ORDER BY, JOIN) is in the index. The database can answer from the index alone, an index-only scan, without visiting the table rows at all. That removes one random I/O per matching row, which can make a query many times faster.

• With index (customer_id, created_at), the query SELECT created_at FROM orders WHERE customer_id = 42 is covered.
• SELECT amount FROM orders WHERE customer_id = 42 is not, because amount is not in the index.

To cover more queries without making the extra columns part of the search key, some systems allow included columns: CREATE INDEX ... ON orders (customer_id) INCLUDE (amount) in PostgreSQL 11+ and SQL Server. In InnoDB every secondary index implicitly contains the primary key, so queries that need only indexed columns plus the primary key are covered automatically.

In PostgreSQL, index-only scans also depend on the visibility map: if a page has recently changed rows, the database must still check the table to see whether each row is visible to the transaction (see concurrency control). Regular VACUUM keeps index-only scans effective.

Seeing it with EXPLAIN

EXPLAIN shows the plan the optimizer chose. The syntax varies: EXPLAIN QUERY PLAN in SQLite, EXPLAIN and EXPLAIN ANALYZE in PostgreSQL and MySQL 8 (the ANALYZE form actually runs the query and reports real row counts and times). The following was run in SQLite on a 100,000-row table:

CREATE TABLE orders (
  order_id    INTEGER PRIMARY KEY,
  customer_id INTEGER NOT NULL,
  status      TEXT    NOT NULL,
  created_at  TEXT    NOT NULL,
  amount      INTEGER NOT NULL,
  email       TEXT    NOT NULL
);

-- 100,000 synthetic rows: 5,000 customers, 4 statuses, dates across 2025
WITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i + 1 FROM n WHERE i < 100000)
INSERT INTO orders
SELECT i,
       i % 5000,
       CASE i % 4 WHEN 0 THEN 'NEW' WHEN 1 THEN 'PAID'
                  WHEN 2 THEN 'SHIPPED' ELSE 'DONE' END,
       date('2025-01-01', '+' || (i % 365) || ' days'),
       (i * 37) % 10000,
       'user' || i || '@ex.com'
FROM n;

No index on the filter column: full scan.

EXPLAIN QUERY PLAN SELECT * FROM orders WHERE customer_id = 42;

QUERY PLAN
`--SCAN orders

Add an index: index search.

CREATE INDEX idx_orders_customer ON orders(customer_id);
EXPLAIN QUERY PLAN SELECT * FROM orders WHERE customer_id = 42;

QUERY PLAN
`--SEARCH orders USING INDEX idx_orders_customer (customer_id=?)

SCAN means read every row; SEARCH means a seek using an index. A lookup by order_id uses the table's own B-tree: SEARCH orders USING INTEGER PRIMARY KEY (rowid=?).

Composite index and the leftmost prefix.

DROP INDEX idx_orders_customer;
CREATE INDEX idx_orders_cust_created ON orders(customer_id, created_at);

EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE customer_id = 42 AND created_at >= '2025-06-01';
-- SEARCH orders USING INDEX idx_orders_cust_created (customer_id=? AND created_at>?)

EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE created_at >= '2025-06-01';
-- SCAN orders              (no leading column, so no seek)

EXPLAIN QUERY PLAN
SELECT created_at FROM orders WHERE customer_id = 42;
-- SEARCH orders USING COVERING INDEX idx_orders_cust_created (customer_id=?)

EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 5;
-- SEARCH orders USING INDEX idx_orders_cust_created (customer_id=?)

The third plan says COVERING INDEX: the query never touches the table. The fourth has no USE TEMP B-TREE FOR ORDER BY line, meaning the index already supplies rows in the required order (read backwards), so no sort is needed.

Functions on the column defeat the index.

CREATE INDEX idx_orders_email ON orders(email);

EXPLAIN QUERY PLAN SELECT * FROM orders WHERE lower(email) = 'user42@ex.com';
-- SCAN orders

EXPLAIN QUERY PLAN SELECT * FROM orders WHERE email LIKE '%42@ex.com';
-- SCAN orders

CREATE INDEX idx_orders_email_lower ON orders(lower(email));
EXPLAIN QUERY PLAN SELECT * FROM orders WHERE lower(email) = 'user42@ex.com';
-- SEARCH orders USING INDEX idx_orders_email_lower (<expr>=?)

The index stores email, not lower(email), so the database cannot seek on the function's result. An expression index (function-based index) on lower(email) fixes it; PostgreSQL, Oracle, SQLite and MySQL 8.0.13+ support them. Similarly, customer_id + 0 = 42 shows SCAN orders; rewrite arithmetic so the bare column is alone on one side.

When indexes are not used, or hurt

When the optimizer will not or cannot use an index

1. Function or expression on the column: WHERE YEAR(created_at) = 2025, WHERE lower(email) = ..., WHERE price * 1.18 > 1000. Rewrite as a range (created_at >= '2025-01-01' AND created_at < '2026-01-01') or create an expression index.
2. Leading wildcard: LIKE '%term' cannot seek. LIKE 'term%' can (with the right collation or operator class; in PostgreSQL with a non-C locale you need text_pattern_ops). For substring search use a full-text or trigram index.
3. Not using the leftmost column of a composite index.
4. Type mismatch and implicit conversion: comparing a string column to a number (WHERE phone = 9845012345 when phone is text) makes MySQL convert every row's value, and the index cannot be used. Comparing an integer column to a string literal is usually fine because the literal is converted once; SQLite, for example, still searches the index for customer_id = '42'. Match types anyway.
5. Low selectivity: if a condition matches a large fraction of rows, reading the whole table sequentially can be cheaper than thousands of random index lookups. Selectivity is the fraction of rows a condition returns; low fraction means high selectivity. A cost-based optimizer decides using statistics, so the threshold differs by system, data layout and storage. In our SQLite test, status = 'PAID' matches 25% of rows and SQLite still chose the index, while PostgreSQL would typically prefer a sequential scan at that fraction. The point is that the optimizer may legitimately ignore your index.
6. OR across different columns: WHERE a = 1 OR b = 2 may need two indexes combined (a "bitmap OR" in PostgreSQL, "index merge" in MySQL) or fall back to a scan. Rewriting as UNION sometimes helps.
7. Negations: <>, NOT IN and NOT LIKE usually match most rows and rarely use an index usefully.
8. Stale statistics: the optimizer estimates row counts from statistics. After big data changes, run ANALYZE so it chooses well.
9. NULL checks: Oracle B-tree indexes do not store rows where all indexed columns are NULL, so IS NULL cannot use them; PostgreSQL, MySQL and SQLite do index NULLs.

When indexes hurt

• Write cost: every INSERT and DELETE must update every index on the table, and every UPDATE must update each index containing a changed column. Ten indexes can make writes several times slower.
• Storage and memory: indexes take disk space and compete for buffer-cache memory with the data itself.
• Page splits and fragmentation: random-key inserts split pages and leave them partly empty.
• Redundant indexes: an index on (a) is usually redundant if (a, b) exists, because the composite index serves a-only queries too.
• Unused indexes: they cost on every write and help nothing. PostgreSQL's pg_stat_user_indexes and MySQL's sys.schema_unused_indexes show which indexes are never used.
• Small tables: scanning a few blocks is as fast as using an index.

What to index

• Primary keys and unique constraints (indexed automatically).
• Foreign key columns: joins use them, and deleting a parent row must find children. PostgreSQL does not index them automatically; MySQL InnoDB does.
• Columns in frequent WHERE, JOIN, ORDER BY and GROUP BY clauses, with composite indexes ordered equality-first, then range or sort.
• Use EXPLAIN ANALYZE on real queries and real data volumes to confirm.

Bitmap indexes (brief)

A bitmap index stores, for each distinct value of a column, a bit array with one bit per row: bit i is 1 if row i has that value.

 rows:      1  2  3  4  5  6  7  8
 gender=F:  1  0  0  1  1  0  1  0
 gender=M:  0  1  1  0  0  1  0  1
 state=KA:  1  1  0  0  1  0  0  1

 F AND KA:  1  0  0  0  1  0  0  0   -> rows 1 and 5

Strengths: very compact for low-cardinality columns (few distinct values: gender, status, region), compress well, and combine multiple conditions with fast bitwise AND/OR/NOT. That suits data warehouses with ad hoc filters on many such columns.

Weakness: updating one row can require locking a large compressed bitmap segment covering many rows, so they perform badly under concurrent OLTP writes.

Support: Oracle offers persistent bitmap indexes (Enterprise Edition). PostgreSQL has no stored bitmap indexes but builds bitmaps at query time ("Bitmap Index Scan" / "Bitmap Heap Scan") to combine several B-tree indexes and to read table pages in physical order. Many columnar warehouses use similar ideas internally.

Other index types worth naming

• Full-text (inverted) index: maps each word to the documents containing it, for search (tsvector/GIN in PostgreSQL, FULLTEXT in MySQL, FTS5 in SQLite).
• GIN and GiST (PostgreSQL): generalized indexes for arrays, JSON, full text, ranges and geometric data.
• Spatial indexes (R-trees): for "points within this map rectangle".
• Partial (filtered) index: indexes only rows matching a condition, such as WHERE status = 'PENDING', keeping it small. Supported in PostgreSQL, SQLite and SQL Server.
• LSM trees: used by write-heavy stores (RocksDB, Cassandra) instead of B+ trees, trading read cost for much cheaper writes. See NoSQL and distributed databases.

Interview questions

Q1. What is an index and what does it cost?

An index is a separate data structure, usually a B+ tree, that maps search key values to row locations so the database can find rows without scanning the whole table. It turns a lookup over millions of rows into a few block reads. The costs are extra storage, extra memory pressure, and slower inserts, updates and deletes, because every index must be maintained on every write.

Q2. What is the difference between a clustered and a non-clustered index?

A clustered index determines the physical order of the rows, or holds the rows in its leaves, so there can be only one per table; range scans on its key are very fast. A non-clustered index is a separate structure with keys and pointers to the rows, and a table can have many. In MySQL InnoDB the clustered index is the primary key, and secondary indexes store the primary key as their pointer.

Q3. What is the difference between a dense and a sparse index?

A dense index has an entry for every search key value; a sparse index has entries for only some, usually the first key of each data block. A sparse index is smaller but works only if the data file is sorted on the search key. Secondary indexes on unsorted columns must be dense.

Q4. Why do databases use B+ trees instead of B-trees?

B+ tree internal nodes contain only keys and child pointers, so more fit in a block, giving higher fan-out and a shallower tree. All records live in leaves that are linked in order, so range scans and ordered reads are just a walk along the leaves. Every lookup has the same predictable depth, and the small internal levels stay cached in memory.

Q5. Why not use a binary search tree or a hash table for database indexes?

A binary search tree has only two children per node, so a million keys need about 20 levels, meaning about 20 random disk reads; B+ trees pack hundreds of keys per node to need 3 or 4. A hash index is fast for equality but cannot support ranges, ordering or prefix searches, which are very common in queries.

Q6. Calculate the order of a B+ tree for block size 4096 bytes, key 8 bytes, pointer 8 bytes.

For an internal node with p pointers and p − 1 keys: 8p + 8(p − 1) ≤ 4096, so 16p ≤ 4104 and p = 256. For a leaf with m key and record-pointer pairs plus a next-leaf pointer: 16m + 8 ≤ 4096, so m = 255. A B-tree, which also stores record pointers in internal nodes, gets only 171.

Q7. How many disk accesses to find a record among 10 million with that tree?

With full nodes, 10,000,000 / 255 gives 39,216 leaves, then 154 internal nodes, then one root: three levels. A lookup reads three index blocks plus one data block, four I/Os. With nodes about two-thirds full it takes four levels and five I/Os, and if the upper levels are cached only the leaf and data reads hit disk.

Q8. What happens when a B+ tree leaf overflows?

The leaf splits into two half-full leaves, and the first key of the new right leaf is copied into the parent as a separator. If the parent overflows, it splits too, pushing its middle key up. If the root splits, a new root is created, which is the only way the tree's height increases, so all leaves stay at the same depth.

Q9. What is the leftmost-prefix rule?

A composite index on (a, b, c) is sorted by a, then b, then c, so it can be used to seek on a leftmost prefix: a, a and b, or a, b and c. A query filtering only on b or c cannot seek with it, because those values are scattered across the index. After a range condition on one column, later columns no longer narrow the seek.

Q10. What is a covering index?

An index that contains every column a query needs, so the database answers from the index alone with an index-only scan and never reads the table rows. It saves one random lookup per matching row. You build one by adding the needed columns to the index key or, in PostgreSQL and SQL Server, as INCLUDE columns.

Q11. Why might the database not use my index?

Common reasons: a function or arithmetic on the indexed column, a leading wildcard in LIKE, a type mismatch that forces conversion of the column, a query that does not use the leading column of a composite index, or low selectivity where a full scan is cheaper. Stale statistics can also mislead the optimizer. EXPLAIN shows the chosen plan, and fixes include rewriting the predicate, adding an expression index, or running ANALYZE.

Q12. Should you index every column?

No. Each index slows every write, consumes storage and memory, and many would never be used. Index primary and foreign keys and the columns used by frequent filters, joins and sorts, prefer a few well-ordered composite indexes over many single-column ones, and remove unused or redundant indexes.

Q13. When are hash indexes better than B+ tree indexes?

When the workload is purely equality lookups on a key, a hash index can find the bucket in about one read regardless of size. It cannot handle ranges, sorting or prefix matches, so B+ trees are the default. Extendible and linear hashing let hash structures grow without rehashing everything.

Q14. What is a bitmap index and where is it used?

It keeps one bit array per distinct value, with a bit per row. It is compact for low-cardinality columns and combines conditions with fast bitwise operations, so it suits data warehouses with ad hoc filters. It handles concurrent row-level updates poorly, so it is not used for OLTP tables.

Q15. Why do random UUID primary keys hurt performance in InnoDB?

InnoDB clusters rows by primary key, so random UUIDs insert all over the B+ tree, causing frequent page splits, half-empty pages and poor cache locality. A 16-byte (or 36-character string) key also enlarges every secondary index, since each stores the primary key. Auto-increment integers or time-ordered UUIDs insert at the right edge and avoid these problems.

Key takeaways

• Query cost is dominated by block reads; an index cuts a million-row search from tens of thousands of reads to a handful.
• Dense indexes have an entry per key; sparse indexes one per block and need a sorted file. A table has one clustered order but many secondary indexes.
• Multi-level indexes and B+ trees reduce search cost to about log base fan-out of the number of blocks.
• B+ trees keep data only in linked leaves, giving higher fan-out, fast range scans and predictable depth; that is why databases use them.
• Compute order by fitting pointers and keys into one block: 4 KB blocks with 8-byte keys and pointers give a fan-out of 256, and 3 to 4 levels index millions to billions of rows.
• Leaves split and copy up; internal nodes split and push up; the tree only grows at the root.
• Composite indexes follow the leftmost-prefix rule; order columns equality-first, then range or sort.
• Covering indexes avoid table lookups; functions on columns, leading wildcards and low selectivity prevent index use.
• Indexes cost writes, storage and memory, so index deliberately and verify with EXPLAIN.

Next lesson

Continue with Transactions and ACID.