[bind10-dev] Using AVL tree instead of red-black tree in DomainTree

[Mukund Sivaraman]

Hi all

I propose we use an AVL tree instead of a red-black tree as the core
data structure of the DomainTree.

Aside from the better lookup performance that AVL trees have over
red-black trees (at the expense of slower insert time), an
implementation to delete nodes from the DomainTree when it is a
red-black tree is going to be hairy because we no longer have a
NULL_NODE and use NULL values instead.

There are many color combination cases that we will need to handle when
deleting from a red-black tree. Each of these will require NULL testing
before color testing and it will make our developers lose hair each time
they have to look at this code. AVL trees are easier to understand,
maintain code for, and also provide better lookup performance.

We should implement this before #2750 (support DomainTree::delete()).

I have filed ticket #2838 for this task and have pushed an
implementation to the trac2838 branch.  This bug is to test performance
also, when switching from red-black to AVL trees.

Comments are welcome. Please test query and zone loading performance of
this branch (AVL implementation) vs. the point where it was branched off
master (red-black implementation), if you have a BIND 10 benchmark
environment.

		Mukund
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 801 bytes
Desc: not available
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20130302/914fcbe8/attachment.bin>