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. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/
