红黑树和B树应用场景总结

左手的ㄟ右手 2022-08-20 15:23 86阅读 0赞

红黑树和B树应用场景有何不同？

2者都是有序数据结构，可用作数据容器。  
红黑树多用在内部排序，即全放在内存中的，微软STL的map和set的内部实现就是红黑树。  
B树多用在内存里放不下，大部分数据存储在外存上时。因为B树层数少，因此可以确保每次操作，读取磁盘的次数尽可能的少。

在数据较小，可以完全放到内存中时，红黑树的时间复杂度比B树低。  
反之，数据量较大，外存中占主要部分时，B树因其读磁盘次数少，而具有更快的速度。

红黑树，B树，B+树，B-树 理解  
  
红黑树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切换。  
  
B树  
       即二叉搜索树：  
       1.所有非叶子结点至多拥有两个儿子（Left和Right）；  
       2.所有结点存储一个关键字；  
       3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；  
       如：  
       B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；  
       如果B树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变B树结构（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；  
       如：  
    但B树在经过多次插入与删除后，有可能导致不同的结构：  
   右边也是一个B树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；所以，使用B树还要考虑尽可能让B树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题；        
       实际使用的B树都是在原B树的基础上加上平衡算法，即“平衡二叉树”；如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键；平衡算法是一种在B树中插入和删除结点的策略；  
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的兄弟结点合并；  
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.更适合文件索引系统；  
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树的变形结构，用于大多数数据库或文件系统的存储而设计。

B树相对于红黑树的区别

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

B树和B+树的区别

B树所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息。

B+树所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接，所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)

为什么说**B+比**B树更适合实际应用中操作系统的文件索引和数据库索引？

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

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

2) B\+\-tree的查询效率更加稳定

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

数据库索引采用B+树的主要原因是 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）