引语
作为一直后端程序猿，经常会看到好几个关于树的概念，平衡二叉树，二叉搜索树，avl树，btree，b+tree等等。没有弄清楚的时候，放到一起很容易弄混。今天咱们就来捣鼓捣鼓这几个名词，理解一下它们都是啥。本文会从二叉树由浅入深介绍到b+tree，对于不同的树的插入删除先不谈，主要用于帮助不清楚概念的童鞋理解这些名词代表的什么样的数据结构，暂不涉及红黑树（这玩意要写起来篇幅有点长，下次可以单独出一篇）。
树：
首先咱们来看看最基本的定义，之后讲的所有种类的树都是属于树这个大类里面：
树（tree）是包含n（n>=0）个结点的有穷集，其中：
（1）每个元素称为结点（node）
（2）有一个特定的结点被称为根结点或树根（root）
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
然后一些树的基本概念（默认大家都学过了，不过照顾一下真没看过的列了几个简单的概念在下面，不会的请百度了解下）：
根节点：最顶层的节点，没有任何父节点的节点，通俗来说是树最顶上那一个节点
度：一个节点拥有子树的数量，通俗来说就是一个树的节点有多少个分支，度就是多少
叶子节点：度为0的节点就是叶子节点，通俗来说就是一棵树最下面的部分，没有分支的节点都是叶子节点
树的高度或深度：树中结点的最大层次，通俗来说就是一棵树有几层，按节点来算
树的度：一棵树中，最大的结点的度称为树的度，通俗来说就是一棵树中分支最多的那个节点度是多少，树的度就是多少，图中树的度就是3,因为最大的度是C节点，有三个分支
子树：每一个节点下的部分都是一颗子树，它也符合树的定义，比如图中T1，T2 
二叉树：
这个基本上没啥大问题，树的度不超过2的就是二叉树,图中B，C都是度最大的节点为2
二叉搜索树：
有的书上也叫查找树，binary search tree，搜索树，查找树是同一个东西哦。属于二叉树，特征在于在二叉搜索树中，左子树中所有节点的值小于根的值，右子树中所有节点的值大于或等于根的值，
并且对于任意节点都符合这个规则。
二叉搜索树的优点如同它的名字一般，方便搜索，搜索一个元素的时间复杂度是o(logn)，最坏的情况是全部遍历才找到该元素时间复杂度是o(n)。
平衡二叉搜索树：
avl树也是一棵二叉搜索树，只是它的名字过于特殊了，avl树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，取简称叫avl树。
因为它这个名字，我经常忘记它是平衡二叉搜索树，我是用联想的方法记住的，读者们可以试下看有效果没。avl 我联想的是一颗（A）用来搜索的平衡（V是左右对称的）的二叉树（L是两个分支，一横一竖）
。把这句话给记住了，在看avl三个字母的时候就能联想知道它代表的是啥了。
然后看看它的特点是：
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，avl树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
一棵树如果是这样： 
它是一颗二叉搜索树，符合定义，但是元素如果在13->9这个子树上，查询效率和链表差不多，这就因为这个数它不平衡，左右子树额高度差太多
，查询起来的效率就比较低。所以avl树诞生了，每个节点的左右子树高度差都不超过1。如图和上面的二叉搜索树的图都是avl树，都是平衡的。
btree：
首先这里说清楚一点，很重要，btree和b-tree是同一个东西。之前有很多人按照读音来都以为是B树，B减树（可能是受了B加树的影响，实际上没有B减树，那只是一个短横是一种写法，实际上就是btree）。好了，
咱们知道了avl树是二叉平衡搜索树，那么btree就好讲了。
btree是多路平衡搜索树，和avl相比它不是二叉的，而是多叉的，有很多个分支，M阶的btree就是树的度是M，最多有M个分支。
1.根节点至少两个子节点
2.每个非叶子节点且不是根节点的至少有m/2个
3.每个节点最多不超过m个孩子
4.所有的叶子节点都在同一高度
5.每个非叶子节点由n个key和n+1个指针构成，并且[ceil(m/2)-1]<=n<=m/2 （这里ceil是向上取整的意思）
这些定义不用死记，咱们可以结合实际来理解下，这是我从网上找的一张4阶的bree，因为自己真滴懒，画起来好麻烦 
好，咱们看图
对照上面的规则，1-4应该都没啥问题，第5条M是4，n算出来1<=n<=2，指针是2-3个，1-2个key，key就是图中有数值的方框，指针就是白色的方框。
优势：
因为btree主要也是用来搜索数据，它和二叉搜索树相比，是多叉的所以相同的数据量的情况下，它的树高会更低，如果是二叉树，找到一个数据不再某一个
子树树越高，查询的次数就越多，多路降低了树高，提升了查找效率。
b+tree：
了解了btree之后啊，理解b+tree又简单了一些，根据名字咱们就知道它们长得很像，除了b+tree多一个+。b+tree其实是btree的优化版本。
有没有玩过大家来找茬？看看和btree有几处不同之处.
聪明的你应该找到了答案，答案是5处。是的，没错，全是指针的不同。
所以b+tree的这个加咱们可以理解为叶子节点的指针加上了,而且b+tree详细的数据只放在叶子节点上，非叶子节点只是保存的索引（想一想mysql的聚簇索引和非聚簇索引，是不是很熟悉的感觉？可以看看我的另一篇博客:mysql的聚簇索引和非聚簇索引）。
为啥要加个叶子节点间的指针呢？如果用过mysql咱们知道，innodb里面支持两种索引，一种是hash，
一种是btree，这里的btree实际上就是用的b+tree。咱们知道mysql索引搜索的时候会有范围搜索，如果是找某个范围的数据，btree是不是得从根节点查询几次，每次遍历到叶子节点，才能知道数据有多少？
但是b+tree就不一样，所有叶子节点都有指针相连，是不是直接按照指针依次找过来就可以了？是的，这就是b+tree的优势。
从网上摘了一下区别，可以自行理解一下：
区别：
B树
1.搜索键无法重复存储。
2.数据可以存储在叶节点以及内部节点中
3.搜索某些数据是一个较慢的过程，因为可以在内部节点和叶节点上找到数据。
4.删除内部节点非常复杂且耗时。
5.叶节点不能链接在一起。 叶节点链接在一起以使搜索操作更有效
B+树
1.可以存在冗余搜索键。
2.数据只能存储在叶节点上。
3.搜索速度相对较快，因为只能在叶节点上找到数据。
4.删除永远不会是一个复杂的过程，因为元素将始终从叶节点中删除。
后记：
1.看完文章知道了树，二叉树，二叉搜索树，avl树，btree，b+tree的概念和特性，应该对这些树有了一个大致的了解吧
2.但是其实这里面还有很多可以继续深入的地方，比如btree，b+tree增删改查是怎么操作的？
还有红黑树的概念和操作，这里面其实也有很多内容可以讲。
