Why MyISAM and InnoDB Indexes Differ Even Though Both Use B+ Trees

MySQL’s MyISAM and InnoDB storage engines both use B+‑tree indexes, but their index structures differ fundamentally. The article creates a sample table and then compares the two engines.

CREATE TABLE `t_user` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `name` varchar(16) DEFAULT NULL,
  `email` varchar(32) DEFAULT NULL,
  `phone` varchar(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `k_name` (`name`)
) ENGINE=InnoDB AUTO_INCREMENT=3 DEFAULT CHARSET=latin1;

1. MyISAM

MyISAM stores index files and data files separately; the index file contains only the storage addresses of data records.

1.1 Primary key index

MyISAM’s B+‑tree index stores index values in non‑leaf nodes, while leaf nodes hold the primary key value plus the data address. This is called a non‑clustered index because leaf nodes do not store the actual row data.

1.2 Non‑primary index

The structure of a non‑primary (secondary) index in MyISAM is identical to the primary index; the only difference is that the index values can repeat. The example shows the structure of the k_name index.

2. InnoDB

InnoDB organizes indexes as clustered B+‑trees. The primary key index’s leaf nodes store the full row records, so the data file itself acts as the index file.

2.1 Primary key index

InnoDB’s primary key index stores the primary key value and the complete row data in the leaf nodes, effectively combining data and index storage.

2.2 Non‑primary index

InnoDB’s secondary index stores only the index value in the leaf nodes; the data column holds the primary key value, requiring a lookup (back‑row) to retrieve the full record.

3. Summary

Although both MyISAM and InnoDB use B+‑tree indexes, MyISAM implements non‑clustered indexes with separate index and data files, while InnoDB uses clustered indexes where the data file is the index file, leading to different storage and lookup behaviors.