高效查找范围表

Question

我有一个由160万个IP地址范围和组织名称组成的表格。IP地址被转换为整数。该表格的形式如下： 我有一个包含2000个唯一IP地址（例如321223，531223等）的列表需要翻译成组织名称。

我将翻译表作为MySQL表加载，并在IP_from和IP_to上创建索引。我循环遍历这2000个IP地址，每个IP地址运行一次查询，15分钟后报告仍在运行。我使用的查询是：

select organization from iptable where ip_addr BETWEEN ip_start AND ip_end

有没有更有效率的方式来进行这个批量查找？如果有好的解决方案，我可以用手指头来实现。如果有 Ruby 特定的解决方案，请告诉我，因为我正在使用 Ruby。

- gitb

---

你想在(IP_from, IP_to)上创建一个R-Tree（空间）索引。 - eggyal

你使用了哪些索引？ - Walter Tross

我们需要更多的信息，比如模式和查询。我们还需要知道为什么Ruby和Rails是标签。 - the Tin Man

Answer 1

假设您已经在 ip_start 上有一个索引，以下是如何最好地使用它，假设您想要每个IP进行一次访问（例如此示例中的1234）：

select organization from (
    select ip_end, organization
    from iptable
    where ip_start <= 1234
    order by ip_start desc
    limit 1
) subqry where 1234 <= ip_end

这将使用您的索引来开始扫描，由于limit 1的存在，扫描会立即停止。成本应该只比简单索引访问略高。当然，这种技术依赖于ip_start和ip_end定义的范围从不重叠的事实。

您原始方法的问题在于mysql不知道这个约束条件，只能使用索引确定在哪里开始或停止扫描（它认为）需要找到查询的所有匹配项。

- Walter Tross

---

你是一个mysql(sql)之神。使用原始问题中的索引和我的查询，我发现：1）9位数字以下的IP地址（例如248082010）需要大约40ms。2）十亿级别、即10位数字（如1823194021）以上的IP地址需要约600ms，这就是性能问题的瓶颈。使用您的查询，所有内容只需0.5ms。哇。 - gitb

谢谢 @gitb，但如果我是神，世界将会是一个万神殿;-) 你介意我把你的问题标题改成“范围表中的高效查找”吗？（或者也许你有更好的标题）。这将是朝着“在Stack Overflow中高效查找”的方向。 - Walter Tross

Answer 2

可能做这种查找的最有效方法是将要查找的地址列表加载到数据库的临时表中，并查找与SQL联接的交集，而不是使用单独的SQL语句检查每个地址。

无论如何，您都需要在（IP_from，IP_to）上建立索引。

- Joni

---

很可能，我的2000个IP地址都不在查找表中。它们将落在“from”和“to”字段之间。所以我不知道如何进行连接。 - gitb

你可以写成 JOIN ON ip >= ip_from AND ip <= ip_to。虽然效率可能不如使用 = 进行连接，但是通过适当的索引优化，它并不会差太多。 - Joni

你会得到所有匹配项，@Walter。如果没有重叠的范围，每个IP最多只会得到一个结果。 - Joni

@WalterTross，你说得对，我稍微读了一些资料，发现我对数据库索引的理解是不完整的。在(ip_from, ip_to)上的常规B树索引只能帮助处理ip_from的条件，就像你所说的那样，而我建议的简单查询将意味着数据库必须扫描数千个条目才能满足ip_to的条件。 - Joni

@Joni，嗯，我也学到了一些东西：在特定情况下可以使用多个索引（http://dev.mysql.com/doc/refman/5.5/en/index-merge-optimization.html），尽管这不适用于手头的情况。 - Walter Tross