mysql中用到的一些树

在mysql的各种引擎中，最常用到树就是 B树，B+树，最早由平衡二叉树演变而来

所以我们要了解B+树，首先需要了解二叉树，平衡二叉树，平衡多路查找树（B-树）

1，二叉树，左边的树的键值小于跟键值，右侧子树的键值大于跟键值
当深度为一的时候，查找次数为1，深度为二的时候，随着3号球的加入，查找次数变为两次，7号球的加入，查找次数为两次。

当深度为三的时候，3号球加入，查找次数为3，5号球，8号球同理，最终平均查找次数为（1+2+2+3+3+3）/6 为 2.3次

2，平衡二叉树

平衡二叉树，在符合二叉树的条件下，还满足两个子树的高度差，最大为1
当平衡树中插入，或者删除节点导致由平衡树变为非平衡树的时候，可以通过旋转的方式，重新平衡

3，平衡多路查找树：

B-树是为磁盘等外部内存设计的平衡查找树。

B-Tree 能让系统搞笑的找到数据在的磁盘，然后进行数据读取。

为了描述它，我们需要定一个二元组[key,data] ，key记录键值，data记录除键值外的主数据

每个节点占用一个磁盘空间，一个节点上两个升序关键字，三个只想子节点的指针。以根节点为例

p1 指向 大于17的磁盘空间，p2指向 17到35，p3指向 大于35的位置

例如我们查找36

根节点找到磁盘块1，读入内存【磁盘I/O第一次操作】

比较36，大于35，找到指针p3

根据p3找打磁盘块3，读入内存【磁盘I/O第二次操作】

比价36，小于65，找到指针p1

根据p1找到磁盘块9，读入内存【磁盘I/O第三次操作】

在磁盘中找到 36

可见B-Tree 减少了i/o操作，可以提高查询效率

4，B+Tree

相比B-树，缺少了data，就可以更多的存储key，从而减小深度