Hash—Tree—一种词典组织方法

本文讨论了一种新的数据组织Hash-Tree。它综合了散列(Hash)和树(Tree)的优点。Hash使键值分布均衡,使所生成的基本上是一棵平衡树,而树结构又使最坏时间开销从Hash的O(N)降为o(logk N),k是树的分枝数。Hash-Tree的算法难度远较B-树,B~+树,DB树为低,当然它仅适于随机检索。 本文提出了Hash-树的结构及操作算法,分析了它的时空效率,对它的优劣作了简单评述。