Re: AVL -> T-trees

[Howard Chu <hyc@symas.com>]

Gavin Henry wrote:
> <quote who="Howard Chu">
> > 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?
>
> I wonder what PostgreSQL does, as it's much much faster than MySQL.

Faster at what? MySQL, like OpenLDAP, has a dozen or so backends to choose 
from. In what context does the above statement mean anything? If you're 
talking about transactions, disk I/Os, different database backend libraries, 
etc., that's not interesting here. I was specifically talking about in-memory 
data.
--
  -- Howard Chu
  CTO, Symas Corp.           http://www.symas.com
  Director, Highland Sun     http://highlandsun.com/hyc/
  Chief Architect, OpenLDAP  http://www.openldap.org/project/