我想检查一个 IP 地址是否属于一个子网。当我必须检查 300.000 个子网范围从/3 到/31 的 CIDR block 时,痛苦就来了,每秒几百万次。
取https://github.com/indutny/node-ip例如:
我可以ip.cidrSubnet('ip/subnet')
为所有 300.000 个 block 中的每个 block 检查我要查找的 IP 是否在第一个到最后一个地址范围内,但是这个非常昂贵。
我如何才能以最佳方式检查 IP 地址是否属于这些 block 之一,而不是每次都循环遍历所有 block ?
最佳答案
将信息存储在针对范围检查进行了优化的二叉树中。
一种简单的方法是将每个 CIDR block 变成一对事件,一个在您进入该 block 时,一个在您离开该 block 时。然后按 IP 地址对事件列表进行排序。运行它并创建一个排序的 IP 地址数组以及您所在的 block 数。对于 300,000 个 CIDR block ,将有 600,000 个事件,您的搜索将是 19-20 次查找。
现在您可以对该文件进行二进制搜索,以找到您当前 IP 地址之前的最后一个转换,并根据它是在一个或多个 block 中还是在一个 block 中返回真/假。
如果不是搜索文件,而是搜索某种专用索引,查找会更快。 (搜索中的查找次数相同或略高,但你更好地利用了 CPU 缓存。)我个人在其他语言中使用 BerkeleyDB 的 BTree 数据结构来处理这种事情,并且非常高兴。
关于node.js - 最佳检查 IP 是否在子网中,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38251016/