为了快速查找，读/写IPv6地址范围的有效数据结构是什么？
为了快速查找，读/写IPv6地址范围的有效数据结构是什么？
提问于 2017-08-08 03:09:20
我正在尝试想一种有效的数据结构，我可以用它来存储IPv6地址范围。查找时间应该很快。也就是说，给定一个IPv6地址，我应该能够快速确定它来自哪个间隔。在我的例子中，地址范围不重叠。
一种有效的方法是创建一个简单的二进制搜索树，并且每个非叶节点将简单地“重定向查找流量”。然而，这种方法的问题是，BST的大小会非常大，大约是2^128个节点，我可能无法对文件进行读/写。
那么，我可以使用什么数据结构来快速查找IPv6地址，并且对文件大小也有一个下限呢？
顺便说一下，我正在使用Java。
回答 2
Stack Overflow用户
发布于 2017-08-08 03:15:00
为此，有一个非常好的数据结构，称为区间树。它基于普通的二进制搜索树。但是，它不是存储关键字，而是存储间隔。并且支持值的查找。它可以返回找到键的节点。因为节点包含它的边界，所以很容易实现你的用例。
Stack Overflow用户
发布于 2017-08-08 03:57:02
如果你不需要定义IPv6的时间间隔，那么我相信你可以使用trie数据结构。
关于tries实现的一些文档。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/45554116
复制相关文章
相似问题
腾讯云开发者
