Understanding InnoDB Index Structures: B+ Trees, Covering Indexes, and Best Practices

InnoDB stores its indexes using a multi‑way search tree called a B+ tree, where only leaf nodes contain data and all leaf nodes are linked together in a doubly‑linked list.

The choice of B+ trees over binary trees or plain B‑trees is driven by disk‑access characteristics: a shallower tree reduces the number of costly disk seeks, and the leaf‑node linked list enables efficient range scans.

When a table is created, InnoDB builds a B+ tree for each defined index. For example:

create table test(
  id int primary key,
  a int not null,
  name varchar,
  index(a)
) engine=InnoDB;

This statement results in two B+ trees: a clustered primary‑key index that stores the full row in its leaf nodes, and a secondary index on column a whose leaf nodes store only the primary‑key values.

The process of retrieving a column value that is not stored in a secondary index is called row lookup (回表). For instance, executing: select name from test where a = 30; uses the secondary index on a to find the matching primary‑key, then follows the clustered index to fetch the name value.

Index maintenance consumes space, so it should be used judiciously. Using a high‑cardinality integer primary key reduces leaf‑node size compared to a large string key such as an ID card number.

InnoDB also performs necessary maintenance on B+ trees during inserts and deletions, such as node splitting or marking pages as reusable.

A covering index occurs when all columns required by a query are present in the secondary index, eliminating the need for a row lookup. For example: select id from test where a = 1; Here the secondary index on a already contains the id, so the query can be satisfied directly.

Composite (combined) indexes can be created on multiple columns, e.g., on class and name:

CREATE TABLE `stu` (
  `id` int(11) NOT NULL,
  `class` int(11) DEFAULT NULL,
  `name` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `class_name` (`class`,`name`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Such an index allows queries that filter by class to retrieve name without a row lookup.

The left‑most prefix rule dictates that an index can be used only from its leftmost column onward; queries that start with a non‑leftmost column cause a full table scan.

When a range condition appears on the leftmost column, the optimizer may stop using the index for subsequent columns, but index push‑down (available since MySQL 5.6) can still apply remaining predicates at the storage engine level to avoid extra row lookups.

Best practices for index design include:

Create indexes on columns frequently used in WHERE clauses, JOIN conditions, ORDER BY, GROUP BY, or aggregations.

Prefer high‑cardinality columns and avoid indexing columns with low selectivity.

Reuse or extend existing indexes rather than adding redundant ones.

Leverage covering indexes, index push‑down, and respect the left‑most prefix rule to maximize performance.

Author: FrancisQ (original source: https://juejin.im/post/5db19103e51d452a300b14c9)