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

[Mukund Sivaraman]

On Wed, Mar 06, 2013 at 10:58:03AM +0100, Michal 'vorner' Vaner wrote:
> I have another idea why it might be and that is memory layout. If it happened by
> accident that the RB tree often had two nodes accessed soon after each other in
> the same memory line, while the AVL doesn't, then it could make the RB faster
> even if the AVL was shallower.

In the main AVL branch, the size of the node is the same. We use
different bits in the flags_ member variable, but otherwise, data size
is unchanged. Text segment changes, but nothing in the query path is
different from the RB tree as both are BSTs and the find() operation is
identical.

		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/20130306/97476144/attachment.bin>