今天，我给大家介绍一种面试中经常被问到数据结构树。大家可能也经常会听到二叉树、二叉查找树、AVL平衡二叉树、B树、 等等，那今天我给大家一次性讲清楚。

另外，我花了1个多星期，准备了一份10W字的面试题解析配套文档，想获取的小伙伴可以扫描文章底部二维码领取！

1、树形结构的演变历史

树是一种数据结构，它的结构形状如同一棵树木，但是是倒立的状态。

树的分叉就相当于树形数据结构中的节点，树上的节点可以从树根无限延伸。如图所示：

但是，这种无限延伸的树在实际开发中一般用于可无限扩展的树形功能菜单。这样的无限级、无限宽扩展的结构查询性能会比较低。因此，为了提高树形结构的查询性能，于是就出现了二叉树，来看这么一张图：

所谓二叉树是指每个节点最多支持两个分叉，相比于单向链表来说它多了一个分支。而二叉查找树，是在二叉树的基础上增加一个规则。它的规则是左子树的所有子节点都要小于它的根节点，而右侧子节点要大于它的根节点。

我们再来看这个图，二叉查找树有可能会出现斜树问题，从而导致时间复杂度会增加。因此，又引入了一种叫做平衡二叉树的机制。它具有二叉查找树的所有特点，同时还增加了一个规则。它的规则是左右两个子树的高度差的绝对值不能超过1。 为了达到这样一个平衡，所以它会引入一个左旋和右旋的机制，来实现树的平衡。

我们再来看这张图，这是B树。它是一种多路平衡查找树。它既满足平衡二叉树的规则，又可以有多个子路。子路的数量呢取决于它的关键字的数量。如图所示，根节点中有两个关键字3和5，那么它能够拥有的子路数量等于关键字的数量加1。因此，从这个特征来看，在存储同样数量的情况下，平衡二叉树的高度一定要大于B树的高度。

2、B树和B+树的区别

B+树呢，其实是在B树的基础上做了增强，和B树有两个最大的区别：

第1个：B树的数据存储在每个节点上，而B+树中的数据只存储在叶子节点上，并且通过链表的方式将所有叶子节点全部串联起来

第2个：B+树的子树数量等于它的关键字的数量，而B树是关键字数量加1。我们来看这个图：

这个是B树的存储结构。从B树的结构上可以看到，每个节点都会存储数据。我们再来看这个图：

这是一个B+树的结构。B+树的数据是存储在叶子节点上的，并且呢，叶子节点的数据是用双向链表来关联。

3、选择B树和B+树的理由

那为什么要用B树或者B+树来做索引结构呢？

因为AVL树的高度要比B树或者B+树的高度更高，而高度就意味着磁盘IO的数量，所以，为了减少磁盘IO的次数，文件系统或者数据库才会使用B树，或者B+树来做索引结构。

在比较经典的程序应用中，MongoDB使用的是B树，MongoDB中所有的节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询会更快。

而MySQL作为一个关系型数据库，数据的关联性是非常强的，区间访问是常见的一种情况，B+树由于数据全部存储在叶子节点，并且通过指针串在一起，这样就很容易的进行区间遍历甚至全部遍历。

以上就是我对B树和B+树的理解。程序的本质就是数据结构加算法。数据结构在实际开发中非常常见，比如数组、链表、双向链表、红黑树、跳跃表、B树、B+树、队列等。所以，数据结构是编程最重要的基本功之一，很多大厂面试也经常会问到。同时，基本功也是决定大家在技术路上能够达到的高度的重要因素。