0

我有一个使用 B+Tree 根据 key1 排序的 touples {key1, key2} 列表。此结构位于辅助存储器 (HDD) 中。我想实现一个算法，它需要在 key1 上排序的列表，但也需要使用 key2 随机访问列表。我不需要算法的整个列表，我会根据需要从磁盘中获取块，因此 B+Tree 可以很好地处理所有发生的插入和删除。

我已经苦苦挣扎了一周，我认为唯一的方法是使用第二个结构（例如第二个 B-Tree）和 key2，但这会使更新树所需的空间和时间加倍。

我对哈希表了解不多，但我认为我不能用这些将键映射到某个值，对吧？

您对可以为我提供对 key2 的随机访问而不会使数据加倍的结构有任何想法吗？

或者，我可以使用不需要随机访问的替代算法，但我想将其作为最后的解决方案。

提前致谢

4

1 回答 1

0

如果您关心速度，我认为最好的方法是构建一个指向 key2 的哈希表。哈希表在插入和查找方面通常比 B 树更快。而且您不需要将所有数据加倍，只需从哈希表指向现有结构中的 key2 即可。

更新：如果您没有使用过哈希表，请阅读：

于 2011-02-03T11:08:06.000 回答