Understanding ngx_rbtree_t Red‑Black Tree in Nginx: Theory, Properties, and Implementation

1. ngx_rbtree_t Red‑Black Tree

ngx_rbtree_t is a highly efficient self‑balancing binary search tree employed by core Nginx modules (e.g., timer management, file cache) to achieve fast lookup, insertion, deletion, range queries, and traversal.

2. Origin and Characteristics of Red‑Black Trees

2.1 Introduction

Standard textbook definition: each node is either red or black; the root is black; all leaf (null) nodes are black; a red node’s children are black; every path from any node to its descendant leaves contains the same number of black nodes.

These formal rules alone do not explain the tree’s origin; the red‑black tree is derived from the 2‑3 tree, which offers an equivalent representation.

2.2 What Is a 2‑3 Tree?

A 2‑3 tree satisfies the binary‑search‑tree property and allows each node to store one element (2‑node) or two elements (3‑node). The following images illustrate the node types:

In a 2‑3 tree, a 3‑node is represented by two adjacent keys (b, c) that share a parent relationship.

2.3 2‑3 Tree Is Absolutely Balanced

All root‑to‑leaf paths contain the same number of nodes, guaranteeing perfect balance. The article demonstrates node insertion step‑by‑step (adding 42, 37, 12, 18, 6, 11, 5) with diagrams showing how temporary four‑node structures are split to maintain balance.

2.4 Equivalence Between Red‑Black Trees and 2‑3 Trees

By storing a single element per node and representing a 3‑node with a red left‑leaning child, a 2‑3 tree can be mapped directly to a left‑leaning red‑black tree. The red edge indicates the extra element of a 3‑node.

2.5 Basic Properties and Complexity Analysis

The five classic red‑black properties follow directly from the 2‑3 tree equivalence, guaranteeing a maximum height of 2·log₂N and O(log N) time for search, insertion, and deletion.

2.6 Recoloring and Rotations

Insertion or deletion may violate properties 4 or 5, requiring adjustments via rotations (left, right) and color flips. The article illustrates each operation with diagrams.

3. ngx_rbtree_t Source Code Analysis

3.1 Nginx Red‑Black Tree Structures

The structural diagram of ngx_rbtree_node_t and related types is shown below:

3.2 Inserting a New Node

Insertion consists of three steps: (1) locate the position using standard BST insertion, (2) create the node and color it red, (3) fix violations of property 4 by recoloring and rotating. Three cases are considered depending on the colors of the parent, uncle, and grandparent.

3.3 Deleting a Node

Deletion follows the classic BST removal (leaf, single‑child, or two‑child cases) and then restores red‑black properties. If the removed node is black, up to four cases are handled, involving recoloring, sibling rotations, and possibly propagating the fix upward.

4. Conclusion

The article has presented the theoretical foundation of red‑black trees, their equivalence to 2‑3 (and 2‑3‑4) trees, and detailed the insertion and deletion algorithms as implemented in Nginx’s ngx_rbtree_t . Understanding these mechanisms helps developers work with Nginx internals and other systems that rely on balanced binary search trees.