On Mon, Jun 2, 2008 at 12:49 PM, Howard Chu &lt;<a href="mailto:hyc@symas.com">hyc@symas.com</a>&gt; wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
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.<br>

<br>
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?<br><font color="#888888">
</font></blockquote></div><br>T-trees are great for cache backing.<br><br>Incidentally, we&#39;ve thought about using T-trees as well for an entry cache over at Apache Directory:  Howard you probably remember some of those threads.&nbsp; I think we were initially considering a splay tree but I think that&#39;s pretty insane especially since it will be splaying on lookups.&nbsp; It would be a learning experience for us to see what your conclusions are with T-trees.&nbsp;&nbsp; <br>
<br>Regards,<br>Alex<br><br>