Redis或Mongo用于确定数字是否在范围内？

Redis或Mongo用于确定数字是否在范围内？

与上一幅海报相反，我认为您不能通过使用朴素索引来获得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-8B 4-6C 2-9D 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 11) "range:4"> lrange range:4 0 -11) "2-8"2) "2-9"3) "4-6"