给定一个包含 100 亿个 IPv4 范围的 ACL 列表，在 CIDR 通知中或在两个 IP 之间:
x.x.x.x/y
x.x.x.x - y.y.y.y
用于测试给定 IP 地址是否满足一个或多个 ACL 范围的标准的有效搜索/索引算法是什么？
让我们假设大多数 ACL 范围定义跨越大量 C 类块。
通过哈希表索引点很容易，但请尝试，因为我可能无法提出一种合理的方法来检测哪些点被大量“线”覆盖。
有一些想法，比如在某个细节级别建立索引提示——比如在 C 类级别预先计算涵盖该点的每个 ACL，但表会太大......或者某种 KD 树来动态设置细节级别.
还认为可能有碰撞检测算法可以解决这个问题。
任何关于正确方向的提示或指示？
最佳答案
你可以看看Interval tree找到与任何给定间隔或点重叠的所有间隔。
对于非重叠的 ip 范围，您可以使用 b 树或紧凑尝试，如 Judy arrays (64-bits)用于索引和搜索(将 start-ip 存储为键，将 end-ip 存储为值)。
关于indexing - IP 地址的索引范围搜索算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1042366/