nginx 데이터 구조 1 - ngx_int_t 및 ngx_rbtree_t

./src/core 하위 디렉토리에 있는 71 소스 파일을 보면 시작하기가 약간 어렵습니다. main 함수가 포함된 nginx.c 파일을 검색해 보니 nginx가 자체 캡슐화된 데이터 구조를 많이 사용한다는 사실을 발견했습니다. 이것이 무엇인지 모르겠습니다. 어떤 종류의 데이터 구조가 주 함수의 작업 의미를 이해하기 어렵게 만듭니다. 그래서 우리는 겉으로는 기본적으로 보이는 데이터 구조를 선택하고 연구하기 시작했습니다. nginx의 모든 데이터 구조를 구성하는 것은 ngx_core.h 파일입니다. 먼저 ngx_config.h가 포함되어 있으며 ngx_config.h에서 세 가지 유형 정의를 찾았습니다.

1.ngx_int_t, ngx_uint_t, ngx_flag_t

nginx.c에서 처음으로 보이는 낯선 데이터 유형은 ngx_int_t이며, 해당 정의는 nginx_config.h에 있습니다.

typedef intptr_t        ngx_int_t;
typedef uintptr_t       ngx_uint_t;
typedef intptr_t        ngx_flag_t;

단서를 따라가며 세 가지 데이터 유형의 정의를 찾았습니다. 학부 c 입문 강의에는 intptr_t/uintptr_t 입문 강의가 없습니다. c 해당 정의는 stdint.h 헤더 파일에서 찾을 수 있습니다.

/* Types for `void *' pointers.  */
#if __WORDSIZE == 64
# ifndef __intptr_t_defined
typedef long int               intptr_t;
#  define __intptr_t_defined
# endif
typedef unsigned long int    uintptr_t;
#else
# ifndef __intptr_t_defined
typedef int                    intptr_t;
#  define __intptr_t_defined
# endif
typedef unsigned int        uintptr_t;
#endif

먼저 이 두 유형은 “void *”의 포인터 유형이지만 문자 그대로 intptr_t 및 uintptr_t는 실제로 정수 포인터 유형과 부호 없는 정수 포인터 유형이지만 사람들은 왜 정수를 사용하는지 혼란스러워합니다. 포인터 유형을 정수로 사용하는 것은 어떻습니까? ? 먼저 재생하고 마지막에 매크로를 살펴보세요. 기계는 64비트이고, intptr_t의 단어 길이는 long int, uintptr_t는 unsigned long int입니다. 이는 내 컴퓨터의 비트 컴파일러는 sizeof()이고 잠시 후 8 bytes64 비트, 64 비트 단어 길이intptr_t 미만 int, uintptr_t는 unsigned int이고, 표에서는 32 비트 컴파일러에서 int 및 unsigned는 4입니다. 바이트, 16비트 컴파일러는 2바이트입니다. 그러면 intptr_t/uintptr_t는 플랫폼 단어 길이가 변경됨에 따라 그에 따라 변경되는 정수 유형이어야 합니다. 이해를 해보니 "Linux 커널 소스 코드 심층 분석"의 설명은 시스템 커널이 메모리를 동작시킬 때 메모리를 큰 배열로 취급하고, 포인터는 배열 인덱스/입니다. 커널 프로그래머는 이 특수 정수를 사용하여 메모리 주소 값을 허용합니다. 포인터를 사용하는 것과 비교하여 메모리 운영은 더 직관적이고 실수할 가능성이 적습니다. nginx에서는 플랫폼 관련 int, unsigned int 변수만 입력하세요.

2.ngx_rbtree_t

2.1. >

은퇴한 팀원으로

ACM

대회에 많이 참가했습니다. 레드-블랙 트리와 같은 유명한 데이터 구조는 상대적으로 민감합니다. 레드-블랙 트리는 특별한 제약 조건을 적용한 균형 잡힌 이진 검색 트리 구현입니다. 데이터 구조 수업을 공부한 학생들은 교과서에 나오는 최초의 자체 균형 이진 트리

AVL

트리에서는 하위 트리의 높이 차이가 2 루트 노드에서 모든 리프 노드까지의 거리가 기본적으로 동일(균형)하다는 특성을 얻습니다. 레드-블랙 트리는 엄격한 균형을 추구하지 않고 5 제약을 통해 기본 균형을 달성합니다.

① 노드는 Red입니다. 또는 검정;

②루트 노드는 검정색입니다. ④빨간색 노드의 하위 노드는 모두 검정색입니다. 모든 노드에서 리프 노드까지의 단순 경로에 있는 블랙 노드의 수는 동일합니다.

AVL 트리의 루트에서 리프 노드까지의 최장 거리와 최단 거리의 비율은 2를 초과하지 않습니다. 레드-블랙 트리의 제약 조건도 이러한 특성을 보장합니다(가장 긴 경로는 빨간색과 검은색이고, 최단 경로는 모두 검은색입니다. 이 경우 가장 긴 경로는 최단 경로의 정확히 두 배입니다).

균형 이진 검색 트리를 구현한 것이므로 레드-블랙 트리는 자연스럽게 내부적으로 정렬되며 AVL 트리와 마찬가지로 O(log2n) 시간 복잡도 검색, 삽입 및 삭제를 지원합니다.

    相比AVL树，红黑可以保证在每次插入或删除操作之后的重平衡过程中，全树拓扑结构的更新仅涉及常数个结点。尽管最坏情况下需对O(log2n)个结点重染色，但就分摊意义（平均效率）而言，仅为O(1)个。但是因为没有严格约束树的平衡特性，红黑树的左右子树高度差比AVL树要大。

2.2、ngx_rbtree.h

    机会难得，我们就把nginx的源码作为素材来深入了解一下红黑树的实现。首先是结点的结构：

typedef ngx_uint_t  ngx_rbtree_key_t;
typedef ngx_int_t   ngx_rbtree_key_int_t;


typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;

struct ngx_rbtree_node_s {
    ngx_rbtree_key_t       key;//平台相关的无符号整型关键字
    ngx_rbtree_node_t     *left;//左子结点指针
    ngx_rbtree_node_t     *right;//<span style="font-family:宋体;">右</span>子结点指针
    ngx_rbtree_node_t     *parent;//父结点指针
    u_char                 color;//结点颜色
    u_char                 data;//结点数据
};

    然后是红黑树的结构定义：

typedef struct ngx_rbtree_s  ngx_rbtree_t;	//“_s”是结构体“_t”是类型
//下面是一个函数指针变量类型的定义，是红黑树插入函数的指针
//参数有树根结点、插入结点和哨兵结点的指针
typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);

struct ngx_rbtree_s {
    ngx_rbtree_node_t     *root;	//根节点指针
    ngx_rbtree_node_t     *sentinel;	//哨兵结点指针
    ngx_rbtree_insert_pt   insert;	//插入函数指针
};

    将函数指针变量作为结构体成员变量以达成可以把结构体当做类来使用（既有成员变量又有成员方法）的效果，这种手法在nginx的源码中相当普遍。关于函数，nginx还有一种更神奇的手段——宏：

#define ngx_rbtree_init(tree, s, i)                                         \
    ngx_rbtree_sentinel_init(s);                                               \
    (tree)->root = s;                                                                  \
    (tree)->sentinel = s;                                                            \
    (tree)->insert = i//这里insert函数指针的赋值实现了多态

    借助宏来达成内联函数的效果（函数实现如果比较简单，就干脆把实现过程整个搬到类中），令人费解的是，C不是没有内联关键字，甚至同一个头文件中就有一个内联函数的定义。研究内联函数之前，下面还有几个宏要看一看：

#define ngx_rbt_red(node)               ((node)->color = 1)
#define ngx_rbt_black(node)             ((node)->color = 0)
#define ngx_rbt_is_red(node)            ((node)->color)
#define ngx_rbt_is_black(node)          (!ngx_rbt_is_red(node))
#define ngx_rbt_copy_color(n1, n2)      (n1->color = n2->color) 

/* a sentinel must be black */
#define ngx_rbtree_sentinel_init(node)  ngx_rbt_black(node)

    nginx源码中的变量都很容易看懂以至于我们不怎么需要查资料或找注释。color置1染红置0染黑，color为1则结点为红色，不为红色的则为黑色，复制结点颜色即复制color值，哨兵结点一定要染成黑色。

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;
}

    ngx_inline是一个宏，实际值就是关键字inline。这个内联函数非常好懂，目的看起来是寻找以任意结点为根结点的子树中结点值最小的结点。实现方法是找到红黑树子树最边缘的左子结点。那么我们有理由猜测，哨兵结点是空结点或边缘标识。

2.3、红黑树的结点插入

    接下来我们来深入ngx_rbtree.c看看nginx如何实现几个关键的红黑树方法。

void
ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
    //根结点指针的指针，或者根结点指针数组，会有多个根结点吗，令人费解
    //临时结点指针
    //哨兵结点指针，推测哨兵在每次查询时可能都不一样，也许指待插位置
    //变量不分行，我写注释都很不方便
    ngx_rbtree_node_t  **root, *temp, *sentinel;
 
    /* a binary tree insert */
 
    root = (ngx_rbtree_node_t **) &tree->root;//树根指针的指针赋给了root
    sentinel = tree->sentinel;//哨兵指针赋给了哨兵指针
 
    if (*root == sentinel) {//特判，如果根是哨兵，即树是空的
        node->parent = NULL;//新插入的结点变成了根
        node->left = sentinel;//新结点的左子结点是哨兵
        node->right = sentinel;//新结点的右子结点也是哨兵
        ngx_rbt_black(node);//新根染黑
        *root = node;//确认新结点为新根
 
        return;//插入结束
    }
 
    //树初始化时给了insert指针一个函数地址
    //查看前面的宏ngx_rbtree_init(tree, s, i)
    //发现只是把指定结点染黑，同时赋为根和哨兵，给insert指针指定一个函数
    //ngx_rbtree.c中有两个参数表符合的可选函数：插入值、插入计时器值
    //稍后来看两种插入分别如何实现又有什么区别
    tree->insert(*root, node, sentinel);
 
    /* re-balance tree */
    //如果新结点不是根且其父结点是红的，循环
    while (node != *root && ngx_rbt_is_red(node->parent)) {
        //如果父结点是左子结点，获得父结点的右兄弟
        if (node->parent == node->parent->parent->left) {
            temp = node->parent->parent->right;
            //如果父结点的右兄弟是红的
            if (ngx_rbt_is_red(temp)) {
                ngx_rbt_black(node->parent);//父结点染黑
                ngx_rbt_black(temp);//父结点的右兄弟染黑
                ngx_rbt_red(node->parent->parent);//父结点的父结点染红
                node = node->parent->parent;//父结点的父结点成为当前结点
 
            } else {//如果父结点的右兄弟是黑的
                if (node == node->parent->right) {//如果新结点是右子结点
                    node = node->parent;//父结点成为新node
                    ngx_rbtree_left_rotate(root, sentinel, node);//node左旋
 
                }
 
                ngx_rbt_black(node->parent);//node的父结点染黑
                //node的父结点的父结点染红
                ngx_rbt_red(node->parent->parent);
                ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);//node的父结点的父结点右旋
            }
 
        } else {//如果父结点是右子结点，获得父结点的左兄弟
            temp = node->parent->parent->left;
            //如果父结点的左兄弟是红的
            if (ngx_rbt_is_red(temp)) {
                ngx_rbt_black(node->parent);//父结点染黑
                ngx_rbt_black(temp);//父结点的左兄弟染黑
                ngx_rbt_red(node->parent->parent);//父结点的父结点染红
                node = node->parent->parent;
 
            } else {//如果父结点的左兄弟是黑的
                if (node == node->parent->left) {//如果新结点是左子结点
                    node = node->parent;//父结点成为当前结点
                    ngx_rbtree_right_rotate(root, sentinel, node);
                    //当前结点右旋
                }
 
                ngx_rbt_black(node->parent);//当前结点染黑
                //当前结点父结点的父结点染红
                ngx_rbt_red(node->parent->parent);
                ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);//当前结点的父结点的父结点左旋
            }
        }
    }
 
    ngx_rbt_black(*root);//根结点染黑
}

    然后是对应ngx_rbtree_insert_pt指针的基础的结点插入函数：

void
ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
    ngx_rbtree_node_t *sentinel)
{
    ngx_rbtree_node_t  **p;//虽然无关紧要，但两层指针令人费解
 
    for ( ;; ) {//无条件循环或者说死循环，等同于while(1)但节省了一个字符
 
        p = (node->key < temp->key) ? &temp->left : &temp->right;
 
        if (*p == sentinel) {//在二叉树中查找新结点合适的叶结点位置
            break;
        }
 
        temp = *p;
    }
    //令新结点占据合适的哨兵位置成为新的叶结点，染红，产生新哨兵
    *p = node;
    node->parent = temp;
    node->left = sentinel;
    node->right = sentinel;
    ngx_rbt_red(node);
}

    ngx_rbtree_insert_timer_value函数跟ngx_rbtree_insert_value函数唯一区别就是判断大小时，采用了两个值相减，避免溢出。

    以上是插入结点涉及的函数，老实说我不太喜欢这么长的函数实现，换我自己写肯定分块了。分支操作太多，看代码逻辑已经乱了，我们需要画几个图。首先，如果树为空：

    如果树中只有一个根结点：

    如果C>A：

    如果C，C染红，B染黑A染红，A右旋。右旋函数如下：

static ngx_inline void
ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
    ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  *temp;
 
    temp = node->left;
    node->left = temp->right;//左子结点指向原左子结点的右结点
 
    if (temp->right != sentinel) {//如果左子结点的右结点不为哨兵
        temp->right->parent = node;//左子结点的右子结点挂在右旋结点上
    }
 
    temp->parent = node->parent;//左子结点挂在右旋结点的父结点上
 
    if (node == *root) {//如果右旋结点为根节点
        *root = temp;//根节点赋为左子结点
 
    } else if (node == node->parent->right) {//如果右旋结点为右子结点
        node->parent->right = temp;//左子结点挂父结点右边
 
    } else {//否则左子结点挂父结点左边
        node->parent->left = temp;
    }
 
    temp->right = node;//右旋结点挂左子结点右边
    node->parent = temp;
}
<p>    显然<span>B</span><span>将成为新的根，左</span><span>C</span><span>右</span><span>A</span><span>：</span></p>
<img src="http://image.codes51.com/Article/image/20150806/20150806084733_7641.png" alt=""><br><p>    如果<span>B<C<A</span><span>，会先做一次左旋再做一次右旋，其实除开染色过程，我觉得这跟</span><span>AVL</span><span>树的插入过程没有什么区别：</span></p><img src="http://image.codes51.com/Article/image/20150806/20150806084733_8423.png" alt=""><p>    其他的插入情景要么与以上几个对称，要么发生在树的其他子树中，实际过程完全一样。LL<span>型右旋，</span><span>RR</span><span>型左旋，</span><span>LR</span><span>型先右旋后左旋，</span><span>RL</span><span>型先左旋后右旋。</span>与<span>AVL</span><span>树不同的是，插入结点时红黑树左旋或右旋的判定条件明确为附近一两个结点的颜色，其他过程没有任何区别。</span></p><p>2.4、红黑树的结点删除</p><p>    据说红黑树和<span>AVL</span><span>树的区别主要体现在删除节点时，我们就来看一看。</span>我刚说什么来着，删除结点的函数体更长了，足足<span>165</span><span>行，我决定分段研究，</span>先看第一部分：</p><pre name="code">if (node->left == sentinel) {//如果左子结点是哨兵或左右子结点都是哨兵
    temp = node->right;//获得右子结点，后面让它接替node位置
    subst = node;//node赋给subst
 
} else if (node->right == sentinel) {//如果右子结点是哨兵
    temp = node->left;//获得左子结点，后面让它接替node位置
    subst = node;//node赋给subst
 
} else {//如果左右子结点都不是哨兵
    subst = ngx_rbtree_min(node->right, sentinel);//获得右子树中最小的结点
 
    if (subst->left != sentinel) {//如果右子树的最小结点的左子结点不是哨兵
        temp = subst->left;//获得右子树的最小结点的左子结点
    } else {//否则获得右子树最小结点的右子结点
        temp = subst->right;
    }//看起来subst将被从原位置删掉然后接替node的位置
}
<p>    下面我们来看看<span>temp</span><span>和</span><span>subst</span><span>要干什么用：</span></p>
<pre name="code">if (subst == *root) {//如果subst是根
    *root = temp;//temp接替根
    ngx_rbt_black(temp);//染黑temp
 
    /* DEBUG stuff */
    node->left = NULL;//清空了待删结点
    node->right = NULL;
    node->parent = NULL;
    node->key = 0;
 
    return;
}
 
red = ngx_rbt_is_red(subst);//获得subst是否是红色
 
if (subst == subst->parent->left) {//如果subst是左子结点
    subst->parent->left = temp;//把接替结点挂到subst位置
 
} else {//如果subst是右子结点
    subst->parent->right = temp;//把接替结点挂到subst位置
}

    下一段：

if (subst == node) {//如果subst是待删结点
    temp->parent = subst->parent;//接替结点直接接替，删除完成
 
} else {//如果subst不是待删结点
     if (subst->parent == node) {//如果subst的父结点就是待删结点
        temp->parent = subst;//接替结点挂在subst上
     } else {//如果待删结点比subst的父结点更高
        temp->parent = subst->parent;//把接替结点挂在subst的父结点上
    }
    //subst接替待删结点node的位置，复制待删结点跟周围结点的关系
    subst->left = node->left;
    subst->right = node->right;
    subst->parent = node->parent;
    ngx_rbt_copy_color(subst, node);//复制颜色
 
    if (node == *root) {//如果待删结点是根
        *root = subst;//subst接替根
    } else {//如果待删结点不是根，subst接替它
        if (node == node->parent->left) {
            node->parent->left = subst;
        } else {
            node->parent->right = subst;
        }
    }
 
    if (subst->left != sentinel) {//如果subst左子结点不是哨兵
        subst->left->parent = subst;//subst的左子结点放弃node，挂上来
    }
 
    if (subst->right != sentinel) {//如果subst右子结点不是哨兵
        subst->right->parent = subst;//subst右子结点放弃node，挂上来
    }
}
//清空待删结点node
/* DEBUG stuff */
node->left = NULL;
node->right = NULL;
node->parent = NULL;
node->key = 0;
//如果subst是红色，红黑树约束依然被遵守，删除工作就可以结束了
if (red) {
    return;
}

    看起来结点的删除过程已经顺利完成了，但是如果subst是黑色，我们需要修复红黑树的约束。下面这一段代码的主角是接替subst位置的temp结点：

//当subst的接替结点不是根且为黑色，循环
while (temp != *root && ngx_rbt_is_black(temp)) {
        if (temp == temp->parent->left) {//如果temp是左子结点
            w = temp->parent->right;//获得其右兄弟
 
            if (ngx_rbt_is_red(w)) {//如果temp的右兄弟是红色
                ngx_rbt_black(w);//染黑temp的右兄弟
                ngx_rbt_red(temp->parent);//染红temp的父结点
                //temp的父结点左旋
                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
                w = temp->parent->right;//获得temp的新右兄弟
            }
            //如果temp右兄弟的左右子结点都是黑的
            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
                ngx_rbt_red(w);//染红temp的右兄弟
                temp = temp->parent;//获得temp的父结点为新temp
 
            } else {//如果temp右兄弟的子结点不全为黑
                if (ngx_rbt_is_black(w->right)) {//如果其右子结点是黑色
                    ngx_rbt_black(w->left);//染黑左子结点
                    ngx_rbt_red(w);//染红temp的右兄弟
                    ngx_rbtree_right_rotate(root, sentinel, w);//右兄弟右旋
                    w = temp->parent->right;//获得temp的新右兄弟
                }
                //temp右兄弟复制temp父结点颜色
                ngx_rbt_copy_color(w, temp->parent);
                ngx_rbt_black(temp->parent);//染黑temp父结点
                ngx_rbt_black(w->right);//染黑temp右兄弟的右子结点
                //temp父结点左旋
                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
                temp = *root;//获得根
            }
 
        } else {//如果temp是右子结点，做对称的事
            w = temp->parent->left;
 
            if (ngx_rbt_is_red(w)) {
                ngx_rbt_black(w);
                ngx_rbt_red(temp->parent);
                ngx_rbtree_right_rotate(root, sentinel, temp->parent);
                w = temp->parent->left;
            }
 
            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
                ngx_rbt_red(w);
                temp = temp->parent;
 
            } else {
                if (ngx_rbt_is_black(w->left)) {
                    ngx_rbt_black(w->right);
                    ngx_rbt_red(w);
                    ngx_rbtree_left_rotate(root, sentinel, w);
                    w = temp->parent->left;
                }
 
                ngx_rbt_copy_color(w, temp->parent);
                ngx_rbt_black(temp->parent);
                ngx_rbt_black(w->left);
                ngx_rbtree_right_rotate(root, sentinel, temp->parent);
                temp = *root;
            }
        }
    }

ngx_rbt_black(temp);//染黑当前temp

    跟插入结点时一样乱，我们梳理一下。

    首先忽略红黑树的约束进行删除：

    ①如果删除的是一个叶结点，即没有后继或后继全为哨兵的结点，直接删除即可；

    ②如果只有一个后继，让其替换待删除结点即可；

    ③如果有两个后继，需要从树的边缘选择一个结点，有两种等价的选择，待删结点左子树的最大结点和右子树的最小结点，nginx选择的是后者，以这个结点的键与值（key与value/data）替换待删结点的键与值，然后删除这个替身。

    不论是①、②情景中的待删结点还是③情景中替身，在源码中都是subst。下面要围绕着它来进行讨论。

    以上是不考虑红黑树平衡性的纯拓扑结构变动。下面要考虑是否调整树的拓扑结构使树重新平衡，是否调整结点的颜色使树重新符合红黑树的约束条件。我们知道红黑树有一条关键约束是任意结点到其子树中叶结点的简单路径中黑色结点数相同。那么如果subst是一个红色结点，我们不需要对红黑树做任何调整，它仍是一棵红黑树；如果subst是黑色的，所有经过subst的简单路径上都会少一个黑色结点数，所以需要进行调整。

    下面来根据不同情景分情况讨论，因为二叉树的情景左右颠倒时调整方式也可以左右颠倒，我们只讨论subst是左子结点的情况。设刚接替subst的temp为X，X的新右兄弟为W。从经过简化的源码来看，关于结点颜色的变化很令人费解，我们不妨先来看一看：

    ①W为红色：将W染黑，将X与W的父结点X->parent染红，X->parent左旋，W重设为X的新右兄弟，然后转入情景①、②或③；

    ②W为黑色，W两个后继都是黑色：将W染红，X重设为X->parent；

    ③W为黑色，W右子结点为黑色：将W左子结点染黑，将W染红，W右旋，W重设为X的新右兄弟，然后将X->parent的颜色赋给W，将X->parent染黑，X->parent左旋，根赋给temp；

    ④W为黑色，W右子结点为红色：将W左子结点染黑，将W染红，W右旋，W重设为X的新右兄弟，然后将X->parent的颜色赋给W，将X->parent染黑，将W右子结点染黑，X->parent左旋，根赋给temp。

    最后还要把temp染黑。我们可以看到情景①中进行了一次左旋，情景②只进行了染色，情景③、④都进行了一次右旋和一次左旋。情景①处理结束时一定还要转入别的情景，情景②、③、④的出现则标志着本次调整的结束。那么，红黑树删除结点后的调整过程中，依情景①循环出现的次数，调整过程中旋转的最多见的次数将是1次、2次、3次，再往上次数越多越罕见（依情景①循环出现的次数），最多旋转次数将可能到达树高即log2n次。生产环境中，删除结点后平均每次调整中旋转的次数就像分析源码之前提到的，将是常数规模的。

다음으로는 레드-블랙 트리의 데이터 구조를 보다 자세하고 직관적으로 이해하기 위해 단계별 혁신 버전으로 레드-블랙 트리를 다시 작성할 계획입니다. 다시 작성하기 전에 nginx의 레드-블랙에 있는 모든 리프 노드가 센티넬이라는 점을 이해해야 합니다. 이는 레드-블랙 트리를 조정할 때 레드-블랙 트리의 최적화를 달성합니다. 올블랙 하위 노드 레이어를 추가하면 레드-블랙 트리에서 실제로 값을 갖는 하위 트리에 레드 노드가 나타날 수 있습니다. 증명하지는 못했지만 이 상수 스케일은 노드를 삭제할 때 회전 수를 늘리고 새 노드를 삽입할 때 조정 확률을 촉진하며(레드 노드 아래에 새 노드를 삽입할 확률을 높임) 삽입 확률도 높입니다. 빨간색 노드 아래의 새 노드. 회전은 레드-블랙 트리 하위 트리의 높이를 압축하고 쿼리 효율성을 향상시킵니다.

레드-블랙 트리를 단순성에서 개선으로 다시 작성하는 과정에서 nginx를 사용하여 레드-블랙 트리를 더 적은 것에서 더 많은 것으로 최적화하거나 나만의 최적화를 추가하는 것을 고려해 보겠습니다.

저작권 안내: 이 글은 해당 블로거의 원본 글이므로 블로거의 허락 없이 복제할 수 없습니다.

위는 관련 내용을 포함하여 nginx 데이터 구조 1 - ngx_int_t 및 ngx_rbtree_t를 소개합니다. PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.