共计 3065 个字符，预计需要花费 8 分钟才能阅读完成。
大家好，我是啊粥。
接下来的几天咱们会开启一个全新的系列文章，那就是搞定面试官系列，我会把常见的面试常识通过这个专栏写进去，比方咱们常见的 Java、MySQL、Redis、MQ 以及其余的一些技术框架。
当初最先开启的是 MySQL 系列，明天先来分享咱们最常见的一个面试问题，那就是对于 MySQL 的索引。
置信很多人在面试中会遇到对于 MySQL 索引的相干常识，从 MySQL 的架构到索引模型，而后再到表设计，SQL 优化等等。
首先，咱们来看下索引是什么？
索引概述
索引是一种帮忙 MySQL 高效获取数据的有序数据结构。
它的呈现就是为了进步数据的查问效率，就像书的目录一样。如果一本书没有目录，那咱们就必须一页一页的去找咱们本人想要的货色。
然而一旦有了目录，那咱们就能够疾速的通过目录理解书的全貌，而后再依据具体的页码找到咱们本人想要的货色。
MySQL 的索引就是相似的作用，帮忙咱们疾速且高效的获取数据。
索引的常见模型
索引的实现有不同的形式，实质上能够进步查问效率的数据结构有很多种，这里先介绍三种比拟常见的数据结构：
- 哈希表
- 有序数组
- 树形构造
哈希表
以键值（key-value）模式存储数据的构造。哈希的形式非常简单，是用一个哈希函数把 key 换算成一个确定的地位，而后把 value 放在数组的这个地位。
因为哈希算法的起因，多个 key 可能会存在 Hash 抵触，这个时候个别会应用拉链法来解决抵触，也就是雷同 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 个数据块。在机械硬盘时代，从磁盘随机读一个数据块须要 10 ms 左右的寻址工夫。也就是说，对于一个 100 万行的表，如果应用二叉树来存储，独自拜访一个行可能须要 20 个 10 ms 的工夫，这个查问可真够慢的。
所以，咱们须要找到另一种更加适宜用来做 MySQL 索引引擎的数据结构。
Innodb 的索引模型
InnoDB 应用了 B+ 树作为索引构造，所有的元素都会呈现在叶子节点上，同时，叶子节点之间会通过双向链表连贯。
InnoDB 应用 B+ Tree 应用索引构造次要有以下起因：
相比于二叉树，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 里，主键索引也被称为聚簇索引（clustered index），非主键索引也被称为二级索引（secondary index）。
基于主键索引和一般索引的查问有什么区别？
如果语句是 select * from test where id = 5，即主键查问形式，则只须要搜寻 id 这棵 B+ 树；
如果语句是 select * from test where age = 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 命令把表里的数据都删除了，然而表文件的大小却没有发生变化的状况？
如果有的话，欢送留言咱们一起探讨，答案在下一篇文章中揭晓。
我是啊粥，公号同名，关注我，咱们一起在技术陆地中向上成长。
我是啊粥，公号同名，关注我，咱们一起在技术陆地中向上成长。
