平衡二叉树与红黑树
-
- 一、红黑树的性质：
- 二、红黑树的主要用途，和其他树的比较：
- 三、运用场景
一、红黑树的性质：
红黑树是一颗二叉搜索树，通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。 树的每个结点包含5个属性，color，key，left，right，p。如果一个结点没有子结点或父结点，则该结点的响应指针属性的指为NIL。我们可以把这些NIL视为指向二叉搜索树的叶结点（外部节点）的指针，把带关键字的结点视为树的内部结点。 一颗红黑树是满足下面红黑性质的二叉搜索树： 1.每个结点或是红色的，或是黑色的。 2.根结点是黑色的。 3.每个叶子结点（NIL）是黑色的。 4.如果一个结点是红的，那么它的两个子结点都是黑的。 5.对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑结点。 ——引用自《算法导论》 第十三章 红黑树 红黑树的性质
红黑树的平衡通过旋转实现，任何不平衡都会在三次旋转之内解决。查找，插入，删除的时间复杂度均为O(log(N))
二、红黑树的主要用途，和其他树的比较：
1.主要用途是搜索 2.AVL和红黑树都是二叉搜索树的变体。 3.AVL树是严格维持平衡的，红黑树是黑平衡的。但是维持平衡又需要额外的操作，这也加大了数据结构的时间复杂度，所以红黑树可以看做是二叉搜索树和AVL树的一个折中，可以尽量维持树的平衡，又不用话过多的时间来维持数据结构的性质。 4.AVL和红黑树适合内部存储使用 红黑树的统计性能要好于AVL，但极端性能略差。 5.AVL树适合用于插入删除次数比较少，但查找多的情况。 用于搜索时，插入删除次数多的情况下我们就用红黑树 windows对进程地址空间的管理用到了AVL树 6.B树适合外部存储使用 B树，B 树：多路查找树，一般用于数据库中做索引，因为它们分支多，层数少。因为磁盘I/O是非常耗时的，大量数据存储在磁盘中，我们要有效的减少磁盘I/O次数避免磁盘频繁的查找。AVL和红黑树的问题在于，树的层高过高，在磁盘查询的时候，需要先到对应的扇区，找到下一层节点的位置，再到下一层扇区，找到节点，再继续查找。对于1024个数据，二叉树则需要10层，查询要遍历的扇区过多。 B 树是B树的变种树，有n棵子树的节点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子节点。是为文件系统而生的。 B 树相对B树磁盘读写代价更低：因为B 树非叶子结点只存储键值，单个节点占空间小，索引块能够存储更多的节点，从磁盘读索引时所需的索引块更少，所以索引查找时I/O次数较B-Tree索引少，效率更高。而且B Tree在叶子节点存放的记录以链表的形式链接，范围查找或遍历效率更高。Mysql InnoDB用的就是B Tree索引。 6.Trie树，又名单词查找树，常用来操作字符串，它是不同字符串的相同前缀只保存一份。相对直接保存字符串肯定是节省空间的，但是它保存大量字符串时会很耗费内存（是内存）。 类似的有：前缀树(prefix tree)，后缀树(suffix tree)，radix tree(patricia tree, compactprefix tree)，crit-bit tree（解决耗费内存问题），以及前面说的double array trie。 前缀树：字符串快速检索，字符串排序，最长公共前缀，自动匹配前缀显示后缀。 后缀树：查找字符串s1在s2中，字符串s1在s2中出现的次数，字符串s1,s2最长公共部分，最长回文串。
三、运用场景
总结了部分红黑树的实际应用 1.sk_buffer 2.epoll保存socket，epoll在内核中的实现，用红黑树管理事件块。 3.Nginx中，用红黑树管理timer，因为红黑树是有序的，可以很快的得到距离当前最小的定时器。 timer_add timer_delete timer_trigger 触发 4.java中的TreeSet，TreeMap 5.STL中的map和set 6.著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。
①sk_buffer sk_buff( socket buffer )结构是linux TCP/IP stack中，用于管理Data Buffer的结构，它管理和控制接收或发送数据包的信息。 为了提高网络处理的性能，应尽量避免数据包的拷贝。目前Linux协议栈在接收数据的时候，需要拷贝2次。数据包进入网卡驱动后拷贝一次，从内核空间递交给用户空间的应用时再拷贝一次。 @TODO
1.1 sk_buffer的组成 packet data ： 通过网卡收发的报文，包括链路层，网络层，传输层的协议头和携带的应用数据，包括headroom ， data ， tail room三部分。 skb_shared_info： 作为 packet data的补充，用于存储ip分片，其中sk_buf *frag_list 是一系列子skbuff链表，而frag[]是由一组单独的page组成的数据缓冲区。 data buffer：用于存储packet data的缓冲区，分为以上2部分。 sk_buff：缓冲区控制结构sk_buff。 整个sk_buff结构图如图：
1.2 sk_buffer的结构
代码语言：javascript复制struct sk_buff {
struct sk_buff *next;
struck sk_buff *prev;
struct sock *sk;
struct skb_timeval tstamp; /* Time we arrived，记录接收或发送报文的时间戳*/
struct net_device *dev; /*通过该设备接收或发送，记录网络接口的信息和完成操作*/
struct net_device *input_dev; /*接收数据的网络设备*/
struct net_device *curlayer_input_dev;
struct net_device *l2tp_input_dev;
union {
struct tcphdr *th;
struct udphdr *uh;
struct icmphdr*icmph;
struct igmphdr *igmph;
struct iphdr *ipiph;
struct ipv6hdr*ipv6h;
unsigned char *raw;
} h; //传输层报头
union {
struct iphdr *iph;
struct ipv6hdr*ipv6h;
struct arphdr *arph;
unsigned char *raw;
} nh; //网络层报头
union {
unsigned char *raw;
} mac; //链路层报头
.
.
.
unsigned int len, //len缓冲区中数据部分的长度。
data_len, //data_len只计算分片中数据的长度
mac_len, //mac头的长度
csum; //校验和
__u32 priority;
__u8 local_df:1,
cloned:1, //表示该结构是另一个sk_buff克隆的
ip_summed:2,
nohdr:1,
nfctinfo:3;
__u8 pkt_type:3,
fclone:2,
ipvs_property:1;
__be16 protocol;
__u32 flag; /*packet flags*/
.
.
.
/* These elements must be at the end, see alloc_skb() for details. */
unsigned int truesize; //这是缓冲区的总长度，包括sk_buff结构和数据部分
atomic_t users;
unsigned char *head, //指向缓冲区的头部
*data,// 指向实际数据的头部
*tail, //指向实际数据的尾部
*end;//指向缓冲区的尾部
};引用自 https://www.cnblogs.com/tzh36/p/5424564.html 后续待修改 引用自 http://www.doc88.com/p-17346276334.html 后续待修改
1.3 struct sk_buff *next, struct sk_buff *prev 有些sk_buff成员变量的作用是方便查找，或者是连接数据结构本身. 内核可以把sk_buff组织成一个双向链表。当然，这个链表的结构要比常见的双向链表的结构复杂一点。就像任何一个双向链表一样，sk_buff中有两个指针next和prev，其中，next指向下一个节点，而prev指向上一个节点。但是，这个链表还有另一个需求：每个sk_buff结构都必须能够很快找到链表头节点。为了满足这个需求，在第一个节点前面会插入另一个结构sk_buff_head，这是一个辅助节点，它的定义如下。
代码语言：javascript复制/**************** * 作用：sk_buff链表的表头; * @next: 链表的下一个元素; * @prev: 链表的前一个元素; * @qlen: sk_buff结构的数量; * @lock: 自旋锁; **************/
struct sk_buff_head
{
struct sk_buff *next;
struct sk_buff *prev;
__u32 qlen;
spinlock_t lock;
};sk_buff和sk_buff_head的前两个元素是一样的：next和prev指针。这使得它们可以放到同一个链表中，尽管sk_buff_head要比sk_buff小得多。另外，相同的函数可以同样应用于sk_buff和sk_buff_head ②.epoll保存socket，用红黑树管理事件块 @TODO
③Nginx中红黑树管理timer nginx中的定时器是放在一个全局的叫做ngx_event_timer_rbtree的红黑树中的，通过ngx_add_timer来添加定时器，等超时定时事件执行完后就从红黑树中移除该定时器，所以想要达到循环定时的目的，那就需要每次在执行定时操作后再次通过ngx_add_timer添加到定时列表中。 nginx通过红黑树来维护所有的timer节点，在worker进程的每一次循环中都会调用ngx_process_events_and_timers函数，在该函数中就会调用处理定时器的函数ngx_event_expire_timers，每次该函数都不断的从红黑树中取出时间值最小的，查看他们是否已经超时，然后执行他们的函数，直到取出的节点的时间没有超时为止。 ————————— nginx定时器实现的源码有下面几个接口 3.1.1初始化定时器 来看一下ngx_event_timer_init这个函数是怎么实现的, 在 src/event/ngx_event_timer.c 中
代码语言：javascript复制ngx_int_t
ngx_event_timer_init(ngx_log_t *log) {
ngx_rbtree_init(&ngx_event_timer_rbtree, &ngx_event_timer_sentinel,
ngx_rbtree_insert_timer_value);//初始化了一个红黑树
return NGX_OK;
}调用ngx_rbtree_init初始化一颗红黑树，其中前两个参数是全局变量
代码语言：javascript复制ngx_rbtree_t ngx_event_timer_rbtree; //红黑树
static ngx_rbtree_node_t ngx_event_timer_sentinel; //哨兵结点ngx_rbtree_insert_timer_value 是ngx_rbtree_t中的用于插入定时器的处理函数，支持自定义：
代码语言：javascript复制typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
// 红黑树中的结点
struct ngx_rbtree_node_s {
ngx_rbtree_key_t key; //用于保存定时时间戳
ngx_rbtree_node_t *left;
ngx_rbtree_node_t *right;
ngx_rbtree_node_t *parent;
u_char color;
u_char data;
};
// 红黑树
struct ngx_rbtree_s {
ngx_rbtree_node_t *root;//根结点
ngx_rbtree_node_t *sentinel;//哨兵结点
ngx_rbtree_insert_pt insert; //插入结点处理函数
};3.1.2添加计时器 添加前会判断新的定时器与现在的定时器是否间隔很短，如果时间时隔小于NGX_TIMER_LAZY_DELAY所定义的毫秒数，则无需向红黑树添加，仍旧使用原有的定时器，提高性能。
代码语言：javascript复制#define NGX_TIMER_LAZY_DELAY 300 //时间差：300毫秒
static ngx_inline void
ngx_event_add_timer(ngx_event_t *ev, ngx_msec_t timer)
{
ngx_msec_t key;
ngx_msec_int_t diff;
// 计算新key值
key = ngx_current_msec timer;
//已注册有定时事件
if (ev->timer_set) {
/* 如果新的key值与现有的key值相差小于NGX_TIMER_LAZY_DELAY定义的毫秒数 /* 则不对rbtee做任何操作，直接退出，继续使用现有的key值。 diff = (ngx_msec_int_t) (key - ev->timer.key); if (ngx_abs(diff) < NGX_TIMER_LAZY_DELAY) { return; } //相差大于NGX_TIMER_LAZY_DELAY定义的毫秒数，先将rbtree结点删除 ngx_del_timer(ev); } //使用新的key值。 ev->timer.key = key; //向红黑树中注册新的定时事件，并将time_set置1 ngx_rbtree_insert(&ngx_event_timer_rbtree, &ev->timer); ev->timer_set = 1; } 3.1.3删除定时器 先从红黑树中删除节点，再将timer_set标志位置0
代码语言：javascript复制static ngx_inline void
ngx_event_del_timer(ngx_event_t *ev)
{
ngx_rbtree_delete(&ngx_event_timer_rbtree, &ev->timer);
ev->timer_set = 0;
}3.1.4查找定时器 从红黑树中找到key值最小的结点，并根据超时与否，返回不同的值
代码语言：javascript复制ngx_msec_t
ngx_event_find_timer(void)
{
ngx_msec_int_t timer;
ngx_rbtree_node_t *node, *root, *sentinel;
// 没有定时器，直接返回-1
if (ngx_event_timer_rbtree.root == &ngx_event_timer_sentinel) {
return NGX_TIMER_INFINITE;
}
root = ngx_event_timer_rbtree.root;
sentinel = ngx_event_timer_rbtree.sentinel;
// 从树上找到key值最小的结点
node = ngx_rbtree_min(root, sentinel);
// 定时器中的key与当前时间戳比较，如果小于当前时间戳，说明已超时了，反之则未超时
timer = (ngx_msec_int_t) (node->key - ngx_current_msec);
// 超时返回0，否则返回即将到达当前时间点的的数值
return (ngx_msec_t) (timer > 0 ? timer : 0);
}
其中，查找最小key结点使用了ngx_rbtree_min函数，查找树的最左边结点。
static ngx_inline ngx_rbtree_node_t * ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{
while (node->left != sentinel) {
node = node->left;
}
return node;
}3.2超时处理 循环查找树种已超时结点，删除超时结点，并调用超时处理函数，知道第一个还未超时的结点，退出。
代码语言：javascript复制void ngx_event_expire_timers(void)
{
ngx_event_t *ev;
ngx_rbtree_node_t *node, *root, *sentinel;
sentinel = ngx_event_timer_rbtree.sentinel;
for ( ;; ) {
root = ngx_event_timer_rbtree.root;
//没有直接返回
if (root == sentinel) {
return;
}
// 查找key值最小的结点
node = ngx_rbtree_min(root, sentinel);
/* node->key > ngx_current_msec */
// 循环查找最小结点，直到遇到第一个还未到时间的结点，退出循环
if ((ngx_msec_int_t) (node->key - ngx_current_msec) > 0) {
return;
}
//根据成员地址和偏移，得出成员所在结构体的地址
ev = (ngx_event_t *) ((char *) node - offsetof(ngx_event_t, timer));
// 删除定时器结点
ngx_rbtree_delete(&ngx_event_timer_rbtree, &ev->timer);
//标志位置0
ev->timer_set = 0;
// 已超时标志位置1
ev->timedout = 1;
// 调用超时事件处理函数
ev->handler(ev);
}
}3.3Nginx定时器调用流程 3.3.1初始化 在nginx_event_process_init函数中调用了定时器初始化函数
代码语言：javascript复制static ngx_int_t ngx_event_process_init(ngx_cycle_t *cycle)
{
......
if (ngx_event_timer_init(cycle->log) == NGX_ERROR) {
return NGX_ERROR;
}
......
}3.3.2设置事件的超时处理函数，并通过ngx_add_timer接口添加定时器事件 ngx_add_timer是一个宏定义，实际调用的是ngx_event_add_timer函数
代码语言：javascript复制#define ngx_add_timer ngx_event_add_timer
#define ngx_del_timer ngx_event_del_timer摘取nginx添加定时器事件的代码片段：
代码语言：javascript复制 ngx_cleaner_event.handler = ngx_clean_old_cycles; //设置超时处理函数
ngx_cleaner_event.log = cycle->log;
ngx_cleaner_event.data = &dumb;
dumb.fd = (ngx_socket_t) -1;
}
......
if (!ngx_cleaner_event.timer_set) {
ngx_add_timer(&ngx_cleaner_event, 30000); //添加定时器事件
ngx_cleaner_event.timer_set = 1;
}3.3.3循环处理超时事件 nginx中有四个循环处理函数，分别运行于nginx不同的工作模式： ngx_single_process_cycle ngx_worker_process_cycle ngx_cache_manager_process_cycle ngx_worker_thread_cycle 以 ngx_single_process_cycle 为例：
代码语言：javascript复制void ngx_single_process_cycle(ngx_cycle_t *cycle)
{
......
for ( ;; ) {
ngx_log_debug0(NGX_LOG_DEBUG_EVENT, cycle->log, 0, "worker cycle");
ngx_process_events_and_timers(cycle);
......
}
}在for循环中中，调用了ngx_process_events_and_timers函数
代码语言：javascript复制void ngx_process_events_and_timers(ngx_cycle_t *cycle)
{
......
if (delta) {
ngx_event_expire_timers(); //调用超时触发函数
}
ngx_event_process_posted(cycle, &ngx_posted_events);
}PS：这一部分的介绍和代码取自 知乎「夜空」 我也没有在Nginx的源码中完整查找论证过，我看的nginx版本是1.14.2 ，后续可能会改动代码的部分引用和注释。
本篇文章引用了以下文章中的内容，
CSDN博主「mengfanteng」的文章 《AVL树，红黑树，B树，B 树，Trie树都分别应用在哪些现实场景中》 原文链接：https://blog.csdn.net/mtt_sky/article/details/51442452
知乎博主「夜空」的文章 《红黑树应用1-nginx timer》 原文链接：https://zhuanlan.zhihu.com/p/78042487
博客园博主 「唐稚骅」的文章 《Linux内核：sk_buff解析》 原文链接：https://www.cnblogs.com/tzh36/p/5424564.html
CSDN博主「繁华落尽梦一场」的原创文章 原文链接：https://blog.csdn.net/zhangqi_gsts/article/details/52461031
CSDN博主「Sunands」的原创文章 原文链接：https://blog.csdn.net/woaini2050/article/details/89639951
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/179448.html原文链接：https://javaforall.cn
