本文主要是介绍深入理解MySQL索引底层数据结构,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
什么是索引
索引是帮助MySQL高效获取数据的排好序的数据结构
若没有使用索引的话,查找数据的时候会从上到下一条一条的向下查找,直到找到数据为止,索引的目的是为了提高查找速度的。
索引的数据结构
二叉树
![](/upload/202204/24/202204240212511953.png)
如图所示,若采用二叉树,的确能提高查找的速度。对于 col2 列的 89 来说,使用索引之前需要 6 次查找,而使用二叉树做索引之后,只需要 2 次查找即可
但是,对于 col1 列来说,查找对应的那条记录同样需要 6 次。这是为什么?对于二叉树来说,若采用递增的列作为索引的话,二叉树会退化成链表
红黑树
![](/upload/202204/24/202204240212512890.png)
本质上还是一个二叉树,叫做二叉平衡树。平衡树在插入和删除的时候,会通过旋转操作将树的左右节点达到平衡
红黑树规则定义:
- 任何一个节点都有颜色,红色或黑色
- 根节点是黑色的
- 父子节点之间不能出现两个连续的红节点
- 任何一个根节点,遍历到它的子孙节点,所经过的黑节点树必须相同
- 空节点被认为是黑色的
若采用红黑树作为索引的数据结构,当数据量特别大的时候,黑红树的高度就特别大了。假如有 500w 条数据,那么红黑树的高度可能达到几十甚至更多,要经过大量的磁盘 I/O 操作,性能太差了,若要解决这一问题,就要减少 I/O 的次数
B树(B-Tree) 和 B+树(B+Tree)的选择
B-Tree
![](/upload/202204/24/202204240212513843.png)
- 叶节点具有相同的深度,叶节点的指针为空
- 所有索引元素不重复
- 节点中的数据索引从左到右递增排列
B+Tree
![](/upload/202204/24/202204240212514936.png)
- 非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用指针连接,提高区间访问的性能
对比B-Tree和B+Tree
- B-Tree的所有节点都存储了 data 元素,B+Tree 的非叶子节点不存储 data 元素,则 B+Tree 的一个非叶子节点可以存储更多的索引
- B+Tree在叶子节点之间增加了指针,对于范围查找来说,有很好的支持
这篇关于深入理解MySQL索引底层数据结构的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!