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