列表按 key1 排序，按 key2 随机访问
我有一个使用 B+Tree 根据 key1 排序的元组 {key1, key2} 列表。该结构驻留在辅助存储器（HDD）中。我想实现一个算法，它需要按 key1 排序的列表，但也需要使用 key2 随机访问列表。我不需要算法的整个列表，我根据需要从磁盘获取块，因此 B+Tree 可以很好地处理发生的所有插入和删除。
我已经绞尽脑汁一周了，我认为唯一的方法是使用带有 key2 的第二个结构（例如第二个 B 树），但这会使更新树所需的空间和时间加倍。
我对哈希表了解不多，但我不认为我可以用这些将键映射到某个值，对吧？
您是否知道一种可以为我提供对 key2 的随机访问而不会使数据加倍的结构？
或者，我可以使用不需要随机访问的替代算法，但我想将其保留为最后的解决方案。
提前致谢
I have a list of touples {key1, key2} sorted according to key1 using a B+Tree. This structure resides in secondary memmory (HDD). I want to implement an algorithm which requires lists sorted on key1 but also requires random access to the list with key2. I don't need the whole list for the algorithm, I get blocks from the disk as needed so the B+Tree works nice with all the insertions and deletions that occure.
I've been banging my head for a week and I think the only way is to use a second structure (eg a second B-Tree) with key2, but this doubles the already large space needed and time required to update the tree.
I don't know much about hashtables, but i don't think I can map a key to a certain value with these, right?
Do you have any idea about a structure that could provide me with random access to key2 without doubling the data?
Alternatively I could use an alternative algorithm that doesn't require random access but I want to leave that as a last solution.
Thanks in advance
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我认为，如果您关心速度，最好的方法是构建一个指向 key2 的哈希表。哈希表的插入和查找速度通常比 B 树更快。
并且您不需要将所有数据加倍，只需从哈希表指向现有结构中的 key2 即可。
更新：如果您还没有使用过哈希表，请阅读：
I think the best way, if you're concerned about speed, is to build a hash table pointing to key2. Hashtables are generally faster on inserts and lookups than B Trees.
And you won't need to double all data, just point from the hashtable to key2 in your existing structure.
Update: If you haven't worked with hashtables, read: