MySQL相关：索引数据模型推演及 B+Tree 的详细介绍( 二 ) _索引数据

那它的平衡是怎么做到的呢？怎么保证左右子树的深度差不能超过 1 呢？

www.cs.usfca.edu/~galles/vis… 插入 1、2、3 。我们注意看：当我们插入了 1、2 之后，如果按照二叉查找树的定义，3 肯定是要在 2 的右边的，这个时候根节点 1 的右节点深度会变成 2，但是左节点的深度是 0，因为它没有子节点，所以就会违反平衡二叉树的定义。
那应该怎么办呢？因为它是右节点下面接一个右节点，右-右型，所以这个时候我们要把 2 提上去，这个操作叫做左旋。同样的，如果我们插入 7、6、5，这个时候会变成左左型，就会发生右旋操作，把 6 提上去。所以为了保持平衡，AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。

平衡的问题我们解决了，那么平衡二叉树作为索引怎么查询数据？
在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？

它应该存储三块的内容：

索引的键值。比如我们在 id 上面创建了一个索引，我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。
数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。
因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如大于 26 的时候，走右边，到下一个树的节点，继续判断。

如果是这样存储数据的话，我们来看一下会有什么问题。在分析用 AVL 树存储索引数据之前，我们先来学习一下 InnoDB 的逻辑存储结构。innodb 的逻辑存储结构
AVL 树用于存储索引数据首先，索引的数据，是放在硬盘上的。查看数据和索引的大小：

SELECT	CONCAT(ROUND(SUM(DATA_LENGTH / 1024 / 1024) , 2) ,'MB'	) AS data_len ,	CONCAT(ROUND(SUM(INDEX_LENGTH / 1024 / 1024) , 2) ,'MB'	) AS index_lenFROM	information_schema. TABLESWHERE	table_schema = 'gupao'AND table_name = 'user_innodb';复制代码

当我们用树的结构来存储索引的时候，访问一个节点就要跟磁盘之间发生一次 IO 。
InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384 字节) 。
那么，一个树的节点就是 16K 的大小。
如果我们一个节点只存一个键值+数据+引用，例如整形的字段，可能只用了十几个或者几十个字节，它远远达不到 16K 的容量，所以访问一个树节点，进行一次 IO 的时候，浪费了大量的空间。
所以如果每个节点存储的数据太少，从索引中找到我们需要的数据，就要访问更多的节点，意味着跟磁盘交互次数就会过多。
如果是机械硬盘时代，每次从磁盘读取数据需要 10ms 左右的寻址时间，交互次数越多，消耗的时间就越多。

文章插图

比如上面这张图，我们一张表里面有 6 条数据，当我们查询 id=37 的时候，要查询两个子节点，就需要跟磁盘交互 3 次，如果我们有几百万的数据呢？这个时间更加难以估计。

所以我们的解决方案是什么呢？

让每个节点存储更多的数据。节点上的关键字的数量越多，我们的指针数也越多，也就是意味着可以有更多的分叉（我们把它叫做“路数”）。

因为分叉数越多，树的深度就会减少（根节点是 0）。
这样，我们的树是不是从原来的高瘦高瘦的样子，变成了矮胖矮胖的样子？
这个时候，我们的树就不再是二叉了，而是多叉，或者叫做多路。
多路平衡查找树（B Tree）（分裂、合并）Balanced Tree 这个就是我们的多路平衡查找树，叫做 B Tree（B 代表平衡）。跟 AVL 树一样，B 树在枝节点和叶子节点存储键值、数据地址、节点引用。它有一个特点：分叉数（路数）永远比关键字数多 1 。比如我们画的这棵树，每个节点存储两个关键字，那么就会有三个指针指向三个子节点。

文章插图

B Tree 的查找规则是什么样的呢？比如我们要在这张表里面查找 15 。因为 15 小于 17，走左边。因为 15 大于 12，走右边。在磁盘块 7 里面就找到了 15，只用了 3 次 IO 。这个是不是比 AVL 树效率更高呢？那 B Tree 又是怎么实现一个节点存储多个关键字，还保持平衡的呢？跟 AVL 树有什么区别？