Re: AVL -> T-trees

[Howard Chu <hyc@symas.com>]

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.
--
  -- Howard Chu
  CTO, Symas Corp.           http://www.symas.com
  Director, Highland Sun     http://highlandsun.com/hyc/
  Chief Architect, OpenLDAP  http://www.openldap.org/project/