Indexing in DBMS: B+ Tree, Clustered and Hash Index

Finding one student among a million by reading every row is like finding a topic in a textbook by reading every page. An index is the book's index for a table: a separate, sorted structure that says where each value lives. With the right index a lookup touches a handful of disk pages instead of thousands. This note covers the kinds of index, dense and sparse and multilevel indexes, then the B+ tree that almost every relational database uses, with search and insertion worked step by step, and ends with hash indexes, the cost of indexes and the leftmost-prefix rule for composite ones.

Why indexes

Databases read and write data in pages (blocks) of a fixed size: 16 KB in InnoDB, 8 KB in PostgreSQL. The cost of a query is roughly the number of pages it reads. Suppose a table of 1,000,000 students fits 100 rows to a page: that is 10,000 pages, and a query by roll number without an index reads all of them.

A B+ tree with a fan-out (children per node) of 100 and 100 keys per leaf needs only three levels for that table:

Real fan-outs are larger, often several hundred keys per 16 KB page for small keys, so three or four levels cover very large tables.

The terms: the search key is the column (or columns) an index is built on, which need not be a primary or candidate key. An index entry is a search-key value with a pointer to the row or the block holding it. Ordered indexes keep entries sorted (B+ trees); hash indexes spread them across buckets with a hash function.

Primary, clustering and secondary indexes

In everyday database language the two words are clustered and non-clustered. A clustered index determines how the rows are physically ordered, so a table can have only one. In MySQL's InnoDB the table is a B+ tree on the primary key, with whole rows in its leaves. A secondary index in InnoDB stores (indexed value, primary key) in its leaves, so finding a row through it takes two tree walks: the secondary index to get the primary key, then the clustered index to get the row. If the secondary index already contains every column the query needs, the second walk is skipped; such an index is covering for that query, and EXPLAIN shows "Using index".

Dense and sparse indexes

Take a data file sorted on roll_no, three records to a block, and look for 105 both ways:

A sparse index is smaller, but it needs the file sorted on the search key, which is why only a primary or clustering index can be sparse. A secondary index must be dense, because the rows are not in its order.

Multilevel indexes

An index on a large table is itself large. If an inner index has 10,000 entries and 100 fit in a block, it spans 100 blocks, and binary search over them costs about ⌈log₂ 100⌉ = 7 block reads. Build a sparse outer index on the inner index, one entry per inner block: 100 entries, one block. Now a lookup reads the outer block, one inner block and the data block: 3 reads. Repeating the idea until the top level fits in one block gives a multilevel index. A B+ tree is a multilevel index that stays balanced automatically as rows are inserted and deleted.

B-tree vs B+ tree

When a database's documentation says "B-tree index", it almost always means a B+ tree: InnoDB and PostgreSQL both use B+ trees.

B+ tree structure

This note uses a B+ tree of order 4: a node has at most 4 children and therefore at most 3 keys. Textbooks define "order" differently (maximum children, maximum keys, or minimum keys), so in an exam, state your convention. The rules:

• Every leaf is at the same depth: the tree is always balanced.
• An internal node with k keys has k + 1 children. Keys in child i are at least key i−1 and less than key i.
• Every node except the root is at least half full: internal nodes have 2 to 4 children, leaves 2 to 3 keys.
• Leaves hold every key (with its row or row pointer) and are linked left to right.

Splitting conventions used below. A leaf that overflows to 4 keys splits into two leaves of 2 keys each, and the first key of the right leaf is copied up into the parent (it must stay in the leaf too). An internal node that overflows to 4 keys keeps the first 2, moves the third up to its parent, and gives the fourth to a new right node.

Worked example: inserting into a B+ tree

Insert 10, 20, 30, 40, 50, 15, 25, 35, 45, 55 into an empty order-4 B+ tree:

1. The tree starts as one leaf that is also the root. 10, 20, 30 fit, because an order-4 node holds at most 3 keys, kept sorted.
2. 40 belongs in the same leaf, which would then hold 4 keys, one more than the limit of 3. A node that overflows must split.
3. The leaf splits into [10 20] and [30 40], and the right half's first key, 30, is copied up into a new root. It stays in the leaf too, because every key lives in a leaf; the root's copy is only a signpost.
4. 50 ≥ 30, so it follows that pointer: [30 40 50] still has room, so 50 simply fits. Nothing above the leaf changes.
5. 15 < 30, so it goes left: [10 15 20] still has room, so 15 simply fits. Nothing above the leaf changes.
6. 25 makes a full leaf overflow, so it splits into [10 15] and [20 25] and copies 20 up: the parent becomes [20 30].
7. 35 makes a full leaf overflow, so it splits into [30 35] and [40 50] and copies 40 up: the parent becomes [20 30 40], now full.
8. 45 ≥ 40, so it follows that pointer: [40 45 50] still has room, so 45 simply fits. Nothing above the leaf changes.
9. 55 lands in a full leaf, which splits into [40 45] and [50 55], copying 50 up. Now the root holds [20 30 40 50], 4 keys: it overflows too.
10. An internal node splits differently: it keeps [20 30], moves 40 up into a new root and gives [50] to a new right node. 40 is moved, not copied, so it is no longer at that level. The tree grew at the top, so every leaf stays at the same depth.

The final tree has three levels: root [40]; internal nodes [20 30] and [50]; leaves [10 15] [20 25] [30 35] [40 45] [50 55], linked left to right. Check it against the rules: every leaf is at depth 3 and holds 2 or 3 keys, every internal node has 2 to 4 children (the root may have as few as 2), and 40 and 50 appear both as signposts and in leaves, because leaf splits copy keys up while the internal split moved 40 out of its node.

Searching

A point lookup follows one pointer per level; a range query finds its first key the same way and then follows the leaf links:

1. Lookup 35: at the root, 35 < 40, so go left; at [20 30], 35 ≥ 30, so take the third pointer; the leaf [30 35] holds it. 3 page reads, one per level.
2. Lookup 22 follows the same rules to the leaf [20 25] and finds no 22 there. A miss also costs exactly one read per level: every search ends at a leaf.
3. Range 22 to 42: descend as for 22 to [20 25], then follow the leaf links right, collecting 25, 30, 35, 40, and stop at 45, the first key past 42. The tree is never climbed again.

The links are what make B+ trees good at BETWEEN, > and ORDER BY.

Deletion mirrors insertion: remove the key from its leaf; if the leaf falls below half full, borrow a key from a sibling or merge with it, and fix the parent's signposts. Merges can cascade up and shrink the tree by one level. Search, insertion and deletion each cost O(log n) page reads, where the base of the logarithm is the fan-out.

Hash indexes

A hash index applies a hash function to the search key and stores the entry in the resulting bucket. An equality lookup (WHERE email = '…') costs about one bucket read on average, independent of table size. But hashing destroys order, so a hash index cannot answer ranges, ORDER BY or prefix searches such as LIKE 'abc%'. Collisions go into overflow chains, and dynamic schemes (extendible and linear hashing) grow the table without rehashing everything.

In practice: MySQL's MEMORY engine supports explicit hash indexes; InnoDB uses B+ trees and builds an internal adaptive hash index over frequently used pages on its own; PostgreSQL offers CREATE INDEX … USING hash.

The cost of an index

Indexes are not free:

• Writes: every INSERT and DELETE updates every index on the table, and an UPDATE updates each index containing a changed column, sometimes splitting pages.
• Space: each index is another tree on disk and competes for the buffer pool in memory.
• Choice: the optimizer may ignore an index that matches a large fraction of rows (low selectivity, such as a yes/no column), because a sequential scan is cheaper than thousands of random lookups.

Index the columns that appear in frequent WHERE, JOIN and ORDER BY clauses, check with EXPLAIN, and drop indexes nothing uses.

Composite indexes and the leftmost-prefix rule

A composite index covers several columns, for example CREATE INDEX idx ON employees (dept, city, salary). Its entries are sorted by dept, then by city within each dept, then by salary within each (dept, city), like names in a phone book sorted by surname then first name. So it can only seek on a leftmost prefix of its columns:

1. The index keeps its 9 entries sorted by dept, then city, then salary. dept = 'CSE' is a leftmost prefix, so its 4 entries sit together: one seek to the first, then read until dept changes.
2. Equality on dept and city narrows the run to CSE, Pune, which is sorted by salary inside, so salary > 50000 is a range at its end: 2 entries, found by seeking on all three columns.
3. city = 'Pune' skips the leading column. Its 6 entries are scattered through 3 separate runs, one per department, so the index offers no single range to seek and the query must scan.
4. With dept = 'CSE' AND salary > 50000, city sits between them unused, so salary is not sorted inside the CSE run. The index seeks dept, then checks salary on each of the 4 entries and keeps 3.

MySQL 8.0.13 and later can sometimes use a skip scan for a condition on a non-leading column, but do not design around it. Put equality columns first and the range column last, and prefer the more selective equality column first when queries use both.

Common mistakes

• Thinking a table can have several clustered indexes: it is stored in one order only.
• Indexing every column: writes slow down and most of the indexes are never used.
• Expecting an index on (a, b) to help WHERE b = …: it is not a leftmost prefix.
• Using a hash index for range queries or sorting: hashing destroys order.
• Forgetting that leaf splits copy the key up while internal splits move it.
• Wrapping an indexed column in a function, such as WHERE YEAR(joined) = 2025: the B+ tree is sorted on the column, not the function, so the index cannot seek.

Interview questions

What is an index and why does it speed up queries? A sorted (or hashed) structure from search-key values to rows. It replaces a full scan of every page with a walk down a tree of a few levels, so a lookup reads a few pages instead of thousands.

What is the difference between a B-tree and a B+ tree? A B-tree stores data pointers in every node; a B+ tree stores them only in linked leaves and uses internal keys purely as signposts. B+ trees have higher fan-out, shorter height and fast range scans, which is why databases use them.

What is the difference between a primary and a secondary index? A primary index is built on the key the file is sorted by and can be sparse; there is one per file. A secondary index is built on any other column, must be dense and can be added many times.

What is a covering index? An index that contains every column a query needs, so the query is answered from the index alone without reading the table rows. In InnoDB, a secondary index on (dept, salary) covers SELECT salary FROM employees WHERE dept = 'CSE'.

When will a database not use an index? When the condition is not on a leftmost prefix, when the column is wrapped in a function or compared with an implicit type conversion, when a LIKE pattern starts with %, or when so many rows match that a scan is cheaper.

What is the height of a B+ tree with fan-out 100 holding a million keys? About three levels, since 100³ = 1,000,000. Each lookup reads one page per level, so three index pages plus the row's page.

What happens when a B+ tree node overflows? It splits in two. A leaf copies its new right half's first key up to the parent; an internal node moves its middle key up. If the root splits, a new root is created and the tree grows by one level.

Why should the primary key of an InnoDB table be short? Every secondary index stores the primary key in each entry, so a long primary key makes every index larger. A short, increasing key such as an auto-increment integer also appends to the end of the clustered index instead of splitting pages in the middle.

Next, the databases that are not relational at all: SQL vs NoSQL Databases. Index design is examined in the SQL (Intermediate) skill test.