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?
<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.
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.
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.
I was talking about in general, going by what I saw at this years PostgreSQL Day, specifically http://spring2008.ukuug.org/talk_abstracts.html#41
On Mon, Jun 2, 2008 at 12:49 PM, Howard Chu hyc@symas.com 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
-
Alex Karasulu -
Gavin Henry -
Howard Chu