Red black tree

Red black tree library – nginx.

See wikipedia link on rb tree description.  Red black tree provides improvement over binary trees that makes it faster to search and also faster to insert/delete nodes.  It applies four principles as described in wiki link to balance the tree after every addition and deletion.  These principles make it search performance predictable.  These rebalancing principles are not expensive and hence insert and delete operations are also faster.

Nginx web server uses rb trees to cache SSL sessions across threads, to store the open file cache entries and for many other purposes.

Nginx rbtree implementation does not include all  binary tree operations. It leaves the binary tree insertion to the applications.  It does rebalancing of the tree and also it provides delete operation API function. It lets the application to do the ‘search’ on binary tree.  Note that search operation on rbtree is same as search operation on binary tree.

Though implementation of ‘rbtree’ implementation looks complicated (mainly if you have not gone through the algorithm before),   its usage by application is simple.  Applications need to define the root and put the node in the structure elements which it wants to put in the rbtree.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s