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? http://dev.mysql.com/doc/refman/5.0/en/create-index.html
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.