给定一个包含 100 亿个以 CIDR 表示法表示的 IPv4 范围或两个 IP 之间的 ACL 列表：
x.x.x.x/y
x.x.x.x - y.y.y.y
用于测试给定 IP 地址是否满足一个或多个 ACL 范围条件的有效搜索/索引算法是什么？
假设大多数 ACL 范围定义跨越大量 C 类块。
通过哈希表对点进行索引很容易，但请尝试一下，因为我可能无法想出一种合理的方法来检测哪些点被大量“线”覆盖。
有一些想法，比如在一定的细节级别上进行索引提示——比如在 C 类级别上预先计算覆盖该点的每个 ACL，但表会太大..或者某种 KD 树来动态设置详细级别。
还想到也许有碰撞检测算法可以解决这个问题。
有任何正确方向的提示或指示吗？
简单的基数树 http://en.wikipedia.org/wiki/Radix_tree已被用于最长前缀匹配 http://en.wikipedia.org/wiki/Longest_prefix_match互联网路由查找可以扩展以保存代表与其他较小子网重叠的较大 CIDR 子网的节点。最长匹配查找将遍历这些节点，这些节点也将被选择以获得与 IP 地址匹配的整个 CIDR 子网集。
现在，要将 IP 范围保存在同一棵树中，我们可以将每个范围转换为一组 CIDR 子网 http://www.perlmonks.org/?node_id=79663。尽管该集合可能有很多子网（甚至一些主机 IP，即 IP/32 类 CIDR 地址），但始终可以完成此操作。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
