php - IP地址的快速文件搜索算法

Question

问题

查找 IP 地址是否存在于包含排序为 IP 地址的文件中的最快方法是什么:

219.93.88.62
219.94.181.87
219.94.193.96
220.1.72.201
220.110.162.50
220.126.52.187
220.126.52.247

约束

• 没有数据库(例如 MySQL、PostgreSQL、Oracle 等)
• 允许不频繁的预处理(参见可能性部分)
• 最好不要每次查询都加载文件 (131Kb)
• 使用不到 5 兆字节的磁盘空间
• 没有额外的 PHP 模块

文件详细信息

• 每行一个 IP 地址
• 9500 多行

可能的解决方案

• 创建目录层次结构 ( radix tree ?) 然后使用 is_dir()(遗憾的是，这使用了 87 兆字节)

Answer 1

如果在到达 232.0.17.1

之前要检查 9,000 个不匹配项，逐行扫描文件以查找 IP 似乎很痛苦

您的文件是否仅限于单个文件？例如假设此列表是被禁止的 IP，而您只想查看是否有一个“在”列表中。

如果您创建一个包含多个文件的 DIR 会怎样:

BannedIPs
  +- 0.ips
  +- 1.ips
  +- 37.ips
  +- 123.ips
  +- 253.ips
  +- 254.ips

每个文件仅包含以该数字开头的 IP 地址。

如果您足够幸运能够均匀分布...您将有 256 个文件，但每个文件只有约 37 个条目。

因此，当您想要测试:232.0.17.1 时，您可以查看 232.ips 文件并扫描它。