浅析 Mysql 索引数据结构演变，让你一看就懂 (1)，意外收获字节跳动内部资料

这种方式会存在很大的问题：

1、运气好的话 比较 1 次直接返回 2、运气差的话 比较 7 次才能返回

这个方案就是全部遍历的方式，从第一条记录开始遍历，一直遍历下去。我们这么才 7 条记录，如果几百万条，那查询性能太低了。

二叉树

为了解决这个问题，我们引入索引技术，改变一些数据存储结构。首先想到的结构，就是二叉树。

二叉树的特点：1、一个节点只能有两个子节点，也就是一个节点度不能超过 22、左子节点 小于 本节点；右子节点大于等于 本节点我们看一下上面的数据，以 id 为索引，建立的二叉树的结构是什么？

因为二叉数的特点，右边比左边大，这次我们查询 id=51，只需要比较 3 次，因为有一部分数据是不需要比较的，再索引建立的时候就已经排序好了。

这个二叉树比之前的遍历的方案，性能提高了很多。但他也有一个问题，如果 id 的值是持续递增的话，会是什么样的结构？

我们发现如果 id 是持续递增的话，我们的二叉树结构出现了残缺，如果这个时候查找 id=5，也是从一直遍历到最后，没有像之前的数据那样，排除掉一部分数据。那怎么解决？

红黑树

红黑树的出现就可以解决这个问题，红黑树的特点会自动平衡树，其他特点（小伙伴们自行度娘）。我们看一下红黑树怎么平衡？

上面两个图，左图在插入数值为 3 时，红黑树的算法发现有偏向，就会重新调整树结构；调整到右边的图

那我们可以看看，之前的数据 1～6 持续递增的树，会变成什么样

我们看到红黑树的结构，这样我们再次查找数据为 5，只需要比较 3 次，有部分数据被提前排序了。红黑树很好的平衡了树的偏向问题，但红黑树问题也比较大。

1、每次都要检查规则，再把树进行重新平衡，这个是非常消耗时间的 2、数据量大的话，红黑树的深度会比较深，树一旦深就代表着我们读取磁盘次数就会增加

B 树

小伙

【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取

伴们有没有发现，影响数据查询时间的是树的高度，高度越高，我们需要比较的次数越多，那我们是不是可以想办法把树的高度弄低点？那我们的 B 树数据结构就由此产生。

B 树的特点

假如当前有一颗 m 阶的 B 树（注意阶的意思是指每个节点的孩子节点的个数），那么其符合

（1）每个节点最多有 m 个子节点（2）除了根节点和叶子节点之外，其他的每个节点最少有 m/2（向上取整）个孩子节点（3）根节点至少有两个孩子节点，（除了第一次插入的时候，此时只有一个节点，根节点同时是叶子节点）（4）所有的叶子节点都在同一层（5）有 k 个子节点的父节点包含 k-1 个关键码（6）所有的叶节点都在同一层（7）每个节点中的子节点都是从左到右排序的

小伙伴们是不是看到这个比较晕，这么多的特点（其实还有更多性质，老顾也记不住）；其实我们不需要记住这么多的特点，只要记住几个核心点，先看图

我们的主要目标就是把树的高度弄低，上图中，我们可以看到之前的一个节点里面多了几个子节点（即几阶树）【核心点一】，这样的设计就是把之前节点只存储 1 个数值，现在可以存储多个数值。

多个子节点数值都是从左到右排序【核心点二】，有便于快速查找。而且叶节点具有相同的深度，保证了每个数值查询效率一致【核心点三】。

图中每个节点里面都包含具体信息 data【核心点四】，再查询的时候找到对应的索引后，直接取出这个节点中的信息。

B 树的核心思想就是把树高度弄低，用了树节点包含多个子节点的设计思想，上图中一个树节点包含 3 个子节点。