directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jörg Henne <j.he...@levigo.de>
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


Mime
View raw message