我需要一种方法来快速检查IP地址是否属于许多禁止的IP范围之一。
我目前使用iptables检查IP是否落在指定范围内。这在几千个范围内都可以正常工作，但是这个数字将急剧增加到几十万，并且还将继续增长。
我当前的简单地向iptables添加新规则的方法的另一个问题是重复项的数量不断增加。
在将IP或范围添加到规则集之前，我需要一种有效的方法来检查IP或范围是否属于现有（较大）范围。
Ruby是我最熟悉的语言，但是对于越来越多的范围，哪种数据结构将是最佳选择？
我想出的一个解决方案是使用Redis集或MongoDB将单个IP存储为整数，然后简单地检查IP是否存在于集内……但是我的直觉告诉我，必须有一种更聪明的方法。
如果我要将IP转换为整数并存储范围，那么遍历范围以查看现有的较大范围是否已包含新IP或范围的最佳方法是什么？
最后说明：速度比内存成本更为重要。
与上一幅海报相反，我认为您不能通过使用朴素索引来获得O（log n）复杂性。让我们以mongodb为例。您可以定义两个索引（用于范围的开始和结束属性），但是mongodb仅使用一个索引来解决给定查询。因此它将不起作用。现在，如果您使用涉及范围的开始和结束属性的单个复合索引，则复杂度将是对数的，以找到要检查的第一个范围，但是，它将变得线性，以找到与查询匹配的最后一个范围。最糟糕的情况是O（n），并且当所有存储的范围都与输入重叠时，您就会拥有它。
附带说明一下，如果您知道要做什么，则使用Redis排序集可以模拟排序索引（复杂度为O（log n））。Redis不仅仅是一个简单的键值存储。使用跳过列表实现Redis排序集，并且得分和值都用于比较项目。
为了解决这种问题，需要专用的索引结构。您可能需要看一下：
http://en.wikipedia.org/wiki/Segment_tree 或 http://en.wikipedia.org/wiki/Interval_tree
如果关注的是速度与空间的关系，则使索引变平可能会很有趣。例如，让我们考虑以下范围（仅使用整数来简化讨论）：
A 2-8 B 4-6 C 2-9 D 7-10
可以建立索引非重叠段的稀疏结构。
0 [] 2 [A C] 4 [A C B] 7 [A C D] 9 [C D] 10 [D] 11 []
每个条目都包含一个非重叠段的下限作为键，并包含匹配范围的列表或集合作为一个值。条目应使用已排序的容器（树，跳过列表，btree等）建立索引。
要找到匹配5的范围，我们寻找小于或等于5的第一个条目（在本示例中为4），并提供了范围列表（[ACB]）
使用这种数据结构，查询的复杂度实际上为O（log n）。但是，构建和维护它并非易事（且昂贵）。它可以与mongodb和Redis一起实现。
这是Redis的示例：
> rpush range:2 2-8 2-9 (integer) 2 > rpush range:4 2-8 2-9 4-6 (integer) 3 > rpush range:7 2-8 2-9 7-10 (integer) 3 > rpush range:9 2-9 7-10 (integer) 2 > rpush range:10 7-10 (integer) 1 > zadd range_index 0 range:0 2 range:2 4 range:4 7 range:7 9 range:9 10 range:10 (integer) 6 > zrevrangebyscore range_index 5 0 LIMIT 0 1 1) "range:4" > lrange range:4 0 -1 1) "2-8" 2) "2-9" 3) "4-6"
