wasteful data structures: AVL tree

[Howard Chu <hyc@symas.com>]

ITS#8038 (syncrepl hanging onto its presentlist) only came to my 
attention due to the amount of memory involved. On a refresh of a DB 
with 2.8M entries I saw the consumer using about 320MB just for the 
presentlist. This list consists solely of 16 byte entryUUIDs; 2.8M items 
should have used no more than 48MB. An AVL node itself is 28 bytes on 
64-bit platform, plus 16 bytes for the struct berval wrapped around the 
UUID.

I'm looking into adding an in-memory B+tree library to liblutil. For the 
type of fixed-size records we're usually storing in AVL trees, a Btree 
will be much more compact and higher performance since it will need 
rebalancing far less frequently.

--
  -- Howard Chu
  CTO, Symas Corp.           http://www.symas.com
  Director, Highland Sun     http://highlandsun.com/hyc/
  Chief Architect, OpenLDAP  http://www.openldap.org/project/