博主之前在复习这一块的时候，这几个树的比较经常搞混，也容易忘记，现在就总结整理一下吧（在这里说明的是，本文不讲这些树的特征，因为比较复杂且多，相信大家也记不住，重点讲一些各自的特点和实际运用场景吧）
一、什么是B树
B-树就是B树，不是叫B减树（一开始我也经常叫错），是普遍运用于文件系统和数据库的一种多叉（即，每个非叶子结点可以有多个孩子）平衡查找树。
例如：3阶B树查询数值5
第1次IO:
第2次IO:
第3次IO:
第3次内存比较:
由此可见：IO的次数最多是树的最大高度
优势：每次深度加1就会进行一次磁盘IO的查询，将当前高度的数据加到内存中，再进行数值比较。从中可以看出相比大部分的查询时间是花费在磁盘IO的速度上，所以要想提高性能就是将树的高度足够低，IO次数足够少。总的来说，为了让性能更高，就把"瘦高"的树变的"矮胖"
B树的应用：主要用于文件系统以及部分数据库索引（MongoDB） 而Mysql是用B+树的。
二、什么是B+树
MySQL索引为什么要使用B+树，而不是B树呢？
这是一个问题？首先要搞懂MySQL的数据读取是怎么回事？
我们在MySQL中的数据一般是放在磁盘中的，读取数据的时候肯定会有访问磁盘的操作，磁盘中有两个机械运动的部分，分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟，而磁盘移动则是在盘片旋转到指定位置以后，移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程，而定位是磁盘的存取中花费时间比较大的一块，毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候，显然定位是一个非常花费时间的过程，但是我们可以通过B树进行优化，提高磁盘读取时定位的效率。
B+树是应文件系统所需而产生的一种B树的变形树（文件的目录一级一级索引，只有最底层的叶子节点（文件）保存数据）非叶子节点只保存索引，不保存实际的数据，数据都保存在叶子节点中，这不就是文件系统文件的查找吗?
我们就举个文件查找的例子：有3个文件夹a、b、c， a包含b，b包含c，一个文件yang.c，a、b、c就是索引（存储在非叶子节点）， a、b、c只是要找到的yang.c的key，而实际的数据yang.c存储在叶子节点上。
所有的非叶子节点都可以看成索引部分！
在上面这棵树中，根节点元素8是子节点2，5，8的最大元素，也是叶子节点6，8的最大元素，至于叶子节点，由于父节点的元素都出现在子节点，因此所有叶子节点包含了全量元素信息，并且每个叶子节点都带有指向下一个恶节点的指针，形成了一个有序链表
B+树的好处主要体现在查询性能上：
- 单行查询：由于B+树中间节点没有数据，所以同样大小的磁盘页可以容纳更多的节点元素，在数据量相同的情况下，B+树结构比B树更加"矮胖"，查询IO次数更少。而且B+树每次查询都必须查到叶子节点，比B树更稳定。
- 范围查询
自顶向下，查找到范围的下限（3）
通过链表指针，遍历到元素6, 8
通过链表指针，遍历到元素9, 11，遍历结束
综合起来，B+比B树优势有三个：1、IO次数更少 2、查询性能稳定 3、范围查询简便
应用：B和B+树主要用在文件系统以及数据库做索引，比如MySQL
三、什么是红黑树
一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是red或black。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树(由于是若平衡，可以推出，相同的节点情况下，AVL树的高度低于红黑树)，相对于要求严格的AVL树来说，它的旋转次数变少，所以对于搜索、插入、删除操作多的情况下，我们就用红黑树 应用：
- 著名的Linux进程调度Completely Fair Scheduler，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；
- 广泛用于C++的STL中，Map和Set都是用红黑树实现的；
- IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查；
- Nginx中用红黑树管理timer，因为红黑树是有序的，可以很快的得到距离当前最小的定时器；
- Java中TreeMap、HashMap的实现；
重点讲一下：HashMap在1.7上的数据结构主要是用的：数组+链表，HashMap在1.8里面主要是：数组+链表+红黑树，当链表长度大于8时则后面数据结构为转化为红黑树
为什么要用红黑树，而不用平衡二叉树？
红黑树的平衡度相比平衡二叉树要低，对于删除、插入数据之后重新构造树的开销要比平衡二叉树要低，查询效率比普通二叉树高。所以选择性能相对折中的红黑树。（扩展：平衡二叉树这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多。更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么平衡二叉树还是较优于红黑树。）
既然红黑树那么好，为啥HashMap不直接采用红黑树？
这是因为红黑树需要进行左旋、右旋操作，而单链表不需要。并且单拉链表的方式实现起来比较的简单。
四、什么是平衡二叉树
AVL树（平衡二叉树）是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，它是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。
局限性：由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。
应用：Windows NT内核中广泛存在
最后讲一下为什么说B+树比B树更适合数据库索引？
- B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。
- B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
- 由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。
PS：我在知乎上看到有人是这样说的,我感觉说的也挺有道理的： 他们认为数据库索引采用B+树的主要原因是：B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。