当前位置:网站首页>Mysql——》索引存储模型推演
Mysql——》索引存储模型推演
2022-07-01 21:45:00 【小仙。】
推荐链接:
总结——》【Java】
总结——》【Mysql】
总结——》【Spring】
总结——》【SpringBoot】
Mysql——》索引存储模型推演
数据结构
数据结构可视化:Data Structure Visualizations
一、二分查找
抖音很火的猜数字游戏, 猜你现在是100以内的几, 最后通过不断缩小范围, 锁定数字。
这个就是二分查找的一种思想,也叫折半查找,每一次,我们都把候选数据缩小了一半。
如果数据已经排过序的话,这种方式效率比较高。
二分查找 = 折半查找 = 每一次查询数据范围缩小一半
1)考虑用有序数组作为索引的数据结构
优点:等值查询和比较查询效率非常高
缺点:更新数据的时候会出现一个问题,可能要挪动大量的数据(改变 index)
总结:只适合存储静态的数据
2)考虑用链表作为索引的数据结构
优点:支持频繁插入/修改数据
缺点:单链表,它的查找效率还是不够高
Q:有没有可以使用二分查找的链表呢?
A:为了解决这个问题,BST(Binary Search Tree)也就是我们所说的二叉查找树诞生了。
二、二叉查找树(BST)
参考链接:Binary Search Trees
BST = Binary Search Trees = 二叉查找树
1、特点
左子树所有的节点都小于父节点,右子树所有的节点都大于父节点。
投影到平面以后,就是一个有序的线性表。
示例:按顺序插入14、7、5、12、17、25
2、优点
1)快速查找
2)快速插入
3、缺点
查找耗时是和这棵树的深度相关的,在最坏的情况下时间复杂度会退化成O(n)。
示例:按顺序插入5、7、12、14、17、 25
结果:变成链表(也叫做”斜树“),这种情况达不到加快查找的目的,和顺序查找效率一样
原因:左右子树的深度差太大,这棵树的左子树根本没有节点,也就是它不够平衡
Q:有没有左右子树深度相差不是那么大,更加平衡的树呢?
A:这个就是平衡二叉树,叫做 Balanced binary search trees,或者 AVL 树
三、平衡二叉树(AVL Trees)
参考链接:AVL Trees (Balanced binary search trees)
AVL :是发明这个数据结构的人的名字缩写
AVL 树 = Balanced binary search trees = 平衡二叉树
定义:左右子树深度差绝对值不能超过 1
1、特点
为了保持平衡,AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。
当左边深度与右边深度超过1时,会进行左旋/右旋
示例:按顺序插入5、7、12、14、17、15
1)左旋
示例:按顺序插入5,7,14
过程:当我们插入了 5、7 之后,如果按照二叉查找树的定义,14 肯定是要在 7 的右边的,这个
时候根节点 1 的右节点深度会变成 2,但是左节点的深度是 0,因为它没有子节点,所以就会违反平衡
二叉树的定义。 那应该怎么办呢?因为它是右节点下面接一个右节点,右-右型,所以这个时候我们要把 7提上去, 这个操作叫做左旋。
2)右旋
示例:按顺序插入14,7,5
过程:左左型,就会发生右旋操作,把 7提上去
2、每个节点存储的内容
在平衡二叉树中,一个节点,它的大小是一个固定的单位,作为索引应该存储什么内容?
1)索引的键值
比如我们在 id 上面创建了一个索引,我在用 where id =1 的条件查询的时候 ,就会找到索引里面的 id 的这个键值。
2)数据的磁盘地址
因为索引的作用就是去查找数据的存放的地址。
3)左子节点和右子节点的引用
因为是二叉树,它必须还要有左子节点和右子节点的引用,这样我们才能找到下一个节点。
3、平衡二叉树作为索引怎么查询数据
首先,对于 InnoDB 来说,索引的数据,是放在硬盘上的。
当我们用树的结构来存储索引的时候,因为拿到一块数据就要在 Server 层比较是不是需要的数据,如
果不是的话就要再读一次磁盘。访问一个节点就要跟磁盘之间发生一次 I/O。InnoDB 操作磁盘的最小的单位是一页(或者叫一个磁盘块),大小是 16K(16384 字节)。一个树的节点就是 16K 的大小。
如果我们一个节点只存一个键值+数据+引用,例如整形的字段,可能只用了十几个或者几十个字
节,它远远达不到 16384 字节的容量,所以访问一个树节点,进行一次 IO 的时候,浪费了大量的空
间。
所以如果每个节点存储的数据太少,从索引中找到我们需要的数据,就要访问更多的节点,意味着
跟磁盘交互次数就会过多,消耗的时间也越多。
比如上面这张图,我们一张表里面有 6 条数据,当我们查询 id=66 的时候,要查询两个子节点,就
需要跟磁盘交互 3 次,如果我们有几百万的数据呢?这个时间更加难以估计。
Q:如何解决交互次数多的问题呢?
A:让每个节点存储更多的数据,极大地降低树的深度。我们的树就从原来的高瘦高瘦的样子,变成了矮胖矮胖的样子。 这个时候,我们的树就不再是二叉了,而是多叉,或者叫做多路。
四、多路平衡查找树(B Trees)
参考链接:B Trees
B Tree = Balanced Tree = 多路平衡查找树
1、特点
1)分叉数(路数)永远比关键字数多 1
2)在枝节点和叶子节点存储键值、数据地址、节点引用
示例:比如我们画的这棵树,每个节点存储2个关键字,那么就会有3个指针指向3个子节点。
1)分裂
比如 Max Degree(路数/度数)是 3 的时候,我们插入数据 1、2、3,在插入 3 的时候,本来应该在第
一个磁盘块,但是如果一个节点有3个关键字的时候,意味着有 4 个指针, 子节点会变成 4 路,所以这
个时候必须进行分裂(其实就是 B+Tree)。把中间的数据 2提上去,把 1 和 3 变成 2 的子节点。
2)合并
如果删除节点,会有相反的合并的操作。
注意这里是分裂和合并,跟 AVL 树的左旋和右旋是不一样的。
Q:为什么不要在频繁更新的列上建索引?
A:在更新索引的时候会有大量的索引的结构的调整。
节点的分裂和合并,其实就是 InnoDB 页(page)的分裂和合并。
五、加强版多路平衡查找树(B+Tree)
Q:B Tree 的效率已经很高了,为什么 MySQL 还要对 B Tree 进行改良,最终使用了B+Tree 呢?
A:B+Tree解决的问题比 B Tree 更全面
1、存储结构
搜索到关键字不会直接返回,会到最后一层的叶子节点。比如我们搜索 id=28,虽然在第一层直接 命中了,但是数据地址在叶子节点上面,所以我还要继续往下搜索,一直到叶子节点。
2、特点
1、关键字的数量是跟路数相等的;
2、B+Tree 的根节点和枝节点中都不会存储数据,只有叶子节点才存储数据。
3、B+Tree 的每个叶子节点增加了一个指向相邻叶子节点的指针,它的最后一个数据会指向下一个叶子节点的第一个数据,形成了一个有序链表的结构。
3、优点
1)它是 B Tree 的变种,B Tree 能解决的问题,它都能解决。
1、每 个节点存储更多关键字;2、路数更多
2)扫库、扫表能力更强
如果我们要对表进行全表扫描,只需要遍历叶子节点就可以了,不需要遍历整棵 B+Tree 拿到所有的数据
3)B+Tree 的磁盘读写能力相对于 B Tree 来说更强
根节点和枝节点不保存数据区,所以一个节点 可以保存更多的关键字,一次磁盘加载的关键字更多
4)排序能力更强
因为叶子节点上有下一个数据区的指针,数据形成了链表
5)效率更加稳定
B+Tree 永远是在叶子节点拿到数据,所以 IO 次数是稳定的
边栏推荐
- PCB plug hole technology~
- Why must digital transformation strategies include continuous testing?
- 辅音和声母的区别?(声母与辅音的区别)
- Pytest collection (2) - pytest operation mode
- Design and practice of new generation cloud native database
- 上半年暂停考试要补考?包含监理工程师、建筑师等十项考试
- [NOIP2013]积木大赛 [NOIP2018]道路铺设 贪心/差分
- Smart micro mm32 multi-channel adc-dma configuration
- 选择在同花顺上炒股开户可以吗?安全吗?
- Unity uses SQLite
猜你喜欢
【juc学习之路第9天】屏障衍生工具
Manually implement function isinstanceof (child, parent)
pytest合集(2)— pytest运行方式
并发编程系列之FutureTask源码学习笔记
One of the basic learning of function
[live broadcast review] the first 8 live broadcasts of battle code Pioneer have come to a perfect end. Please look forward to the next one!
locust 系列入门
完全注解的ssm框架搭建
比较版本号[双指针截取自己想要的字串]
从零开始学 MySQL —数据库和数据表操作
随机推荐
Can you get a raise? Analysis on gold content of PMP certificate
Application of real estate management based on 3D GIS
选择在同花顺上炒股开户可以吗?安全吗?
MySQL之MHA高可用配置及故障切换
JS how to get a list of elements in a collection object
I received a letter from CTO inviting me to interview machine learning engineer
名单揭晓 | 2021年度中国杰出知识产权服务团队
【MySQL】数据库优化方法
Introduction à l'ingénierie logicielle (sixième édition) notes d'examen de Zhang haifan
Using closures to switch toggle by clicking a button
Make a three digit number of all daffodils "recommended collection"
Unity uses SQLite
并发编程系列之FutureTask源码学习笔记
The leader of the cloud native theme group of beacon Committee has a long way to go!
【单体】流辰信息I-BPSv3服务器推荐配置
js数组拼接的四种方法[通俗易懂]
Sonic云真机学习总结6 - 1.4.1服务端、agent端部署
MySQL empties table data
信标委云原生专题组组长,任重道远!
#yyds干货盘点# 解决名企真题:扭蛋机