[MySQL]再谈索引

红太狼 2022-11-29 12:59 47阅读 0赞

在这篇文章: [\[mysql\]手把手教你给 SQL 做个优化][mysql_ SQL] 中介绍了,给 SQL 做优化的时候,最主要的一点就是建索引  
那你有没有新的疑问呢?  
索引采用的数据结构是啥呢,为什么一提到 mysql 就会问 B 树, B+ 树呢  
今天这篇文章来说说

在我们给数据库中一个字段建立索引的时候,能够看到可以选择是 Hash 类型,还是 BTREE 类型的索引  
![在这里插入图片描述][20200821132224627.jpg_pic_center]  
那为什么 InnoDB 引擎默认使用的是 B+ 树而不是 Hash 嘞  
你想,你细想  
使用 Hash 的话很容易出现哈希冲突,特别是在数据量非常大的时候,出现了大量的哈希冲突会导致程序的整体查询性能变慢  
假设我现在有个查询语句是这样写的 `select name,age from student where age > 18` 这不是蛮简单的嘛,就找出来所有 age 大于 18 的数据就可以了嘛  
但是对于使用 Hash 数据结构的索引来说,太难了.因为 Hash 是 key-value 的结构,所以它擅长的是精确查询,如果你让它查找 `select name,age from student where age = 18` 它返回结果就非常快了  
那既然 Hash 不支持范围查询,支持 key-value ,那它的应用场景是啥呢?就是等值查询咯,给我一个 key 就可以快速回应一个 value ,咦?怎么和 Redis 那么像呢?  
就是嘛, Redis , Memcached 它们都有用到 Hash 结构

Hash 不支持范围查找,但是有序数组支持啊  
那为啥不用有序数组嘞  
没错,有序数组的查询性能可以说非常好了,不管是等值查询,还是范围查询,效率简直完爆其他  
但是咱们的应用场景又不是只有查询对吧,还有插入,修改,删除呢,有序数组这个时候就顶不住了  
特别是如果插入到头部,第一个位置,从第二位开始往后都要开始向后移动,将第一个位置空出来,这么一来,我的天,还没等你插入完毕,用户都等不及跑了

那新的疑惑来了  
B+ 树属于树的一种,二叉树也是树的一种,你咋不用二叉树呢  
你想,你再想  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70_pic_center]

二叉树是每个节点最多只有两个分支,每个节点只存储一个数据的树结构,那如果我的数据量非常大的话呢,比方说一个小目标, 1 亿数据  
这个时候二叉树的高度就会变得非常高  
既然是数据,不做持久化嘛?肯定是要持久化到磁盘的,而且就目前公司的成本来说,应该还没富到服务器的硬盘全是固态吧,有些还是机械硬盘,机械硬盘的读取速度又比较慢  
那么此时我需要在 1 亿数据里面,查找一个数据,再加上机械硬盘的读取速度,可能给它一分钟的时间都找不到需要的数据  
乖乖,让你在一个空白的页面上呆一分钟,你会么?  
这个时候你的注意力早就不知道跑哪儿去了,或者这个界面打不开对么?行嘞,关闭界面,浏览下一个

用户流失不是咱们希望看到的,对吧  
所以嘞,既然二叉树是树的高度比较高,那我让它低点儿不就好了嘛  
怎么低呢  
因为二叉树每个节点只存储一个数据,那我现在让它一个节点多存储几个数据就好了嘛  
这就是 B 树  
B 树的一个节点可以存储多个数据  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70_pic_center 1]  
能够明显看到, B 树相对于二叉树来说,高度降低了不少  
那为啥不用 B 树做索引呢,采用 B+ 树  
因为 B+ 树在 B 树的基础上又做了优化  
那做了什么优化呢  
咱瞅瞅  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70_pic_center 2]  
有没有看出来一些内容  
在 B+ 树中,叶子节点之间有指针指向,在 B 树中则没有  
在 B+ 树中,非叶子节点会冗余一份在叶子节点中(比如图中的数据 50 ,在叶子节点中也能看到它)  
在 B+ 树中,非叶子节点不存储数据,只存储索引  
在 B+树中,查询必须查找到叶子节点, B 树只要匹配到就可以了, 不需要 care 元素位置,所以 B+ 树查找更慢

我这个人比较懒,图中用到的图片都是直接从网上拿下来的,拿完也忘了原文地址是啥(非常抱歉,我这个人懒不说,记性也不咋滴,太尴尬了;  
侵权的话您和我说一声,我立马撤下来

以上,非常感谢您的阅读~

[mysql_ SQL]: https://blog.csdn.net/zll_0405/article/details/107563520
[20200821132224627.jpg_pic_center]: /images/20221124/7cdc0b31d0714fe3a8c0684363bfc03b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/a90576bf37e143d795f3e20c4bb62e38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/777ea14706af469fb2f8a255a8c08df7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3psbF8wNDA1_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/d36218e9173544b79b25aad55afcd3f4.png