原 mysql的索引为什么是B+树？

版权声明：本文为博主原创文章，请尊重他人的劳动成果，转载请附上原文出处链接和本声明。
本文链接：https://www.91mszl.com/Dream/article/details/1199

一：为什么不是hash？

答：hash一次就能找到对应的数据，但是hash无法进行范围查询和排序操作。

二：二叉树。

二叉树的特点：

1.  一个节点只能有两个子节点，也就是一个节点上不能超过2个。

2. 左子节点小于本节点，右子节点大于本节点。比我大的向右，比我小的向左。

为什么mysql不实用二叉树呢？

答：二叉树无法解决树向一边倒的问题。如当数据为连续的时候，树会不平衡，树会向左边或右边一直连续下去。如下图所示，要查询007这条数据，需要查找7次才能找到，这几乎是要命的。

二叉树动态演示地址：

三：平衡二叉树（AVL）。

平衡二叉树的结构

平衡二叉树不会存在左或右倾斜的情况，但是如上图所示如果我要查找0015这条数据，需要查询4次，如果数据越多，那么树就越高，树越高查询的次数就越多。

平衡二叉树动态演示地址：

四：B树。

B树的结构

B树的树高是3。

B树动态演示地址：

五：B+树。

B+树结构

1) B+上面是B树，下面是链表。方便范围查找，排序。

2) B+树非叶子节点只存储键值信息。所有叶子节点之间都有一个链指针。数据记录都存放在叶子节点中。

B+树动态演示地址：