red-black revision 0c27b3fe77ac1d5094ba3521e8142d9e7973133f
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserCopyright (C) 1999-2001, 2004, 2016 Internet Systems Consortium, Inc. ("ISC")
79159a86ddb51071055abd7ee08935bc65b9e7a9Scott MoserThis Source Code Form is subject to the terms of the Mozilla Public
79159a86ddb51071055abd7ee08935bc65b9e7a9Scott MoserLicense, v. 2.0. If a copy of the MPL was not distributed with this
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserfile, You can obtain one at http://mozilla.org/MPL/2.0/.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser$Id: red-black,v 1.9 2004/03/05 05:04:46 marka Exp $
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser Red-Black Tree Implementation Notes
79159a86ddb51071055abd7ee08935bc65b9e7a9Scott MoserBIND9's basic name storage mechanism is to use a modified form of
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserbalanced binary tree known as a red-black tree. Red-black trees
54e339f91785368a7825b2edaad04c2177a1a382Scott Moserprovide for relatively efficient storage, retrieval and removal of
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserdata while maintaining the lexical order of all stored keys, a
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosernecessary function for DNS security.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserA red-black tree is a balanced binary tree named for the coloring that
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moseris done in the tree, identifying each node as either red or black.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserThere are two simple rules for maintaining the color of nodes:
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser (1) A red node has only black children.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser (2) The path from the root to any leaf node always includes the
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser same number of black nodes.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserWhenever a key is added or removed, adjustments are made to adhere to
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserthose two rules. These adjustments are relatively cheap to make but
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosermaintain the balance of the tree, thus making for efficient addition,
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserlookup and deletion operations, all of which are O(log N). The color
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserof a node is not relevant to external users of the tree; it is needed
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moseronly to maintain the balance of the tree.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserFor more information on basic red-black trees, see _Introduction to
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserAlgorithms_, Cormen, Leiserson, and Rivest, MIT Press / McGraw Hill,
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser1990, ISBN 0-262-03141-8, chapter 14.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserIn BIND9, the red-black tree implementation uses DNS names as keys,
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserand can store arbitrary data with each key value. "name" and "key"
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserare used interchangably in this document.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserThe basic red-black tree algorithm is further adapted for use in BIND9
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserto incorporate the notion of hierarchy, creating a tree of red-black
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosertrees. Where there is more than one name with a common suffix, all
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosernames with that suffix are stored in their own red-black tree, with a
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserdown pointer from the suffix locating the subtree.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserFor example, consider storing the following names:
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserNo matter which order the keys were added, this would result in a tree
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserthat can be visualized as:
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserThis tree shows that when there is no key for a particular label, and
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserwhen there is only one known label for its immediate subordinate, then
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosermultiple labels can appear in a single node, such as at d.e.f and g.h.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserIt also demonstrates that there can be more nodes in the tree of trees
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserthan there are actual keys (which degrades the O(log N) performance
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosermarginally); the nodes at d.e.f and w.y do not represent keys.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserAs an aside, remember that when ordering DNS names, labels are
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserexamined from the right, therefore w.y sorts after x and before z.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserA split can occur not only on a regular label boundary, but also
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserbetween any two bits in an EDNS bitstring label. The common-suffix
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserrules will be applied to keep as many bits together as possible.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserIn the current implementation of the tree of trees, a node is
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserconsidered to "formally" exist only if it has data associated with
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserit. So if the above tree then had the key d.e.f added to it, the
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moseroperation would succeed rather than getting an "already exists"
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserAlong the same lines, if a key is added with a name which is a proper
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosersuperdomain of the name stored in an existing node, the operation will
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosersucceed by splitting the existing node into one node that is the key
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserand another node that is the remaining parts of the name. Adding e.f
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserto the above tree results in the top level red-black tree having a
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosernode named e.f where the current d.e.f is, and a down pointer from
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserd.e.f to a "tree" of a single node named d. The down pointer from d
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserwould be kept to the level which has x, w.y, and z.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserA similar split of d.e.f would occur if the name k.e.f were added.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserThe top level tree would have the node e.f with a down pointer to a
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserlevel that had both d and k, and d would continue to have its down
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserpointer to the x, w.y and z level.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserIt is guaranteed when splitting that external references to the node
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserthat is split will remain valid --- in the previous examples, anything
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserthat was pointing to the node that was d.e.f will still point to the
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosernode that is now just d.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserWhen deleting keys, nodes can be rejoined. If both of p.w.y.d.e.f and
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserq.w.y.d.e.f were removed from the example tree, the node named w.y
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserwould become o.w.y. Unlike splitting, it is _not_ guaranteed that
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserexternal references remain consistent; sometimes they will, sometimes
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserthey won't. Also, note that deletion is not perfectly symmetric with
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moseraddition. If you "undo" the last addition with a deletion of the same
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserkey then the tree of trees is not guaranteed to have exactly the same
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserstructure as it had prior to the addition. Sometimes, but not always.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserRejoining does not happen if it would violate any of the rules that
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosercause a split. o would not be rejoined with w.y if w.y had data
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserassociated with the key; o would remain as a single node on its own
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserlevel. This emphasizes the rule that a node is considered to formally
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserexist only if data is associated with it, because even if w.y.d.e.f
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserhad been explicitly added as a key but with no data, then o would
79159a86ddb51071055abd7ee08935bc65b9e7a9Scott Moserstill be merged with the w.y node when p and q were deleted.
79159a86ddb51071055abd7ee08935bc65b9e7a9Scott MoserSearching for a node generally returns one of three possible results:
79159a86ddb51071055abd7ee08935bc65b9e7a9Scott Mosereither the key is found, a superdomain (partial match) of the key is
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserfound, or no part of the key is found. The first and last are rather
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserobvious, and the second result basically means that a hierarchically
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserenclosing name is found; e.g, searching for bb.rc.vix.com turned up
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserrc.vix.com, but not the full name.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserNo locking is done within the RBT library. @@@
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserWhen a partial match is made, level_matches is set while the chain
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserpoints to the partial match node that was found. Then the chain is
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moseradjusted to point to the DNSSEC predecessor node, which might not even
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserbe under the same top level domain as the name that was searched for.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserFor example, consider a database that had only the names vix.com and
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserisc.org. A search for uu.net would leave the chain pointed to
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moservix.com, the DNSSEC predecessor. Though this might first appear to
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosercause level_matches to be bogus because the chain has been unwound and
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosersent down another path, note that the partial match node will always
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserbe in the chain of the predecessor, too --- and often the partial
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Mosermatch node will be the predecessor itself. In the vix.com/isc.org
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserexample, the search for uu.net finds a partial match at ".", which is
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserof course also in the path to the vix.com predecessor. A search for
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserwww.isc.org would find that isc.org is both the partial match and the
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserEXTERNAL PROGRAMMATIC DETAILS
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserThis section details the functions used to interact with the BIND9
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moserred-black tree library, or RBT for short.
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserA source file that will be using RBT will usually need to include
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott Moser<dns/rbt.h>. This header file automatically includes <isc/result.h),
65d8ae9c4a66f5ca85289c02dc06d63261c84619Scott MoserThe rbt.h file has more complete descriptions of each of the functions