复习：AVL树/红黑树/B树/B+树原理及应用_b+树和红黑树插入的原理

一、AVL树

二叉查找树的一个局限性就是有可能退化成一个链表，这种情况下二叉查找树的效率就会急剧下降变成0(n)。而AVL树可以很好地解决BST的这种困境。

1、什么是AVL树

任何两个子树的高度差最大是1，这样的二叉树叫做AVL树。

2、AVL树的特点

（1）AVL的左右子树高度之差的绝对值不超过1。
（2）树中的每个左子树和右子树都是AVL。
（3）每个节点都有一个平衡因子,任一节点的平衡因子至多为1。
（4）平衡二叉树的高度和结点数量之间的关系是O(logn)。

3、平衡因子

平衡因子 = | 左子树高度 - 右子树高度 |

4、维持自平衡性

AVL树为了维持自身平衡性，在插入元素时，计算了每个节点的平衡因子是否大于1，如果大于，那么就将进行相应的旋转操作以维持平衡性。

二、红黑树

一种二叉查找树，但是在每个节点增加一个存储位表示节点的颜色，可以是红色或者黑色，通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条 路径会比其他路径长两倍。是一种弱平衡二叉树（由于是弱平衡，相同节点的情况下，AVL树的高度低于红黑树），相对于严格要求的AVL树而言，红黑树旋转的次数变少，因此在搜索、删除、插入操作多的情况，可以使用红黑树。

1、红黑树的性质：

算法导论：一棵有n个内节点的红黑树高度至多为2lg(n+1)，则h=O(log(n))

0）在红黑树中，叶子结点指空结点NULL。
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。（首尾必黑）
4）如果一个结点是红的，那么它的俩个儿子都是黑的。（不存在连续2红）
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。（黑色完美平衡）
5-1）右5知，如果一个结点存在黑子结点，那么该结点肯定有两个子结点

2、红黑树与AVL树的比较：

• AVL是严格的平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；

• 红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以O(logn) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。

所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL树，Windows NT内核中广泛存在.

如果搜索，插入删除次数几乎差不多，应选择红黑树。即，有时仅为了排序（建立-遍历-删除），不查找或查找次数很少，R-B树合算一些。

3、红黑树的应用

• 广泛用于C++的STL中,map和set都是用红黑树实现的.

• 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间.

• IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查.

• ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.

• java中TreeMap、hashmap、concurrenthashmap（1.8）的实现.

三、B树（B-树与B树等同）

b树（balance tree）和b+树应用在数据库索引，可以认为是m叉的多路平衡查找树，但是从理论上讲，二叉树查找速度和比较次数都是最小的，为什么不用二叉树呢？
因为我们要考虑磁盘IO的影响，它相对于内存来说是很慢的。数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘页（对应索引树的节点）。所以我们要减少IO次数，对于树来说，IO次数就是树的高度，而“矮胖”就是b树的特征之一，它的每个节点最多包含m个孩子，m称为b树的阶，m的大小取决于磁盘页的大小。

1、一个M阶的b树具有如下几个特征：

• 定义任意非叶子结点最多只有M个儿子，且M>2；
• 根结点的儿子数为[2, M]；
• 除根结点以外的非叶子结点的儿子数为[M/2, M]，向上取整（下边界怎么理解？？）；
• 非叶子结点的关键字个数=儿子数-1（2刀切3段，7刀切8段）；
• 所有叶子结点位于同一层；
• k个关键字把节点拆成k+1段，分别指向k+1个儿子，同时满足查找树的大小关系。

2、有关b树的一些特性，注意与后面的b+树区分：

• 关键字集合分布在整颗树中；
• 任何一个关键字出现且只出现在一个结点中；
• 搜索有可能在非叶子结点结束；
• 其搜索性能等价于在关键字全集内做一次二分查找；

3、如图是一个3阶b树，顺便讲一下查询元素5的过程：

第一次磁盘IO，把9所在节点读到内存，9节点中含有value，刚好要搜索结点9，则在此处返回了不必再深入树的下层。然而目标是5，小于9，跳转到小于9对应的节点；

第二次磁盘IO，还是读节点到内存，在内存中把5依次和2、6比较，定位到2、6中间区域对应的节点；
第三次磁盘IO就不上图了，跟第二步一样，然后就找到了目标5。

• 可以看到，b树在查询时的比较次数并不比二叉树少，尤其是节点中的数非常多时，但是内存的比较速度非常快，耗时可以忽略，所以只要树的高度低，IO少，就可以提高查询性能，这是b树的优势之一。
  

四、B+树

b+树，是b树的一种变体，查询性能更好。

1、m阶的b+树的特征：

• 有n棵子树的非叶子结点中含有n个关键字（b树是n-1个），这些关键字key没有数据value，结点中仅含其子树中的最大（或最小）关键字的结点指针，所有数据value都保存在叶子节点（b树是每个关键字都保存数据）。
• 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
• 所有关键字都在叶子节点出现(稠密索引). (且链表中的关键字恰好是有序的);
• 非叶子节点相当于是叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层.
• 同一个数字会在不同节点中重复出现，根节点的最大元素就是b+树的最大元素。
  
  

2、b+树相比于b树的查询优势：

• b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”；
• b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）；
• 对于区间查找和范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历，

3、B/B+树的共同优点：

考虑磁盘IO的影响，它相对于内存来说是很慢的。数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘页（对应索引树的节点）。所以我们要减少IO次数，对于树来说，IO次数就是树的高度，而“矮胖”就是b树的特征之一，m的大小取决于磁盘页的大小。