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

[Francis Dupont]

> 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.

=> IMHO it was the case: RB tree is known to have a very good
dynamic performance, and the interaction with the virtual memory
system is important in a large data structure.

Regards

Francis Dupont <fdupont at isc.org>

PS: there was the second reason for my choice of the RB tree in
the AFTR code (where BTW the expected work load stressed this point
more than for a DNS auth server).