关于c++:Linux内核深入理解红黑树与B树应用场景

2次阅读

共计 4141 个字符，预计需要花费 11 分钟才能阅读完成。

两者都是有序数据结构，可用作数据容器。
红黑树多用在外部排序，即全放在内存中的，微软 STL 的 map 和 set 的外部实现就是红黑树。B 树多用在内存里放不下，大部分数据存储在外存上时。因为 B 树层数少，因而能够确保每次操作，读取磁盘的次数尽可能的少。
在数据较小，能够齐全放到内存中时，红黑树的工夫复杂度比 B 树低。反之，数据量较大，外存中占次要局部时，B 树因其读磁盘次数少，而具备更快的速度。

(1)红黑树，B 树，B+ 树，B- 树
具体了解：
1. 红黑树 rbtree 二叉排序树
map 就是采纳红黑树存储的，红黑树(RB Tree) 是均衡二叉树，其长处就是树到叶子节点深度统一，查找的效率也就一样，为 logN. 在履行查找，插入，删除的效率都统一，而当是全副静态数据时，没有太多劣势，可能采纳 hash 表各适合。
hash_map 是一个 hash table 占用内存更多，查找效率高一些，然而 hash 的工夫比拟费时。
总体来说，hash_map 查找速度会比 map 快，而且查找速度根本和数据数据量大小，属于常数级别; 而 map 的查找速度是 log(n)级别。并不一定常数就比 log(n)小，hash 还有 hash 函数的耗时，明确了吧，如果你思考效率，特地是在元素达到肯定数量级时，思考思考 hash_map。但若你对内存应用特地严格，心愿程序尽可能少耗费内存，那么肯定要小心，hash_map 可能会让你陷入难堪，特地是当你的 hash_map 对象特地多时，你就更无法控制了，而且 hash_map 的结构速度较慢。
当初晓得如何抉择了吗？衡量三个因素: 查找速度, 数据量, 内存应用。
trie 树 Double Array 字典查找树
Trie 树既可用于个别的字典搜寻，也可用于索引查找。
每个节点相当于 DFA 的一个状态，终止状态为查找完结。有序查找的过程相当于状态的一直转换
对于给定的一个字符串 a1,a2,a3,…,an. 则
采纳 TRIE 树搜寻通过 n 次搜寻即可实现一次查找。不过如同还是没有 B 树的搜寻效率高，B 树搜索算法复杂度为 logt(n+1/2). 当 t 趋势大，搜寻效率变得高效。怪不得 DB2 的拜访内存设置为虚拟内存的一个 PAGE 大小，而且帧切换频率升高，无需常常的 PAGE 切换。
2.B 树
即二叉搜寻树：

1. 所有非叶子结点至少领有两个儿子（Left 和 Right）；
2. 所有结点存储一个关键字；
3. 非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

如：
B 树的搜寻，从根结点开始，如果查问的关键字与结点的关键字相等，那么就命中；否则，如果查问关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；
如果 B 树的所有非叶子结点的左右子树的结点数目均放弃差不多（均衡），那么 B 树的搜寻性能迫近二分查找；但它比间断内存空间的二分查找的长处是，扭转 B 树结构（插入与删除结点）不须要挪动大段的内存数据，甚至通常是常数开销；
如：
但 B 树在通过屡次插入与删除后，有可能导致不同的构造：
左边也是一个 B 树，但它的搜寻性能曾经是线性的了；同样的关键字汇合有可能导致不同的树结构索引；所以，应用 B 树还要思考尽可能让 B 树放弃左图的构造，和防止右图的构造，也就是所谓的“均衡”问题；
理论应用的 B 树都是在原 B 树的根底上加上均衡算法，即“均衡二叉树”；如何放弃 B 树结点散布平均的均衡算法是均衡二叉树的要害；均衡算法是一种在 B 树中插入和删除结点的策略；
3.B- 树
是一种多路搜寻树（并不是二叉的）：

1. 定义任意非叶子结点最多只有 M 个儿子；且 M >2；
2. 根结点的儿子数为[2, M]；
3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
4. 每个结点寄存至多 M /2-1（取上整）和至少 M - 1 个关键字；（至多 2 个关键字）;
5. 非叶子结点的关键字个数 = 指向儿子的指针个数 -1；
6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且 K[i] < K[i+1]；
7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中 P[1]指向关键字小于 K[1]的子树，P[M]指向关键字大于 K[M-1]的子树，其它 P[i]指向关键字属于 (K[i-1], K[i]) 的子树；
8. 所有叶子结点位于同一层；

如：（M=3）
B- 树的搜寻，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则完结，否则进入查问关键字所属范畴的儿子结点；反复，直到所对应的儿子指针为空，或曾经是叶子结点；
B- 树的个性：

1. 关键字汇合散布在整颗树中；
2. 任何一个关键字呈现且只呈现在一个结点中；
3. 搜寻有可能在非叶子结点完结；
4. 其搜寻性能等价于在关键字选集内做一次二分查找；
5. 主动档次管制；

因为限度了除根结点以外的非叶子结点，至多含有 M / 2 个儿子，确保了结点的至多利用率，其最底搜寻性能为：
其中，M 为设定的非叶子结点最多子树个数，N 为关键字总数；
所以 B - 树的性能总是等价于二分查找（与 M 值无关），也就没有 B 树均衡的问题；
因为 M / 2 的限度，在插入结点时，如果结点已满，须要将结点决裂为两个各占 M / 2 的结点；删除结点时，需将两个有余 M / 2 的兄弟结点合并；
4.B+ 树
B+ 树是 B - 树的变体，也是一种多路搜寻树：

1. 其定义根本与 B - 树同，除了;
2. 非叶子结点的子树指针与关键字个数雷同；
3. 非叶子结点的子树指针 P[i]，指向关键字值属于 [K[i], K[i+1]) 的子树（B- 树是开区间）；
5. 为所有叶子结点减少一个链指针；
6. 所有关键字都在叶子结点呈现；

如：（M=3）
B+ 的搜寻与 B - 树也基本相同，区别是 B + 树只有达到叶子结点才命中（B- 树能够在非叶子结点命中），其性能也等价于在关键字选集做一次二分查找；
B+ 的个性：

1. 所有关键字都呈现在叶子结点的链表中（浓密索引），且链表中的关键字恰好是有序的；
2. 不可能在非叶子结点命中；
3. 非叶子结点相当于是叶子结点的索引（稠密索引），叶子结点相当于是存储（关键字）数据的数据层；
4. 更适宜文件索引零碎；

5.B 树
是 B + 树的变体，在 B + 树的非根和非叶子结点再减少指向兄弟的指针；
B 树定义了非叶子结点关键字个数至多为 (2/3)M，即块的最低使用率为 2 /3（代替 B + 树的 1 /2）；
B+ 树的决裂：当一个结点满时，调配一个新的结点，并将原结点中 1 / 2 的数据复制到新结点，最初在父结点中减少新结点的指针；B+ 树的决裂只影响原结点和父结点，而不会影响兄弟结点，所以它不须要指向兄弟的指针；
B 树的决裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最初批改父结点中兄弟结点的关键字（因为兄弟结点的关键字范畴扭转了）；如果兄弟也满了，则在原结点与兄弟结点之间减少新结点，并各复制 1 / 3 的数据到新结点，最初在父结点减少新结点的指针；
所以，B 树调配新结点的概率比 B + 树要低，空间使用率更高；
小结
B 树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
B- 树：多路搜寻树，每个结点存储 M / 2 到 M 个关键字，非叶子结点存储指向关键字范畴的子结点；
所有关键字在整颗树中呈现，且只呈现一次，非叶子结点能够命中；
B+ 树：在 B - 树根底上，为叶子结点减少链表指针，所有关键字都在叶子结点中呈现，非叶子结点作为叶子结点的索引；B+ 树总是到叶子结点才命中；
B 树：在 B + 树根底上，为非叶子结点也减少链表指针，将结点的最低利用率从 1 / 2 进步到 2 /3；

B 树是为了进步磁盘或内部存储设备查找效率而产生的一种多路均衡查找树。
B+ 树为 B 树的变形构造，用于大多数数据库或文件系统的存储而设计。

在大规模数据存储的时候，红黑树往往呈现因为树的深度过大而造成磁盘 IO 读写过于频繁，进而导致效率低下的状况。为什么会呈现这样的状况，咱们晓得要获取磁盘上数据，必须先通过磁盘移动臂挪动到数据所在的柱面，而后找到指定盘面，接着旋转盘面找到数据所在的磁道，最初对数据进行读写。磁盘 IO 代价次要破费在查找所需的柱面上，树的深度过大会造成磁盘 IO 频繁读写。依据磁盘查找存取的次数往往由树的高度所决定，所以，只有咱们通过某种较好的树结构缩小树的构造尽量减少树的高度，B 树能够有多个子女，从几十到上千，能够升高树的高度。

B 树：所有叶子结点都呈现在同一层，叶子结点不蕴含任何关键字信息。
B+ 树：所有的叶子结点中蕴含了全副关键字的信息，及指向含有这些关键字记录的指针，且叶子结点自身依关键字的大小自小而大的程序链接，所有的非终端结点能够看成是索引局部，结点中仅含有其子树根结点中最大（或最小）关键字。(而 B 树的非终节点也蕴含须要查找的无效信息)

为什么说 B + 比 B 树更适宜理论利用中操作系统的文件索引和数据库索引？

1) B+ 的磁盘读写代价更低

B+ 的外部结点并没有指向关键字具体信息的指针。因而其外部结点绝对 B 树更小。如果把所有同一外部结点的关键字寄存在同一盘块中，那么盘块所能包容的关键字数量也越多。一次性读入内存中的须要查找的关键字也就越多。相对来说 IO 读写次数也就升高了。

2) B±tree 的查问效率更加稳固

因为非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查问的门路长度雷同，导致每一个数据的查问效率相当。

数据库索引采纳 B + 树的次要起因是 B 树在进步了磁盘 IO 性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+ 树应运而生。B+ 树只有遍历叶子节点就能够实现整棵树的遍历。而且在数据库中基于范畴的查问是十分频繁的，而 B 树不反对这样的操作（或者说效率太低）。

本群收费分享学习材料 (C/C++，Linux，golang,Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，ffmpeg，TCP/IP，协程，DPDK，嵌入式) 等; 交换探讨支付材料请加 群 Q:1106675687课程地址:https://ke.qq.com/course/4177…。

正文完