说到二叉树、AVL树、B树、B+树等，想必很多人都很头疼，枯燥无味、不好理解、记不住等等。现在我们从 **树-》二叉树-》二叉查找树-》AVL平衡二叉树-》B树（多路平衡树）-》B+树 **这条线来看分析下它们是怎么一回事儿。
一、树
树，是一种数据结构，它的形状如同一棵树，不过是一棵倒立状态的树。树的分叉相当于树形数据结构的节点。
树上的节点可以从树根无限延伸。这种无限延伸的树一般用于可无限扩展的树形功能菜单。无限延伸、无限宽扩展的树形结构，查询效率会比较低，为了提高树形数据结构的查询性能，就出现了二叉树。
二、二叉树
二叉树，是一个节点只能有两个子节点的树，相比于单向链表多了一个分支。
二叉树
三、二叉查找树
在二叉树的基础上，增加一个规则，左子树的所有子节点都要小于它的根节点，右子树的所有子节点都要大于它的根节点，符合这个规则的二叉树叫二叉查找树。
二叉查找树
有两种特殊情况，所有的节点都在左子树（左斜树），或者所有节点都在右子树（右斜树）；斜树的出现，导致查找时间复杂度的增加，这时就出现了平衡二叉树。
四、AVL平衡二叉树
在二叉查找树的基础上，新增一个规则，左右两个子树的高度差绝对值不能大于1，也就是平衡二叉树。为了达到这个平衡，引入了左旋和右旋的机制。
平衡二叉树
五、B树（多路平衡树、B-树）
在平衡二叉树的基础上，新增一个规则，可以有多个子路的平衡二叉树，也就是多路平衡树，它适合对外查找。多路平衡树也称B树，B-树。
B树、多路平衡树、B-树
B树特点：
-
数据存储在节点上，每个节点都会存储数据；
-
子树数量是关键字数量+1；
-
节点上的数值就是关键字。
MongoDB使用B树，所有的节点都有Data，只要找到指定索引就可以访问，单次查询会更快。
B树（多路平衡树）数据结构
六、B+树
B+树，在B树的基础上做了增强。B+树特点：
-
所有数据都存储在叶子节点上，全表扫描能力更强；
-
非叶子节点只存储索引，所以树的每一层能够存储更多的索引；
-
相邻叶子节点使用双向链表的方式进行关联，只需两个节点就可以遍历，在范围查询上效率更高；
-
叶子节点中相邻数据使用单向链表进行关联；
-
子树数量是关键字的数量；
B+树数据结构
Mysql是关系型数据库，数据之间的关联性很强，区间访问是最常见的一种情况；Mysql默认InnoDB引擎，不支持Hash索引，采用B+树作为索引和数据的存储结构。
MySql在存储数据时，以数据页为最小单位，数据在数据页中的存储是连续的，数据页中的数据是按照主键进行存储的。数据页与数据页之间是使用双向链表来关联。数据与数据之间使用单向链表来关联。
总结
采用B树、B+树作为索引结构，主要是为了减少磁盘IO次数。数据保存在磁盘上，磁盘IO效率比较低，随机磁盘IO效率更低，树的高度决定了磁盘IO次数，次数越少，性能提升越大。平衡二叉树要比B树、B+树的高度更高，而高度意味着磁盘IO的次数。为了减少磁盘IO次数，文件系统或数据库才采用B树、B+树来做索引和数据的存储结构。
参考文档：
网友评论