二叉查找树
1、二叉排序树、二叉查找树、二叉搜索树 都是同一个树的不同名称
二叉平衡树
2、二叉平衡树对二叉排序树进行约束，即左右子树高度差不能大于1，否则就要调整。由于二叉平衡树的严格限制，使得二叉平衡树的查找更加方便，但是也同样由于二叉树的严格限制，使得插入和删除操作较多时，平衡二叉树的调整特别频繁，影响性能，于是出现了红黑树。
红黑树
3、红黑树的约束条件相较于二叉平衡树简单粗暴的约束条件来说，更加的巧妙，但同时也更加的松散
- 节点是红色或者黑色
- 根是黑色
- 所有叶子节点都是黑色
- 红色节点和红色节点不能直接相连
- 任一节点的左右子树中黑色节点个数相同(黑高相同)
- 每次插入时插入红色节点
由于这种设计(主要是4和5)，使得左右子树的高度差不会超过一倍，达到了一定程度的平衡，同时因为插入的是红色节点，使得插入和删除时调整树的代价比较小，所以红黑树使用的很广泛。红黑树怎么调整这里就不谈了。
B树
4、B树，注意B树就叫B树，有的教材非要在”B”和”树”之间加个”-“,变成”B-树”，使得很多人以为还有一种B减树的存在，其实是不存在的。
B树其实就是多叉排序树。但是B树也有自己的约束，比如每个节点做多能分的叉是有限制的，最少能分的叉也是有限制的，并且要求所有叶子节点都在同一层，所以也免不了要对B树进行调整。
B树相对于平衡二叉树的不同在于，每个节点包含的关键字的数目不在是一个了，而可以是多个。B树应用到数据库时，可以充分利用磁盘块的性质（磁盘数据的存储是采用块 的形式存储的，每个块的大小为4k，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制在磁盘块的大小范围。
B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快
B+树
5、B+树，B+树与B树相比，它的非叶子节点部分不存储数据，仅仅用作判断该往哪个方向走，只有叶子节点存储数据，并且叶子节点通过指针串起来。B+树其实很像一本书的实现，非叶子节点部分就像书的索引部分一样，叶子节点部分就像书的内容一样。
B+树相对于B树的优点
- B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快
- B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
- B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
- B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
