Trie Hashing With Controlled Load
Trie Hashing With Controlled Load
复制标题
具有受控负载的 Trie 哈希
DOI：
10.1109/32.83904
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
Wang Hong
中科院分区：
文献类型：
--
作者：
W. Litwin;N. Roussopoulos;Gérald Lévy;Wang Hong
讨论了一种用于存储和访问动态文件记录的主键访问方法Trie Hash(TH)。密钥地址是通过trie计算的。当trie在核心中时，关键字搜索通常只需要一次磁盘访问，而当trie必须在磁盘上时，对于非常大的文件，通常只需要两次磁盘访问。提出了一种改进的TRIE散列算法--带受控负载的TRIE散列算法(THCL)。它被设计为像B树文件一样严格地控制TH文件的加载系数，允许有序插入的高加载系数高达100%，并将随机插入的加载系数从70%提高到85%以上。结果表明，这些性质使得Trie散列比B-树更好。>；
Trie hashing (TH), a primary key access method for storing and accessing records of dynamic files, is discussed. The key address is computed through a trie. A key search usually requires only one disk access when the trie is in core and two disk accesses for very large files when the trie must be on disk. A refinement to trie hashing, trie hashing with controlled load (THCL), is presented. It is designed to control the load factor of a TH file as tightly as that of a B-tree file, allows high load factor of up to 100% for ordered insertions, and increases the load factor for random insertions from 70% to over 85%. It is shown that these properties make trie hashing preferable to a B-tree. >