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

Re: wasteful data structures: AVL tree

Le 29/01/15 04:20, Howard Chu a écrit :
> 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.
Why using a B+tree ? A hash map wouldn't be a more appropriate data
structure ? EntryUUID ordering seems overkilling...