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

我不是女神ヾ 2022-06-14 05:57 83阅读 0赞

from: http://blog.csdn.net/benpaobagzb/article/details/50805711

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

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

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

小结  
       B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；  
       B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；  
       所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；  
       B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；  
       B\*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

B树是为了提高磁盘或外部存储设备查找效率而产生的一种多路平衡查找树。

B+树为B树的变形结构，用于大多数[数据库][Link 2]或文件系统的存储而设计。

B树相对于红黑树的区别

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

B树和B+树的区别

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

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

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

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

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

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

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

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

[Link 1]: http://lib.csdn.net/base/datastructure
[Link 2]: http://lib.csdn.net/base/mysql
[Link 3]: http://lib.csdn.net/base/operatingsystem