MySQL索引：提升查询性能的核心数据结构
索引到底是什么？简单来说，索引是MySQL用于快速定位数据的一种数据结构。如果没有索引，数据库查询就像翻阅一本没有目录的书籍，只能逐页查找，效率极低。
常见索引数据结构详解：二叉树、红黑树、Hash表与B-Tree
常见的索引数据结构有多种，但各自存在明显短板：
- 二叉树：虽然能在一定程度上加快查询速度，但容易形成“单边树”，退化后与链表无异，查询效率并无实质提升。
- 红黑树：与二叉树面临相似问题，极端情况下同样可能形成单边树，无法确保稳定高效的查询性能。
- Hash表：等值查询速度极快，但缺点是不支持排序，范围查询也完全无法实现。
- B-Tree：所有节点均存储数据，且节点内的数据从左到右递增排列。相比之前的几种数据结构，性能已有显著提升。
B+Tree：B-Tree的优化变种，MySQL的最终选择
MySQL真正使用的索引数据结构，其实是B+Tree。它和B-Tree有什么区别？关键看三点：
- 非叶子节点仅存储索引，不保存数据，这称为“高阶冗余”，使得每个节点能容纳更多索引项。
- 叶子节点存储所有索引字段，并按照从左到右递增的顺序排列。
- 叶子节点之间通过双向指针连接，显著提升了范围查询和顺序访问的效率。
为什么MySQL最终选择B+Tree？深入解析性能优势
B+Tree的每个节点默认分配16KB的空间。粗略估算，16KB可容纳约1170个索引项。一个三层B+Tree结构，通过1170×1170×16的计算，大约能支撑2000万条数据。因此，生产环境中通常建议MySQL单表数据量控制在1000万条左右，超出后应考虑分库分表。不过，MySQL的横向扩容实现相对简单。
MySQL的数据引擎是表级别的，而非数据库级别的。这一点需要牢记。不同存储引擎的索引实现方式差异显著：
- MyISAM
MyISAM采用非聚集索引，叶子节点存储主键的指针，索引文件与数据文件分离。查询索引后，仍需回表获取实际数据。此外，MyISAM不支持事务。
- InnoDB
InnoDB是目前最常用的存储引擎，采用聚集索引。主键索引的叶子节点直接存储整行数据。对于其他索引（如组合索引、唯一索引、普通索引），如果查询所需的字段已包含在索引中，则无需回表。这里的“回表”是指再次查询主键索引以获取缺失字段，而非读取数据文件。若索引未覆盖所需字段，则必须回表。因此，在实际索引优化中，应优先使用覆盖索引，以减少回表带来的性能开销。
此外，建议使用自增主键。这样新增数据时，只需在索引末尾追加，无需插入中间位置。如果表中未定义主键，InnoDB会自动生成一个虚拟主键，并基于它创建主键索引。
总结：MySQL索引优化的核心要点
从二叉树到B+Tree，再到不同存储引擎的索引实现，核心思想始终如一：选择合适的数据结构，最大限度地减少磁盘I/O。在实际开发中，善用覆盖索引并避免回表操作，是MySQL索引优化中最常用且最有效的手段之一。
