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

Re: AVL -> T-trees

Simon Riggs wrote:
Hi Gavin,

PostgreSQL uses B-trees as the main index type, though also supports
GIST, GIN and Hash index types. We avoid re-balancing the trees at
delete time, which is a high source of contention.

MySQL, to my knowledge, doesn't support T-Trees?

As I noted to Gavin, that's a different thing entirely. Our on-disk indexing uses B-trees as well, but our in-memory caches use AVL trees. I would love to try a B-link tree implementation for our on-disk data, but that's yet another story...

T-Trees are a class of index known to be cache conscious, but they also
perform poorly when I/O is involved. Selecting that would mean you'd
need to know in advance the memory allocation given to your server,
which may not be as much as you want and can change over time. You can
have non-persistent indexes, though rebuilding indexes at startup can be
annoying also.

I/O is not a consideration for this purpose.

Does OpenLDAP experience a high insert/delete rate? I would have
expected most uses to be mostly read-only, percentage-wise, but I guess
you'll set me straight.

Yes, there is a high rate of insert/deletes into the caches when the cache is smaller than the working set. Since T-trees allow more data items to be stored per tree node, that also means we could have less overhead in tree link pointers.
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/