AVL -> T-trees

[Howard Chu <hyc@symas.com>]

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?
--
  -- Howard Chu
  CTO, Symas Corp.           http://www.symas.com
  Director, Highland Sun     http://highlandsun.com/hyc/
  Chief Architect, OpenLDAP  http://www.openldap.org/project/