转载：原文链接：https://blog.csdn.net/wanderlustLee/article/details/81297253

二叉查找树

二叉查找树就是左结点小于根节点，右结点大于根节点的一种排序树，也叫二叉搜索树。也叫BST，英文Binary Sort Tree。
二叉查找树比普通树查找更快，查找、插入、删除的时间复杂度为O(logN) 。但是二叉查找树有一种极端的情况，就是会变成一种线性链表似的结构。此时时间复杂度就变味了O(N)，为了解决这种情况，出现了二叉平衡树。

平衡二叉树

平衡二叉树全称平衡二叉搜索树，也叫AVL树。是一种自平衡的树。

AVL树也规定了左结点小于根节点，右结点大于根节点。并且还规定了左子树和右子树的高度差不得超过1。这样保证了它不会成为线性的链表。AVL树的查找稳定，查找、插入、删除的时间复杂度都为O(logN)，但是由于要维持自身的平衡，所以进行插入和删除结点操作的时候，需要对结点进行频繁的旋转。

AVL树每一个节点只能存放一个元素，并且每个节点只有两个子节点。当进行查找时，就需要多次磁盘IO，（数据是存放在磁盘中的，每次查询是将磁盘中的一页数据加入内存，树的每一层节点存放在一页中，不同层数据存放在不同页。）这样如果需要多层查询就需要多次磁盘IO。为了解决AVL树的这个问题，就出现了B树。

B树

B树也叫平衡树，也叫作B-树，英文为Blance-Tree。是一种多路平衡树。

一个m阶的B树规定了：

1. 根结点至少有两个子女。

2. 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m 。

3. 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m。

4. 所有的叶子结点都位于同一层。

5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

B树每一层存放了更多的节点，由AVL树的“瘦高”变成了“矮胖”。可以相对减少磁盘IO的次数。MongoDB的索引就是用B树实现的。

B树也是一种自平衡的树，在进行插入和删除操作时也需要对结点进行旋转等操作。

不过，B树的查找不稳定，最好的情况就是在根节点查到了，最坏的情况就是在叶子结点查到。另外，B树在遍历方面比较麻烦，由于需要进行中序遍历，所以也会进行一定数量的磁盘IO。为了解决这些问题，出现了B+树。

B+树

B+树每个非叶子结点存放的元素只用于索引作用，所有数据保存在叶子结点。

一个m阶的B+树规定了：

1. 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

因为非叶子结点中存放的元素不存放数据，所以每一层可以容纳更多元素，也就是磁盘中的每一页可以存放更多元素。这样在查找时，磁盘IO的次数也会减少。

另外，B+树的查找稳定，因为所有的数据都在叶子结点。每个叶子结点也通过指针指向构成了一种链表结构，所以遍历数据也会简单很多。

B+树的插入和删除和B树类似。

红黑树

红黑树也叫RB树，RB-Tree。是一种自平衡的二叉查找树，它的节点的颜色为红色和黑色。它不严格控制左、右子树高度或节点数之差小于等于1。也是一种解决二叉查找树极端情况的数据结构。