MySQL为什么不选择平衡二叉树？ 既然平衡二叉树解决了普通二叉树的问题，MySQL为什么不选择平衡二叉树作为索引？

想想索引中需要保存什么。 保存索引时，需要保存哪些信息？ 需要保存三个信息。

索引值：对应于表中索引列的值。

直接保存数据的磁盘地址(从磁盘地址中找到当前数据)或整个数据。

浏览子节点：必须从根节点向下，因此必须知道左右子节点的地址。 从这三点来看，有以下大致结构图。

上图中的数字表示索引值，以0x开始表示盘地址，在根节点中存储有左右节点的参照。

我知道AVL树用来存储索引的问题是什么。 “页面”(Page )是Innodb存储引擎用于管理数据的最小磁盘单位，页面的默认大小为16KB。 页面是指上图中的节点。 每次询问节点时都需要进行I/o操作。 I/o操作是一项非常耗时的操作，许多业务系统瓶颈都在I/o操作上。 因此，如果需要减少I/o次数的方法作为提高查询效率的方法之一，就会出现问题。 AVL树中的一个节点只包含对一个关键字(索引值) 1个磁盘地址左右的节点的引用。 这比不上16KB

要在上图中找到6这个数据，需要进行3次IO。 获取一个节点就是一个IO操作。 如果这棵树高，就会进行大量的IO操作。 因此，AVL树最大的问题是空间利用不足，浪费了大量的空间，在数据量大的时候会变成瘦高的树。 怎样才能改善呢？ 答案很明显。 那就是在每个磁盘块中保存稍微多一点的东西。 也就是说，每个磁盘保存几个关键字。 因为关键字越多，路径数就越多。 道路数量越多，树也越矮越胖，I/o次数也相应减少。

平衡树(balanced tree )复用平衡树又称b树，与AVL树一样，b树在分支节点和叶节点中存储键值、盘地址、左右节点的引用。 让我们来看看下图中的多重平衡树示例。

与AVL树相比，b树的特点是可以在b树的一个磁盘上存储多个关键字(值)，具有以下特点：

分支数(道路数)总是比关键字数多1。 可以画出以下概略图。 (下图中只画了3路，即两个关键字，但实际上取决于一页中可以存储的关键字数量。 ）

上图表明，即使是同样高度的树，b树也能保存比平衡二叉树大得多的数据。

b树以如何查找数据的上图为例。 假设要查找key=32这个数字。 首先获取根节点，发现18小于key。 因此，往右走，获取右边的数据，54和76。 此时，遵循以下原则。

key54，命中最左分支；

key=54，直接命中，返回数据；

54key76，走中间的分支；

key=76，直接命中，返回数据；

key76，命中右分支； 这里key=32，所以前进到第一条，命中左分支。 此时，发现又去获取左分支，获取32和50，按key=32命中，返回数据。

从以上内容可以看出，b树相对于AVL树的效率在数据量大的情况下提高了很多。 那为什么MySQL不选择b树作为索引呢？ 那么，接下来先看改良版的b树，然后再得出结论吧！

b树b树从b树中被改良，属于改良版的多重平衡搜索树。 首先，让我们看看b树是怎么生长的。

与b树相比，可以看到明显的差异：叶子节点有箭头，从左到右有序。

与传统的b树相比，InnoDB中使用的b树改进后的b树具有以下特征

InnoDB中b树的特征其关键字的数量与道路数相等。

在b树的根节点和分支节点中不存储数据，只有叶节点存储数据。 检索到的关键字不会直接返回，而是到达最后一层的叶节点。

它添加了指向与b树中每个叶节点相邻的叶节点的指针，最后一个数据指向下一个叶节点上的第一个数据，链表结构有序。

这基于基于根据左闭右开的区间检索数据的b树的特征，能够如下描绘存储数据的概要图。

最后给读者们一个小福利，有需要这些资料的朋友们可以点击我，即可免费领取资料！

ActiveMQ消息中间件面试专题什么是ActiveMQ？ 如果ActiveMQ服务器停机怎么办？ 丢了新闻怎么办？ 持久化的消息非常慢吗？ 新闻不均匀消费怎么办？ 死队怎么办？ 是ActiveMQ的消息重发时间间隔和重发次数吗？ActiveMQ消息中间件面试专题解析拓展：

redis面试的主题和答案支持一致性哈希的客户端是什么？ Redis与其他密钥值存储有何不同？ Redis的内存使用情况如何？ 有什么方法可以降低Redis的内存利用率？ 使用什么命令显示Redis的使用情况和状态信息？ 当Redis内存耗尽时会发生什么？ Redis是单线程的，如何提高多核CPU的利用率？

Spring面试答案解析拓展

高并发多线程面试解析与拓展

JVM面试专题解析与拓展！

JVM面试专题解析与拓展！