保护树木的十种方法_红黑树优点和应用场景

2024年 8月 29日下午6:43 • 激活谷笔记

红黑树是什么？红黑树与 B+树区别和应用场景？　　红黑树是什么？怎么实现？应用场景？　　红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉树。意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。除了具备该特性之外，红黑树还包括许多额外的信息。　　红黑树的特性: 红黑树是特殊的AVL树(二叉平衡树)，设计红黑树的目的，就是解决平衡树的维护起来比较麻烦的问题，红黑树，读取略逊于AVL，维护强于AVL，每次插入和删除的平均旋转次数应该是远小于平衡树。。　　红定理：不会有连续的红色节点。黑定理：根节点必须是黑节点，所有叶子节点都是黑色。　　性质1：每个节点要么是黑色，要么是红色。　　性质2：根节点是黑色。　　性质3：每个叶子节点（NIL）是黑色。　　性质4：每个红色结点的两个子结点一定都是黑色。　　性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。　　基本操作是添加、删除和旋转。在对红黑树进行添加或删除后，会用到旋转方法。旋转的目的是让树保持红黑树的特性。旋转包括两种：左旋和右旋；　　红黑树的应用比较广泛，主要是用它来存储有序的数据，它的查找、插入和删除操作的时间复杂度是O；　　
　　　　红黑树实际应用：　　IO多路复用的实现采用红黑树组织管理，以支持快速的增删改查. 　　ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器. 　　java中TreeMap，jdk1.8的hashmap的实现. 红黑树和 b+树的用途有什么区别？　　红黑树多用在内部排序，即全放在内存中的，java的map和set的内部实现就是红黑树。　　B+树多用于外存上时，B+也被成为一个磁盘友好的数据结构。　　B+树：　　B+ 树是一种树数据结构，是一个特殊的二叉树，每个节点通常有多个子节点，一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录，便于区间查找和遍历。 B+ 树的优点在于：由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。因此访问叶子节点上关联的数据也具有更好的缓存命中率。B+树的叶子结点都是相连的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的素可能在内存中不相邻，所以缓存命中性没有B+树好。但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的素可能离根节点更近，因此访问也更迅速。下面是B 树和B+树的区别图：
　　如图所示，区别有以下两点： B+树中只有叶子节点会带有指向记录的指针，而B树则所有节点都带有，在内部节点出现的索引项不会再出现在叶子节点中。 B+树中所有叶子节点都是通过指针连接在一起，而B树不会。　　B+树的优点：非叶子节点不会带上指向记录的指针，这样，一个块中可以容纳更多的索引项，一是可以降低树的高度。二是一个内部节点可以定位更多的叶子节点。叶子节点之间通过指针来连接，范围扫描将十分简单，而对于B树来说，则需要在叶子节点和内部节点不停的往返移动。具体的来讲，如何想扫描一次所有数据，对于b+树来说，可以从因为他们的叶子结点是连在一起的，所以可以横向的遍历过去。而对于b-树来说，就这能中序遍历了。　　B树的优点：对于在内部节点的数据，可直接得到，不必根据叶子节点来定位。　　b+树的应用场景: 　　B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树，适用于数据库存储数据. 　　二叉查找树的结构不适合数据库，因为它的查找效率与层数相关。越处在下层的数据，就需要越多次比较。　　　　为什么b+磁盘友好？　　磁盘读写代价更低　　树的非叶子结点里面没有数据，这样索引比较小，可以放在一个blcok（或者尽可能少的blcok）里面。避免了树形结构不断的向下查找，然后磁盘不停的寻道，读数据。这样的设计，可以降低io的次数。　　查询效率更加稳定　　非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。　　遍历所有的数据更方便　　B+树只要遍历叶子节点就可以实现整棵树的遍历，而其他的树形结构要中序遍历才可以访问所有的数据。　　

保护树木的十种方法_红黑树优点和应用场景

相关推荐