B树
m阶B树的性质
定义任意非叶子结点最多只有m个儿子；且m>2；
根结点的儿子数为[2, m]；
除根结点以外的非叶子结点的儿子数为[m/2, m]；
每个结点存放至少m/2-1（取上整）和至多m-1个关键字；（至少2个关键字）
非叶子结点的关键字个数=指向儿子的指针个数-1；
非叶子结点的关键字：K[1], K[2], …, K[m-1]；且K[i] < K[i+1]；
非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[m]指向关键字大于K[m-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
所有叶子结点位于同一层；
B树的应用
B树多用于文件系统
B+树
一棵m阶的B+树和m阶的B树的异同点在于：
（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
（2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
（3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
B树和B+树的对比
1、B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
2、B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
3、B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
4、B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。
AVL树
AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
AVL树的定义:
一棵AVL树满足以下的条件:
1、它的左子树和右子树都是AVL树
2、左子树和右子树的高度差不能超过1
红黑树
红黑树在二叉搜索树的基础上还有以下性质：
1、每个节点要么是黑色，要么是红色
2、根节点永远是黑色的
3、所有的叶节点都是空节点（即 null），并且是黑色的
4、每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
5、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点
性质4保证了从根节点到每个叶子结点的路径长度不会超过任何其他路径的两倍。
红黑树的插入，删除，可以看这篇文章
通过分析 JDK 源代码研究 TreeMap 红黑树算法实现
红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构 能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
问题
1、为什么在文件系统中喜欢使用B树作为底层的数据结构，而不是红黑树或者有序数组？
有个主要原因是文件系统的索引数据是存放在磁盘上的，如果使用有序数组，那么如果索引数据太大，内存可能无法全部加载进来，使用B树作为底层结构，可以逐个逐个节点加载进来。在大规模数据存储时，如果使用红黑树，往往会因为红黑树的高度太高而导致磁盘IO读写过于频繁。因此文件系统一般使用B树作为底层结构。
2、在数据库索引中为什么使用B+树而不是B树？
数据库索引采用B+树的主要原因是 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）
总结
B树是为了提高磁盘或外部存储设备查找效率而产生的一种多路平衡查找树。
B+树为B树的变形结构，用于大多数数据库或文件系统的存储而设计。
