Mysql——》索引存储模型推演

推荐链接：
    总结——》【Java】
    总结——》【Mysql】
    总结——》【Spring】
    总结——》【SpringBoot】

数据结构

数据结构可视化：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 次数是稳定的