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
smime.p7s
Description: S/MIME Cryptographic Signature
