本文为《MySQL归纳学习》专栏的第九篇文章，同时也是关于《MySQL索引》知识点的开篇文章。
MySQL索引是提升数据库查询性能的关键。本文是一系列关于MySQL索引的精彩探索的第一篇，为您揭开索引优化的秘籍。我们首先介绍了InnoDB的索引模型，探讨为什么选择了B+树而非B树作为默认的索引结构。随后，我们详细讨论了索引类型的区分，将聚集索引与非聚集索引进行对比分析。最后，我们分享了关于索引维护的重要注意事项，帮助您精心维护索引以提升查询效率。
首先来看一下这张思维导图，对本文内容有个直观的认识。
接下来进入正文。
索引的常见模型
哈希表
哈希表是一种常见的索引存储结构，它使用哈希函数将键（Key）映射到数组中的位置，从而实现快速的数据访问和查找。
当使用哈希表作为索引存储结构时，哈希冲突是不可避免的。哈希冲突指的是不同的键经过哈希函数计算得到相同的哈希值，导致它们应该存储在数组中的同一个位置。为了解决哈希冲突，哈希表通常使用链表或其他数据结构来处理。
- 优点：高效的查找和插入操作
- 缺点：不支持有序遍历：哈希表的键值对在数组中是无序存储的，这使得它不适用于需要按照顺序遍历元素的场景
哈希表这种结构适用于只有等值查询，且没有大量重复键值的场景，比如 Memcached 及其他一些 NoSQL 引擎。
有序数组
有序数组在等值查询和范围查询场景中的性能就都非常优秀。由于数组的空间连续，查询高效，但是插入删除操作低效。 所以数组用于查询静态稳定的数据。
二叉搜索树
二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。
树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，同等结点的条件下，二叉树比 n 叉树的高度更高，这就意味着需要更多的磁盘 I/O，时间更长。
下面用这样一个例子来说明：
你可以想象一下一棵 100 万节点的平衡二叉树，树高 20，一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10 ms 的时间，这个查询很慢。
为什么平衡二叉树树高为 20，则一次查询需要访问 20 个数据块？
AVL 树（平衡二叉树）在外存的存储结构一般有两种：第一种是顺序存储结构（数组），第二种是链式存储结构（链表），这就导致了在逻辑上很近的节点（父子）在物理上可能很远，无法利用局部性，于是读出的数据块很有可能只有我们想要的一个节点，因此，AVL 的 I/O 渐进复杂度跟树高（h）挂钩，为 O（h）,所以树高 20，其实 I/O的渐进复杂度就为 20。
为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该使用二叉树，而是要使用“N 叉”树。这里，“N 叉”树中的“N”取决于数据块的大小。
以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。
N 叉树中非叶子节点存放的是索引信息，索引包含 Key 和 Point 指针。Point 指针固定为6个字节，假如 Key 为MySQL bigint，则 Key 为 8 个字节，那么单个索引就是 14 个字节。 B+树中数据页默认大小为16K，
16*1024/14≈1200，此时N就差不多等于 1200。
N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。
由上文可知，我们可以根据 Key 值来计算约莫得到N叉树的N值，那么N值受哪些因素影响呢？
1， 通过改变key值来调整
N叉树中非叶子节点存放的是索引信息，索引包含 Key 和 Point 指针。Point 指针固定为6个字节，假如 Key 为10个字节，那么单个索引就是16个字节。 B+树中数据页默认大小为16K，那么一个页就可以存储1024个索引，此时N就等于1024。我们通过改变 Key 的大小，就可以改变N的值。
2， 改变页的大小
页越大，一页存放的索引就越多，N就越大。
InnoDB的索引模型
在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的，这了解 B+树之前，我们有必要认识一下 B树。
B树
B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。
关于B树的定义如下：
其中[m/2] 等价于 Math.ceil(m/2)。
如下图所示，每个节点都会保存数据。
B+树
B+树是B-树的进阶版本，在B-树的基础上又做了如下的限制:
B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。
B+树与B树最大的不同是内部结点不保存数据，只用于索引，内部节点的值都被保存了一份到叶子节点中，所有数据（或者说记录）都保存在叶子结点中。
每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
这样可以带来什么好处呢?
推荐阅读：B树和B+树的插入、删除图文详解
索引类型
InnoDB 存储引擎将 B+树索引分为聚集索引 (clustered index）和辅助索引 (secondary index）两种。聚集索引是通过将表的主键作为键值来构造 B+树。
聚集索引
聚集索引即索引结构和数据一起存放的索引。主键索引属于聚集索引。
在 MySQL 中，InnoDB 引擎的表的 .ibd文件就包含了该表的索引和数据，因为 InnoDB 是把数据存放在B+树中的，而B+树的键值就是主键，在B+树的叶子节点中，存储了表中所有的数据。
聚集索引的非叶子节点存放的是＜键值，地址＞对。地址为指向下一层的指针，InnoDB 存储引擎通过页在表空间中的偏移量来表示。
优点：
数据访问更快，因为整个B+树本身就是一颗多叉平衡树，叶子节点也都是有序的，定位到索引的节点，就相当于定位到了数据。
缺点：
非聚集索引
非聚集索引即索引结构和数据分开存放的索引。二级索引属于非聚集索引。
MYISAM 引擎的表的.MYI文件包含了表的索引， 该表的索引(B+树)的每个非叶子节点存储索引， 叶子节点存储索引和索引对应数据的指针，指向.MYD文件的数据。
非聚集索引的叶子节点并不一定存放数据的指针， 因为二级索引的叶子节点就存放的是主键，根据主键再回表查数据。
优点：
更新代价比聚集索引要小 。
缺点：
主键索引
以 InnoDB 作为存储引擎的表，表中的数据都会有一个主键，即使你不创建主键，InnoDB 会选择一个唯一的非空索引代替。如果没有这样的索引，则 InnoDB 会选择内置6字节长的 ROWID 作为隐含的主键索引(ROWID随着行记录的写入而主键递增，这个 ROWID 不像 ORACLE 的 ROWID 那样可引用，是隐含的)。
二级索引(辅助索引)
二级索引又称为辅助索引，是因为二级索引的叶子节点存储的数据是主键。也就是说，通过二级索引，可以定位主键的位置。
唯一索引，普通索引，前缀索引等索引属于二级索引。
基于主键索引和普通索引的查询有什么区别？
- 如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；
- 如果语句是 select * from T where k=5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。
也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。
平时我们更多接触的名称是主键索引和二级索引，那么它们的叶子节点存的是什么？
InnoDB磁盘管理的最小单位就是“页”，也就是说无论是叶子节点、非叶子节点和行数据，都是存放在页当中。页的组成结构有头部数据、主体数据和尾部数据。
头部数据主要存的是页相关数据，例如上一页、下一页、当前页号等。是一个双向链表结构。
主体数据主要关注索引和数据的存储，也就是我们常说的索引和数据的存储位置。主体数据当中有一个“User Records”的概念，用来存储索引和数据，是一个单链表结构。User Records根据节点的不同，User Records又分为四种不同类型：主键索引树叶子节点和非叶子节点，二级索引树叶子节点和非叶子节点。
有了页和User Records的认识，其实说叶子节点存的是页是一种笼统的回答，基于我的理解，我认为叶子节点（主键索引树叶子节点）存放的是行数据更为贴切。
索引维护
根据前面 B+树算法的讲解，当子树中的数据满了，如果此时该子树新增一条数据记录，则需要新增一个子树，然后挪动部分数据过去，这个过程叫做页分裂。在这种情况下，性能会受到影响，除此之外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。
当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。
自增主键防止页分裂
你可能在一些建表规范里面见到过类似的描述，要求建表语句里一定要有自增主键。我们来分析一下哪些场景下应该使用自增主键，而哪些场景下不应该？
自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的： NOT NULL PRIMARY KEY AUTO_INCREMENT。
插入新记录的时候可以不指定 ID 的值，系统会获取当前 ID 最大值加 1 作为下一条记录的 ID 值。
也就是说，自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
如果拿业务字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。
除了考虑性能外，我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？ 答案是采用自增字段做主键，为什么呢？
因为每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约 20 个字节，而如果用整型做主键，则只要 4 个字节，如果是长整型（bigint）则是 8 个字节。
显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
有没有什么场景适合用业务字段直接做主键的呢？还是有的。比如，有些业务的场景需求是这样的：
逻辑删除可以防止页合并
页合并是InnoDB存储引擎的内部优化机制，其工作流程如下：
- 当您删除一条记录时，不会实际删除该记录，而是将记录标记为已删除，并且该记录使用的空间可回收。
- 当一个页删除足够多的数据，达到合并阈值（默认是页大小的50%），InnoDB开始找相邻的页（之前和之后的）查看它们是否有机会合并两个页，优化空间使用率。
从上可以看出，页合并是用来优化空间的使用，提升页的利用率。
但是，如果两个页pageA和pageB都只有少量的可复用空间，那么合并后，即使pageA可以填满，但是另一个页Page也还是有碎片空间的，并且碎片更大，这时候数据移动的开销可能要大于存储的开销，得不偿失。
综上，页合并既可以提升空间利用率，但也可能造成不好的影响，比如说页合并过程涉及读取、修改和写入数据页的操作，这些操作会增加系统的I/O负载和CPU开销，可能导致性能下降。
根据上述描述，可以发现逻辑删除而非物理删除，可以防止页合并，但实际应用中，我们采用逻辑删除可能并非是为了防止页合并。
重建索引
为什么要重建索引？
索引可能因为删除，或者页分裂等原因，导致数据页有空洞，重建索引的过程会创建一个新的索引，把数据按顺序插入，这样页面的利用率最高，也就是索引更紧凑、更省空间。
下面我们通过一个案例来分析哪种方式重建索引是合理的。
对于某个 InnoDB 表 T，如果你要重建索引 k，你的两个 SQL 语句可以这么写：
alter table T drop index k;
alter table T add index(k);
如果你要重建主键索引，也可以这么写：
alter table T drop primary key;
alter table T add primary key(id);
对于上面这两个重建索引的作法，说出你的理解。
重建索引 k 的做法是合理的，可以达到省空间的目的。另外删除重建普通索引影响不大，不过要注意在业务低谷期操作，避免影响业务。
首先我们需要知道的是： 如果删除、新建主键索引，会同时去修改普通索引对应的主键索引，性能消耗比较大。直接删除主键索引，会使得所有的二级索引都失效，并且会用 ROWID 来作主键索引。
然后基于本例，重建主键的过程不合理。不论是删除主键还是创建主键，都会将整个表重建。所以连着执行这两个语句的话，第一个语句就白做了。这两个语句，你可以用这个语句代替 ： alter table T engine=InnoDB。
扩展：MySQL 官方文档提供了三种解决措施。
1、将整个数据库迁移，先 dump 出来再重建表（这个一般只适合离线的业务来做）
2、用空的 alter 操作，比如 ALTER TABLE T ENGINE = InnoDB; 这样子就会原地重建表结构
3、用 repaire table，不过这个是由存储引擎决定支不支持的（innodb就不行）。
以上内容便是本文所讲的内容，更多是理论知识的讲解，下节会贴合实际应用，通过不少案例为大家讲述索引的使用。
