IP地址的索引范围搜索算法

你可以看看 Interval tree 找出与任何给定间隔或点重叠的所有间隔。

对于不重叠的IP范围,可以使用B树或类似的紧凑尝试 Judy arrays (64-bits) 用于索引和搜索(将起始IP存储为键,将结束IP存储为值)。

简单的 Radix Tree 它被用于 longest prefix match Internet路由查找,可以缩放以保存表示重叠其他较小CIDR子网的较大CIDR子网的节点。最长的匹配查找将遍历这些节点,这些节点也将被选中以获取与IP地址匹配的整个CIDR子网集。

现在,要将IP范围保存在同一个树中,我们可以 convert each range into a set of CIDR subnets . 尽管集合可能有很多子网(甚至一些主机IP,也就是IP/32类CIDR地址),但这总是可以做到的。

你有100亿条规则来匹配40亿个可能的地址?

创建一个包含40亿个地址的表。对于100亿条规则中的每一条,“绘制”它适用的地址,当两个或多个规则适用于同一个地址时做一些明智的事情。