大家好，我是粥。在接下来的几天里，我们将开始一个新的系列文章，即get面试官系列，我会通过这个专栏来写常见的面试知识，比如我们常见的Java、MySQL、Redis、MQ等技术框架。现在首先入手的是MySQL系列。今天，让我们分享一个最常见的面试问题，这是关于MySQL索引的。相信很多人在面试的时候都会遇到MySQL索引的相关知识，从MySQL架构到索引模型，再到表设计、SQL优化等等。首先我们来看看什么是索引？索引概述索引是一种有序的数据结构，可帮助MySQL高效地检索数据。它的出现是为了提高数据的查询效率，就像书籍的目录一样。如果一本书没有目录，那么我们就必须一页一页地查找我们想要的内容。但是一旦有了目录，我们就可以通过目录快速了解这本书的全貌，然后根据具体的页码找到我们想要的内容。MySQL的索引就是类似的功能，帮助我们快速高效的获取数据。索引的实现方式多种多样，可以提高查询效率的数据结构也有很多种。这里介绍三种常见的数据结构：哈希表、有序数组、树结构、哈希表和key以key-value的形式存储数据的结构。散列的方式非常简单。它使用哈希函数将键转换到某个位置，然后将值放在数组的这个位置。由于哈希算法的原因，多个键可能会发生哈希冲突。这时一般会采用拉链的方式来解决冲突，即拉出一个hash值相同的链表。哈希表的结果对于等价查询是非常快的，但是因为它是无序的，如果用于范围查询会很慢。比如我们有一张用户名和身份证号的表，它以哈希表的形式存储如下：如果将上述数据存储在有序数组中，其结构为：有序数组可分为两种方法进行数据检索的速度非常快，时间复杂度为O(log(N))。但是更新数据会比较麻烦，因为需要维护顺序，所以每次插入数据需要移动太多元素，成本太高。因此，有序数组只适用于静态存储引擎。同理，如果用二叉树存储，则二叉查找树的结构如下：父节点左子树中所有节点的值都小于父节点的值，且所有节点的值右子树中节点的值大于父节点的值。这样如果要查id_card_03，按照图中的查找顺序，按照路径USERA->USERC->USERF->USER_03就可以得到。这个时间复杂度是O(log(N))。当然，为了保持O(log(N))的查询复杂度，需要保持这棵树为平衡二叉树。为了保证这个，更新的时间复杂度也是O(log(N))。二叉树是最高效的搜索，但实际上大部分数据库存储并不使用二叉树。原因是索引不仅存储在内存中，还写入磁盘。N叉树由于其在读写方面的性能优势，以及适配磁盘的访问方式，在数据库引擎中得到了广泛的应用。但是，二叉树的种类也很多，例如B-Tree、B+Tree、红黑树等。一般来说，100万个节点的平衡二叉树的高度为20，一次查询可能需要访问20个数据块。在机械硬盘时代，从磁盘中随机读取一块数据需要大约10ms的寻址时间。也就是说，对于一个100万行的表，如果用二叉树来存储，访问单行可能需要20次10ms。这个查询真的很慢。因此，我们需要寻找另一种更适合MySQL索引引擎的数据结构。InnoDB的索引模型InnoDB使用B+树作为索引结构，所有的元素都会出现在叶子节点上，同时叶子节点之间会通过一个双向链表连接起来。InnoDB使用B+树来使用索引结构主要有以下几个原因：与二叉树相比，B+数层次更少，查找效率更高。以InnoDB的一个整型字段索引为例，这个N差不多是1200。当这棵树的高度为4时，它可以存储1200个3的值，已经是17亿了。考虑到树根处的数据块一直在内存中，在一个10亿行的表上的整数字段上的索引最多需要3次磁盘访问才能查找一个值。事实上，树的第二层很有可能在内存中，所以平均访问磁盘的次数就更少了。B树的叶子节点和非叶子节点都会存储数据，会减少一个页中存储的键值，指针也会相应减少。要保存同样的数据量，只能增加树的高度，导致搜索性能下降。在InnoDB中，表按照主键的顺序以索引的形式存储，这种存储方式的表称为索引组织表。InnoDB中每一个索引对应一个B+树。假设表中T1~T5的(id,age)值分别为(1,10)、(2,20)、(3,30)、(5,50)和(6,60)，这两个索引树示例示意图如下所示。主键索引树和二级索引树从图中不难看出，两个索引的叶子节点的内容是不一样的。根据叶子节点的内容，索引类型可以分为主键索引和非主键索引。主键索引的叶子节点存储整行数据。非主键索引的叶子节点存储主键的值。在InnoDB中，主键索引也称为聚簇索引，非主键索引也称为二级索引。基于主键索引和普通索引的查询有什么区别？如果语句是select*fromtestwhereid=5，即主键查询方式，只需要查找id的B+树即可；如果语句是select*fromtestwhereage=50，即普通索引查询方式，需要先查找age索引树，得到id为5的值，再在id索引树中查找。这个过程称为回表，即基于非主键索引的查询需要扫描额外的索引树。因此，我们应该在应用中尽量使用主键查询。索引维护的代价B+树为了维护索引的顺序，在插入新值时需要做必要的维护。以上图为例，如果插入一个id值为7的新行，只需要在T5记录后插入一条新记录即可。如果新插入的ID值是4，就比较麻烦了。需要对后续数据进行逻辑上的移动，为4腾出空间，B+树需要进行结构上的改变，以保持平衡和节点顺序。更糟糕的是，如果T5所在的数据页已满，根据B+树算法，此时需要申请新的数据页，然后再将部分数据搬过来。此过程称为页面拆分。在这种情况下，性能自然会受到影响。除了影响性能，分页操作还会影响数据页的利用率，因为原来放在一页的数据现在分成了两页，整体空间利用率会降低50%左右。同样的，哪里有分裂，哪里就有合并。当相邻的两个页由于删除数据而使用率很低时，会合并数据页。合并的过程可以看作是分裂过程的逆过程。合并使用率低的页面数据后，另一个数据叶子会被标记为可重复使用，以供后续数据利用，那么为什么我们推荐使用自增主键，因为自增主键的插入数据方式正好符合我们之前的提到的增量插入场景。每插入一条新记录，都是一次追加操作，所以不涉及移动其他记录，也不会触发叶子节点的分裂。反之，如果使用业务逻辑字段作为主键，往往不能保证有序插入，因此写入数据的成本会比较高。好吧，简单总结一下：MySQL选择B+树作为索引模型来存储数据，这样既可以合理利用磁盘特性，也可以让范围查询变得非常方便。同时，由于B+树在非叶子节点不存储数据，只在叶子节点存储数据，B+树和高度相同的B树，B+树可以存储更多的数据，反之，相同数据量越大，B+树的高度越低，假设每个节点搜索的是一次磁盘IO，那么，B+树可以花费更少的时间来获取需要的数据。今天我们就在这里介绍一下MySQL的索引模型。我在文章末尾给你留了一个问题。你有没有遇到过你执行了delete命令删除了表中的所有数据，但是表文件的大小却没有变化？健康）状况？如果有，请留言让我们一起探讨，下一篇文章揭晓答案。我是粥，与公众号同名，关注我，我们一起在科技的海洋中向上成长。我是粥，与公众号同名，关注我，我们一起在科技的海洋中向上成长。
