为什么要使用红黑树，B树和B+树

系统管理员 2020-11-14 17:48 890阅读 0赞

**一、红黑树**  
**1、红黑树的特性**  
（1）每个节点或者是黑色，或者是红色。  
（2）根节点是黑色。  
（3）每个叶子节点（NIL）是黑色。 \[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！\]  
（4）如果一个节点是红色的，则它的子节点必须是黑色的。  
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。\[这里指到叶子节点的路径\]  
包含n个内部节点的红黑树的高度是 O(log(n)).  
如图：  
![在这里插入图片描述][2018122117224515]  
**2、红黑树的使用场景**  
java中使用到红黑树的有TreeSet和JDK1.8的HashMap。

但是问题来了，为什么要使用红黑树，红黑树的插入和删除都要满足以上5个特性，而作非常复杂的操作。  
**原因：**  
红黑树是一种平衡树，他复杂的定义和规则都是为了保证树的平衡性。如果树不保证他的平衡性就是下图：**很显然这就变成一个链表了。**  
![在这里插入图片描述][20181221112216158.png]

**保证平衡性的最大的目的就是降低树的高度，因为树的查找性能取决于树的高度。所以树的高度越低搜索的效率越高！**  
这也是为什么存在二叉树、搜索二叉树等，各类树的目的。

**二、B树**  
**1、B树的特性**  
一棵m阶的B树的满足条件：  
（1）每个节点至多有m棵子树  
（2）根节点除外，其它每个分支节点至少有【m/2】棵子树  
（3）根节点至少有两棵子树（除非B树只包含一个节点）  
（4）所有叶子节点在同一层上，B树的叶子节点可以看成一种外部节点，不包含任何信息。  
（5）有j个孩子的非叶结点恰好有j-1个关键码，关键码按递增次序排列。  
B 树又叫平衡多路查找树。如图：  
![在这里插入图片描述][8394323_130745821166Sc.jpg]

**2、B树的使用场景**  
B树多用于做文件系统的索引。

那么问题来了：为什么要用B树，红黑树不是就挺好的么？  
**原因：**  
B树和二叉树、红黑树相比较，子树更多也就是路数越多，子树月多表示数的高度越低，搜索效率越高，当然如果路数太多就可能变成一个有序数组了（如下图）。所以当然不可能使得路数无限大。  
![在这里插入图片描述][20181221163002503.png]  
回到正题：正因为文件系统和数据库一般都是存在电脑硬盘上的，如果数据量太大的话不一定能一次性加载到内存中。（一棵树不能一次性加载完怎么查找对吧？）但是**B树可以多路存储**。也正因为B树的这一个优点，可以在文件查找的时候每次只加载一个节点的内容存入内存来查找。而红黑树在内存中查找非常块，但是如果在数据库和文件系统中，显然B树更优。

**三、B+树**  
B+树是B树的变种，有着比B树更高的查询效率。  
**1、B+树的特性**  
（1）有 k 个子树的中间节点包含有 k 个元素（B 树中是 k-1 个元素），每个元素不保存数据，只用来索引，所有数据  
都保存在叶子节点。  
（2）所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小  
自小而大顺序链接。  
（3）所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

![在这里插入图片描述][70]

**2、B+树的使用场景**  
B+树是在B树的基础上进行改造的，他的数据都在叶子节点，同时叶子节点之间还加了指针形成链表。  
B+树多用于数据库中的索引。

那么为什么B+树用于数据库中的索引呢？  
**原因：**  
因为在数据库中select常常不只是查询一条记录，常常要查询多条记录。比如：按照id的排序的后10条。如果是多条的话，B树需要做中序遍历，可能要跨层访问。而B+树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能够把所有数据取出来了。

[2018122117224515]: /images/1605375915316.jpg
[20181221112216158.png]: /images/1605375942564.png
[8394323_130745821166Sc.jpg]: http://dandelioncloud.cn/attachment/201106/7/8394323_130745821166Sc.jpg
[20181221163002503.png]: /images/1605375992777.png
[70]: /images/1605376021876.png