【数据结构】查找：动态查找表(B-树，B+树，红黑树)

心已赠人 2021-10-30 06:06 356阅读 0赞

\#笔记整理  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]

# 查找 #

*  **[查找的基本概念][Link 1]**
 *  **[静态查找表——基于线性表的查找法（二分查找）][Link 1]**
 *  **[动态查找表——基于树表的查找法（二叉排序树、平衡二叉树][Link 2][、B树、红黑树）][B]**
 *  **[哈希表——计算式查找法][Link 3]**

# 动态查找表 #

**多路查找树（multi-way search tree）：**  
其每个结点的孩子树可以多于两个，且每一个结点可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。

## B-树 ##

也称B树， B-树是**一种平衡的多路查找树**，是一种组织和维护外存文件系统非常有效的数据结构，常用作文件索引。结点最大的孩子数目称为 B 树的阶。

一棵 m 阶 B-树或者是一棵空树，或者是满足下列要求的 m 叉树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]

#### B-树的查找 ####

查找过程和二叉排序树的查找类似。  
**大致步骤：**

*  在树中找结点（在磁盘上进行的，内外存交换）；
 *  在结点中找关键字（在内存中进行的）。

**详细步骤：**  
在每个记录上确定向下查找的路径不一定是二路（即二叉）的，而是 n+1 路的。  
将 key 与根结点中的 key\[i\] 进行比较：

1.  若 key=key\[i\]，则查找成功；
2.  若 key＜key\[1\]，则沿着指针 A\[0\] 所指的子树继续查找；
3.  若 key\[i\]＜key＜key\[i+1\]，则沿着指针 A\[i\] 所指的子树继续查找；
4.  若 k＞key\[n\]，则沿着指针 A\[n\] 所指的子树继续查找。

**注意：**

*  B-树的查找过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程。因此，B-树的查找时间与 B-树的阶数 m 和 B-树的高度 h 直接有关，必须加以权衡。
 *  在B-树上进行查找，查找成功所需的时间取决于关键字所在的层次，查找不成功所需的时间取决于树的高度。需要了解树的高度 h 与树中的关键字个数 N 之间的关系。

**查找分析：**  
在磁盘上查找的次数，即待查关键字所在结点在 B-树上的层次数，是决定 B-树查找效率的首要因素。  
含 N 个关键字的 m 阶 B-树的最大深度 h 分析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]

## B+树 ##

B+ 树可以看作是 B-树的一种变形，在实现文件索引结构方面比 B-树使用得更普遍。  
B+ 树是为了解决所有元素遍历等基本问题，应文件系统所需而诞生的一种 B 树的变形树。  
由于 B+ 树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是 B 树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫描，所以 B+ 树更加适合在区间查询的情况，通常 B+ 树用于数据库索引。

**一个 m 阶 B+ 树：**

1.  根结点只有一个，其分支数量范围为 \[2，m\]；
2.  分支结点，每个结点包含分支数范围为 \[ceil(m/2), m\]； // B-树范围左右都要 -1
3.  所有叶子结点都在同一层；
4.  非叶子节点的子树指针与关键字个数相同；
5.  为所有叶子节点增加一个链指针；
6.  所有关键字都在叶子节点出现(稠密索引)，(且链表中的关键字恰好是有序的)；
7.  非叶子节点相当于是叶子节点的索引(稀疏索引)，叶子节点相当于是存储(关键字)数据的数据层。

**B+树可进行两种查找运算：**  
1. 循着叶结点的链顺序进行查找；  
2. 从根结点开始，进行自顶向下，直至叶结点的随机查找。  
![在这里插入图片描述][20190820230302539.png]  
在查找时，若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。因此，在 B+树，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。同时 B+树的插入和删除仅在叶子结点上进行。

**B+树相对于 B-树的优势：**

*  需要随机查找时，从根结点出发，与 B-树的查找方式类似。
 *  在需要从最小的关键字进行顺序查找，可以直接从最左侧的叶子结点出发，不经过分支结点，一直沿着叶子结点就可以遍历所有的关键字。
 *  适合带有范围的查找。

**B-树与 B+树的区别：**

1.  关键字的数量不同；B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，B树虽然也有m个子结点，但是其只拥有m-1个关键字。
2.  存储的位置不同；B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。
3.  分支结点的构造不同；B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。
4.  查询不同；B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中一定走了一条从根结点到叶子结点的路径。
5.  叶子节点不同：B+树的相邻叶子节点之间有指针指向下一个节点，而B树没有。

为什么说 B+树比 B 树更适合数据库索引？

1.  B+树的磁盘读写代价更低：B+树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。
2.  B+树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
3.  由于 B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。
4.  B 树在提高了IO性能的同时并没有解决元素遍历的效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。

## 红黑树 ##

**红黑树的 5 个性质：**

1.  每个节点或者是黑色，或者是红色。
2.  根节点是黑色。
3.  每个空的叶子节点（NIL）是黑色。
4.  如果一个节点是红色的，则它的子节点必须是黑色的。
5.  从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]  
    红黑树从根到叶子的最长路径不会超过最短路径的 2 倍。

**红黑树与 AVL 树的区别：**

*  红黑树是牺牲了严格的高度平衡的优越条件；
 *  红黑树的插入删除效率比 AVL 树高：  
    插入时 AV L树和红黑树最多都需要旋转 2 次；而删除时，RB 最多3次，但是 AVL 最多达到 O(logn) 次。
 *  由于 AVL 树更为平衡，所以容易引起 unbalance，但是它的 search 效率更好。

红黑树的查询性能略微逊色于 AVL 树，因为他比 AVL 树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的 AVL 树最多 多一次比较，但是，红黑树在插入和删除上胜于 AVL 树，AVL 树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转(左旋与右旋)的开销，相较于 AVL 树为了维持平衡的开销要小得多，即维护更加方便。

参考资料：

1.  《数据结构（C语言版）》----严蔚敏
2.  《数据结构》课堂教学ppt ---- 刘立芳
3.  《数据结构算法与解析（STL版）》 ---- 高一凡
4.  《大话数据结构》 ---- 程杰
5.  《挑战程序设计竞赛2：算法和数据结构》 ---- 渡部有隆
6.  https://blog.csdn.net/qq\_35642036/article/details/82835122

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20211029/64bb4457df8242ecae620c39a7300d51.png
[Link 1]: https://steve.blog.csdn.net/article/details/99890774
[Link 2]: https://steve.blog.csdn.net/article/details/99892860
[B]: https://steve.blog.csdn.net/article/details/99894294
[Link 3]: https://steve.blog.csdn.net/article/details/99958241
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190820225927702.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: /images/20211029/8fc10ab49b894dbebfb42096b067c835.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]: /images/20211029/c43375a2e00d4c179d1ecfbcddbeac38.png
[20190820230302539.png]: /images/20211029/ee38cc8019e24b199cacd4b7581956f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]: /images/20211029/5eb6b3b436ab404ca35c296420aa2f21.png