directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Howard Chu <>
Subject Re: splay tree for duplicate key cursor implementation
Date Tue, 12 Feb 2008 08:31:50 GMT
Jörg Henne wrote:
> Kiran Ayyagari schrieb:
>>     So we are thinking of using some kind of btree for the actual
>> implementation.
> "common database wisdom" is to use a B+-Tree for this kind of
> application. A B+-Tree has all its keys in the bottom-most node-level.
> Furthermore, it usually has bottom-level links between adjacent nodes.
> This approach results in several advantages
> - the tree nodes map nicely to disk blocks
> - (read) accesses require an exactly known number of disk accesses
> - the top-few node-levels can be easily kept in a buffer-cache (this
> happens almost automatically if one uses an LRU-approach for retaining
> nodes in the cache)
> - since all keys/data is guaranteed to be present in the bottom-most
> node-level and adjacent nodes are linked, range retrievals become very
> efficient, because the retrieval doesn't have to percolate upwards in
> order to traverse the tree.

Also look into B-link trees. They have very nice locking properties (that I 
wish the BerkeleyDB guys would implement for us. Sigh.)

   -- Howard Chu
   Chief Architect, Symas Corp.
   Director, Highland Sun
   Chief Architect, OpenLDAP

View raw message