On Mon, Jun 2, 2008 at 12:49 PM, Howard Chu <[EMAIL PROTECTED]> wrote:
> Taking a cue from our MySQL friends - MySQL uses T-trees for their > in-memory structures. These are balanced trees, like AVL trees. But instead > of just one data item per tree node, they have N items per node. (Presumably > N is a compile-time constant.) The advantage to using T-trees is that > inserts and deletes have less impact on the overall tree, thus minimizing > the need for rebalancing. > > I would expect that they perform about as well as AVL trees for lookups. > Anyone interested in experimenting here and reporting on the relative > performance? > T-trees are great for cache backing. Incidentally, we've thought about using T-trees as well for an entry cache over at Apache Directory: Howard you probably remember some of those threads. I think we were initially considering a splay tree but I think that's pretty insane especially since it will be splaying on lookups. It would be a learning experience for us to see what your conclusions are with T-trees. Regards, Alex
