Why MySQL Indexes Matter: From B‑Tree to Covering Indexes Explained

What an Index Is

In MySQL an index is a sorted data structure that lets the engine locate rows quickly, similar to how a book's index points to pages.

Tree‑Based Index Structures

Binary Search Trees

A binary tree node has at most two children. In a degenerate (single‑sided) tree, searching a node requires O(n) steps, while a balanced tree reduces the cost to O(log₂n).

Because every node stores actual data, deep trees can cause many node traversals and degrade performance.

Red‑Black Trees

Red‑black trees are self‑balancing binary trees; when a branch exceeds three nodes, the tree automatically rebalances, eliminating the performance issues of plain binary trees.

Hash Tables

Hash tables provide very fast single‑row lookups, but they suffer from collisions, range queries, and other limitations.

B‑Tree

A B‑tree extends binary trees to allow multiple children per node. An M‑order B‑tree can have up to M child pointers, and each internal node stores k‑1 keys (data) and k child pointers, where k is between ⌈M/2⌉ and M.

B+‑Tree

B+‑trees are a variation designed for file systems: only leaf nodes store actual row data, while internal nodes contain only index keys. This structure enables efficient range scans because leaf nodes are linked.

MyISAM vs. InnoDB Index Organization

MyISAM

MyISAM uses a B+‑tree for its indexes. The leaf nodes store the physical address of the row, so the index and the data are stored separately.

InnoDB

InnoDB stores the entire row inside the primary‑key index (a clustered B+‑tree). Consequently every table must have a primary key, and secondary indexes store only the primary‑key value, not the full row.

Index Types in InnoDB

Primary (Clustered) Index

The primary key creates a clustered B+‑tree. If a table lacks an explicit primary key, InnoDB adds a hidden RowId column to serve as the clustered index.

Secondary (Non‑Primary) Index

Secondary indexes maintain their own B+‑tree, but leaf nodes contain the primary‑key value. To retrieve a row, MySQL first finds the primary‑key in the secondary index, then looks up the row in the clustered index, requiring two B+‑tree lookups.

Covering Index

A covering index contains all columns needed by a query, allowing MySQL to satisfy the query using only the index without accessing the clustered data. Benefits include smaller index size, fewer I/O operations, better cache utilization, and, for InnoDB, avoidance of the extra lookup.

Composite (Multi‑Column) Index

When an index spans multiple columns, it follows the left‑most prefix rule: the index can be used only if the query predicates start with the first indexed column and proceed in order. Range conditions (>, <, BETWEEN, LIKE) on a column stop further matching.

CREATE TABLE `test_tb` (
  `id` BIGINT(20) NOT NULL AUTO_INCREMENT,
  `a` VARCHAR(10) NOT NULL,
  `b` VARCHAR(10) NOT NULL,
  `c` VARCHAR(10) NOT NULL,
  `d` INT(10) NOT NULL,
  `e` INT(10) NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `idx_a_b_c` (`a`,`b`,`c`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

Querying only column b does not use the composite index because the left‑most column a is missing, resulting in a full table scan. SELECT * FROM test_tb WHERE b = '10'; In a query like

SELECT * FROM test_tb WHERE a='1' AND b='3' AND d<20 AND c='5';

, the index is used for a and b, but the range condition on d breaks the left‑most order, so c cannot be used.

Visual Illustrations