【MySQL】索引结构

为数据表增加索引（Index）可以提升MySQL数据查询效率。MySQL中所有类型的数据字段都可以有索引。索引指向了数据表中的记录（行），可以快速判断某行记录是否符合 where 语句中的限定条件。

但是索引并不是越多越好：

• 索引需要耗费存储空间；
• 索引越多，MySQL在决定采用哪个索引时也会消耗更多时间；
• 数据的 增、删、改 都会引起索引的维护操作；

如果总共就一、二千条数据，或目标列的查询使用率很低，或重复索引值占比过高，就没必要创建索引。

 

MySQL中的索引结构

B+Tree

MyISAM 和 InnoDB 都使用了 B+Tree 作为索引的数据结构。

（空间索引 Spatial Index 使用了 RTree）

 

B+Tree 是一种特殊的树形数据结构。

与 B-Tree 相比，B+Tree 的内部节点没有指向data的指针，关键字存储更紧凑。所以关键字在磁盘与内存之间传输时所需读写次数更少。

 

MyISAM：

MyISAM 存储引擎中，叶节点 data 域存放的是数据记录的地址。索引文件和数据文件是分开的。按索引检索时，先找到索引，获得data域中的数据记录地址，再访问相应的数据记录。

MyISAM 中的辅助索引（Secondary Index）与主索引结构相同。区别是辅助索引的key可以重复。

 

InnoDB：

InnoDB 存储引擎中，数据文件本身就是索引文件，叶节点的data域保存了完整的数据记录。

=> 如果主键不是单调字段，Insert 操作可能会导致为了维护B+Tree而频繁调整数据文件。

但是，选取具有实际业务意义的字段作为主键是正确的做法。不要为了单方面的性能而选择一个毫无意义的自增主键。从业务整体考虑性能优化更有意义。

InnoDB 的Table中都有主键。如果没有显式指定主键，MySQL会为其生成一个隐含的字段作为主键。

InnoDB 中辅助索引与主索引结构相同，但其data域存的是主键。按辅助索引检索是，先找到辅助索引，获得data域中的主键，再按主索引找到数据记录。

=> 主键字段内容过长会显著增加辅助索引的存储空间消耗。

 

B+Tree 与 B-Tree 示例：

（图片来自《索引基础——B-Tree、B+Tree、红黑树、B*Tree数据结构》）

 

B+Tree：


B-Tree：

 

Hash Index

Hash Index 是一种常见的索引实现方式。MySQL只将其作为辅助性的索引，因为它不能很好地满足 MySQL 的需求：

• Hash Index 不支持通过比较操作（大于、小于）查找符合某个取值范围的数据。

  Hash Index 只用于“等于（=）”操作。它很适合“key-value”形式的数据存储结构。
  如果有这方面的需求，也许Redis是一个不错的选择。

• Hash Index 无法加速 Order By 操作。

  因为不支持查询“下一条”有序的数据。

• Hash Index 不支持针对取值范围的数据量评估。MySQL需要评估满足取值范围的数据条数，以此决定使用哪个索引。
• Hash Index 只支持整个 key 比对。BTree Index 支持最左部分匹配：只指定索引最左侧部分列也能使用多列索引。

 

网上有很多关于MySQL索引数据结构和算法的详细介绍。那些详细深入数据结构的原理知识可以帮助我们更好地理解MySQL的行为特性，明白那些“最佳实践”背后的原因，进而减少“死记硬背”式的学习过程。其实一名合格的DBA不需要知道这些艰涩的数据结构与算法。能熟读官网上的使用手册，水平就非常不错了（能灵活运用是另一码事）。就好比修车人员不需要知道发动机的设计和制造工序。这远超上层业务应用开发人员的必要水平。当然，如果是为了应付面试，那情况又不同了。“面试造火箭，实际工作工作搬砖”的情况是普遍现象。在很大程度上，这些艰涩知识起到的主要作用是试探应聘者综合基础能力/潜力。