Redis或Mongo确定一个数字是否在范围内？

我需要一种快速检查IP地址是否属于许多禁用IP范围之一的方法。

我目前使用iptables来检查IP是否属于指定范围。这适用于几千个范围，但这个数字将急剧增加到几十万，并将继续增长。

我目前简单地向iptables添加新规则的方法的另一个问题是重复数量的增加。

我需要一种有效的方法来检查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 [AC] 4 [ACB] 7 [ACD] 9 [CD] 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"

如果你正在处理范围，那么mongodb将比redis更好。如果您正在处理特定的IP地址，redis将是最佳选择。

为什么？

Mongodb可以在ip地址的开始和结束范围上构建索引，您可以在O（log n）时间内查询，而redis只是一个键值存储。

你可以使用redis哈希，如果你要检查的每一个ip都在一个哈希表中并在O（1）时间查找它们但是因为你使用范围我会说mongo是你最好的选择。我不认为你会比使用redis工具包中的任何数据结构更好地记录时间。具有有序集或列表的O（n）可能但不是O（log n）。