让我们假设我们有geoip的数据库:IPrangeStart
,IPrangeEnd
,country
。
#for, example
1.1.1.1:2.2.2.2:US
3.3.3.3:4.4.4.4:DE
等等。
该数据库有很多字符串,但是所有这些数据都可以完全适合内存(大约200-500Mb)。现在我们需要通过ip查找国家/地区。哪种数据结构最适合这样做(当然,我们会将所有IP都转移到int)?
按范围起始值排序的数组将使您可以通过简单的二进制搜索找到合适的范围。我不知道您使用的地址范围是多少,但是即使您有100万个范围,二进制搜索最多也需要20个探针。您可以轻松地每秒进行成千上万次查找。
另一个选择是段树,尽管在这种情况下我认为它没有特别的帮助,因为您没有重叠的间隔。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句