深入理解MySql之索引与底层原理

一、是什么

使用Mysql大多时候在增删改查，尤其是查，索引是帮助MySQL高效获取数据的排好序的数据结构。它以文件的形式存储在磁盘中，比如MyISAM存储引擎下的.MYI文件就是存储索引的文件。InnoDB存储引擎是.ibd文件。

它就像书的目录一样，帮你快速查询存储在磁盘上的数据。

二、为啥要用索引

在Mysql中存储的数据要被持久化到磁盘中。在物理存储设备中，每条数据的存储地址并不一定是连续的。

计算机底层是如何存储数据如何查找数据的呢？首先要来看看磁盘这个玩意：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yTtVK0xn-1576499811131)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20191216192935584.png)]

• 从正视图来看，它分为磁盘，磁柱和磁头。从俯视图来看，磁头只能沿着磁盘半径方向移动，也就是寻道操作。磁盘只能绕着圆心旋转，也就是旋转操作。我们的数据被存储在磁道的一个个扇区里。
• **查询数据的操作=寻道+旋转。**寻道耗费时间比旋转要长。所以如果数据都在一个磁道中存储，只用旋转磁盘，查询时间会更快，而如果不是连续的，需要再加上寻道的时间。

所以在选取存储索引的数据结构时，一定要从底层考虑查询数据的效率。如果我们用链表存储索引，我们知道，各个节点的存储空间不是连续的，Pass掉。如果用数组存储，虽然连续，查找也快，但是删除操作和添加操作太慢，也Pass。那有木有高级点的数据结构呢？整个什么什么树之类的？

三、到底用啥数据结构存储索引？

低级数据结构不行，咱们用点高级的。树就行。什么树呢？Hash是不是也行？
数据结构与算法可视化网站–测试下面的几个数据结构

来看看备选项：

• 二叉搜索树（Binary Search Tree）
• 红黑树
• Hash
• Btree
• B+Tree

3.1二叉搜索树行不行

你想啊，咱们现在的索引是递增的（比如主键索引1,2,3,4…N）。用二叉搜索树存，那是不是一直往右边斜了，因为下一个节点总比上一个节点的值大嘛，全存储在右子树了。那完了，本想用树结构寻思能效率高点，结果树整成链表了。因为遇到这种数据（实际也挺常见的），树的高度太高，会退化成链表。

链表查找是O（n）的复杂度，用二叉搜索树最坏也是O（n）了。跟树的高度成正比了。

3.2红黑树行不行

再高级一点。用红黑树。红黑树虽然不像二叉搜索树高度那么高，但是还是不太好。在数据量大的时候，红黑树的高度log（N）也会变的比较大。查找起来还是慢。

3.3试试Hash

Hash不错啊，我们可以先对索引对应的具体数据做一次hash映射，得到一个hash值，然后将这个hash值转换成物理内存中的存储地址。这样在查找的时候，时间复杂度是O（1）。

但是Hash只适合单值查找，不适合范围查找，这是硬伤。

3.4B树

特点：

• 度(Degree)-节点的数据存储个数（如上图根节点存储三个小key-val对，度就是3）。
• 叶节点具有相同的深度
• 叶节点的指针为空
• 节点中的数据key从左到右递增排列

B树有了“度”这个概念，使得整个树变“宽”了，也变“矮了”。矮了好啊，矮了查找时间就快了啊。那就用B树吧，等等，还可以优化的。

这里要说说虚拟内存的知识。我们知道CPU处理数据的时候，是在内存中处理的。这就需要将磁盘中的数据一页一页地（一般来说，一页是一个固定大小，比如4K）读到内存中，处理完再写回去，这就是I/O操作。结合B树索引，在查找数据的时候，会先将若干个大节点（包含度个小节点）从磁盘中读出来，然后再在内存中寻找真正需要的数据。问题来了：

• 如果度过小，尽管一次I/O操作可以拿出多个页，但是数据量一大，树又变高了。
• 如果度过大，由于key-val小节点存储的是索引+数据，极端点想，所有数据存储在一个或仅有的几个大节点中，那么一次I/O操作可能读不完。比如你一个大节点是10M，而一页才4k，这得读多少次。。。。寻道时间很慢的。所以最好一次读完。

如果一个节点大小正好是一页就完美了！

3.5B+树

终于到了主角上场了。来看B+树。

特点

• 非叶子节点不存储data，只存储key，可以增大度
• 叶子节点不存储指针
• 顺序访问指针，提高区间访问的性能

特点一，不存数据了，只存key，那玩意才多小，可以存老多。4k的节点能存很多的key，所以说增大了度。

特点三，最后一层的叶子节点才存储数据。还好心地串起来了，那么在范围查找的时候，就方便很多，不用再从根节点重新往下查。举个例子，查大于18的。找到18，往后遍历就好了，不用再从15开始往下找20,30等等。

四、Mysql咋利用B+树的

Mysql中主要有两种存储引擎。MyISAM和InnoDB。首先要明确，这是表级的存储引擎，不是数据库级别的。你建表的时候可以设置的。

4.1MyISAM

查看data目录我们可以发现，使用MyISAM存储引擎建立的表生成了三个文件：.frm .MYD .MYI第一个是表结构文件。第二个是数据文件。第三个是索引文件。可以知道，MyISAM建立索引的时候，索引和数据是分开建立的，这就是非聚集索引。且它的主键索引和非主键索引的建立方式并无区别。

在查找数据的时候，先在.MYI找到索引对应的数据存储地址（比如15对应0x07的地址），然后拿着地址（0x07）去.MYD文件找数据。

4.2InnoDB

查看data目录我们可以发现，使用InnoDB存储引擎建立的表生成了两个文件：.frm和.ibd。后者表示它的索引和索引指向的数据是在一个文件*同存储的。

4.2.1主键索引：

这很好解释，因为叶子节点的value是数据，而不是MyISAM中的文件地址。所以只需要一个文件就够啦。**这就是聚集索引。**这种索引方式在某些场景下查询速度很快。

4.2.2非主键索引：

可以看到，它的叶子节点的value存储的是主键！这是为啥呢。。。

因为引入了分布式中的数据一致性问题。试想如果还像MyISAM那样，如果多个线程对某个字段进行修改，会有数据不一致的问题。

还有就是为了节省存储空间。因为你主键怎么着也得建个索引对吧，而且主键查询起来快啊（如果是整型非递减的话），所以就算你在非主键上加了索引，如果我把你引到主键上面去，那你可以根据主键索引查询更多的数据段，而这些数据段，不必冗余在非主键索引上（要是字段太多，就浪费空间了不是？）。