directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jörg Henne <>
Subject Re: splay tree for duplicate key cursor implementation
Date Tue, 12 Feb 2008 08:21:44 GMT
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.

Joerg Henne

View raw message