[Date Prev][Date Next] [Chronological] [Thread] [Top]

Re: AVL -> T-trees

Gavin Henry wrote:
<quote who="Howard Chu">
Taking a cue from our MySQL friends - MySQL uses T-trees for their
structures. These are balanced trees, like AVL trees. But instead of just
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

I would expect that they perform about as well as AVL trees for lookups.
Anyone interested in experimenting here and reporting on the relative

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/