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

[Mukund Sivaraman]

On Sat, Mar 02, 2013 at 10:58:19PM +0530, Mukund Sivaraman wrote:
> 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.

I've pushed another branch trac2838_alt that uses a separate node member
for storing the balance factor (instead of overloading flags). It
increases the size of the node by 1 byte + any alignment. The related
methods are also inlined aggressively now. It should provide some
improvement in performance, but time complexity will be the same.

The reason this was not done in trac2838 is that it increases the
storage of a DomainTree node, which is likely to get rejected. But
here's the branch anyway. :)

		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/20130303/526c29bc/attachment.bin>