最佳检查IP是否在子网中
我想检查一个IP地址是否属于一个子网。 当我必须检查具有从/ 3到/ 31，几百万次/秒的子网的300.000个CIDR块时，会出现这种情况。
以https://github.com/indutny/node-ip为例：
我可以ip.cidrSubnet('ip/subnet')为每个300.000块，并检查我正在寻找的IP是在倒数第一个地址范围内，但这是非常昂贵的。
我怎样才能最佳地检查IP地址是否属于这些块之一，而不是每次都循环遍历它们？
将信息存储在为范围检查而优化的二叉树中。
一种天真的做法是将每个CIDR块变成一对事件，当你input块时，一个当你退出块。 然后按IP地址对事件列表进行sorting。 通过它运行，并创build一个有序的数组的IP地址，你有多less块。对于300,000 CIDR块将有600,000事件，您的search将是19-20查找。
现在，您可以对该文件执行二进制search，以查找当前IP地址之前的最后一个转换，并根据是否在一个或多个块中而不是在一个块中返回true / false。
如果不是search文件，而是search某种专用索引，查找速度会更快。 （在search中查找的数量是相同的或稍高一些，但是您可以更好地使用CPUcaching。）我个人使用BerkeleyDB的BTree数据结构来处理其他语言的这类事情，并且非常高兴。