深入理解MySql之索引与底层原理
深入理解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那样,如果多个线程对某个字段进行修改,会有数据不一致的问题。
还有就是为了节省存储空间。因为你主键怎么着也得建个索引对吧,而且主键查询起来快啊(如果是整型非递减的话),所以就算你在非主键上加了索引,如果我把你引到主键上面去,那你可以根据主键索引查询更多的数据段,而这些数据段,不必冗余在非主键索引上(要是字段太多,就浪费空间了不是?)。