[Date Prev][Date Next]
[Chronological]
[Thread]
[Top]
Re: wasteful data structures: AVL tree
- To: openldap-devel@openldap.org
- Subject: Re: wasteful data structures: AVL tree
- From: Emmanuel Lécharny <elecharny@gmail.com>
- Date: Thu, 29 Jan 2015 08:12:24 +0100
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:subject:references :in-reply-to:content-type:content-transfer-encoding; bh=iJLfEU9hFnU0NX27cW4nwtYZaeRoJ/gqJKBl0VkYTv4=; b=Vl0Iwhh7sm6kKc9ZIMFwafOv/qbPFNP6Wz7UvXShIRFLGb0rNVuTwRW6Z+XTNoEXIw fakFlty4AdI/MBJZvtc5V5ZL5J0FbQj4JJETsSFBBXPHNHJAVxD7fXuWjaLN7DB6UDTz 6KQtVPxRhShUROjQRQ6jL5dj4YqGIm0UB8/TknLHxj1exSFBRRCpiC9KVafNk5xK3T9P 9+BvA1czCdTxPCAim+UmhvcoK24pLn1axB4fKcsiYPnbO9l4heclA/8yrcCQUQ7kbWYE f/NduluU3yxl2/K6/6EwqgMinGwxR5jhzR9GL35CSKRzqztnNStpdeCbAXYdZwA8EVDs X/gg==
- In-reply-to: <54C9A6F4.3020707@symas.com>
- References: <54C9A6F4.3020707@symas.com>
- User-agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9; rv:31.0) Gecko/20100101 Thunderbird/31.4.0
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...