[bind10-dev] new in-memory zone data design

[Francis Dupont]

> > => according to experts (i.e., guys D. Knuth nods to when he sees them)
> > the red-black tree is the best (known) data structure for this kind of
> > things, in particular its dynamic performance is pretty good. So I
> > support Junmei in his choice!
> 
> Well, that's the point. Dynamic performance means it is fast with updates.

=> yes, in the case of the AFTR most connections had short lifetimes
so it was critical to get fast insertions/deletions. And for long
term connections I used a dynamically sized hash table as a cache
(I can look at the code and the front comment: I don't believe there
are many things which can be easily improved, in fact the AFTR code
is clearly over-engineered but to use it for algo experiments was
a part of the design...).

> However, we have much more lookups than updates. AVL trees are
> somewhat slower, but they are better balanced, so they trade the
> update speed to get better lookup speed. So I think AVL tree might
> be better for that reason.

=> yes, wikipedia gives for the length 1.44*log(n+2) - 1 vs
2*log(n+1) with 2 for the basis of log(). As it is C++ code
it should be possible to test one day AVLs...

> What I fear is, somebody decided to use RB tree because it is
>  generally the good choice (without really thinking about specific
>  needs) and then everybody uses them because everybody uses them. We
>  never had a discussion about what tree we want to use.

=> yes, perhaps we are a bit RB addict but on the other hand we never
got bad results with RB too. Perhaps we can agree to make it modular
(in a real programming language it will be a functor) and to start
with RB trees?

Regards

Francis Dupont <fdupont at isc.org>