文档章节

php根据二分查找法从普通csv文件中获取ip的地理位置(效率比使用mysql提高近800倍)

酒逍遥
 酒逍遥
发布于 2013/08/21 10:49
字数 1622
阅读 1006
收藏 14

最近要做一个全球的ip地理位置查询,并且要精确到城市一级,还要求是英文版的.

首先是要找ip库, 纯真ip 库只有中文的,而且国内的ip缺少国家这一级的分类,放弃

apnic 的倒是不错,英文而且更新也快,但是只有国家一级.

终于电驴上找到了相关的资源 IP地理位置数据库 世界城镇扩展版 130812 

数据来源于 MaxMind , 也算比较新的. 这个比较符合要求.

数据源是csv格式的. 格式如下:

 16777472  16778239  CN  CHN  China  

 16785408  16793599  CN  CHN  Guangzhou,  Guangdong, China

前两列是ip端 , 三四列 是国家英文名缩写, 第五列是 国家和地区,用逗号分割的.

看到这个数据,第一反应是导入到mysql数据库然后从数据库查询,但是看了下总数据大概有接近200w条.总大小130M 

预计mysql查询起来也不会太快.

于是自己弄了个简单版的二分查找法.这样可以直接在csv文件中查找,无需导入数据库,查询效率也不低.

总体思路是这样.

先用php读取csv文件的每行数据, 获取该行数据的大小.然后建立一个二进制的索引文件

索引文件的格式如下:

start_ip  end_ip   offset  length

start_ip表示起始ip  ,end_ip表示结束ip , offset表示数据在csv文件中的文件指针偏移位置,length表示该条数据的长度

然后然把数据打包成二进制数据存放到索引文件中.

除了length 外,其他的数据采用无符号长整型,length采用short就可以了. 每一行数据对应一条索引 ,索引长度是 4+4+4+2=14个字节.

200w 行的数据索引大小大概是 26.7M 左右,采用二分法查找时, 最坏的结果是需要循环 21次 才能得到最终的结果.不过效率依然比用数据库高出不少.

部分代码和测试结果如下:

首先把csv 导入数据库 . 

建立表 id_addr 

CREATE TABLE IF NOT EXISTS `ip_addr` (

  `start_ip` bigint(20) NOT NULL,

  `end_ip` bigint(20) NOT NULL,

  `short` varchar(5) COLLATE utf8_unicode_ci NOT NULL,

  `short1` varchar(5) COLLATE utf8_unicode_ci NOT NULL,

  `country` varchar(50) COLLATE utf8_unicode_ci NOT NULL,

) ENGINE=InnoDB  DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci

导入 csv  

mysql> load data infile 'E:/source/ip-to-country.csv' into table ip_addr fields terminated by ',' optionally encl

osed by '"' lines terminated by '\r\n';

测试查询 某IP 59.173.248.188 ,转换为整型 1001257148 

查询语句:SELECT * FROM `ip_addr` WHERE start_ip<=1001257148 and end_ip>=1001257148 ;

查询结果和时间

1001127936   1001390079   CN   CHN    Wuhan, Hubei, China

1 total, Query took 4.4871 sec

耗时近4.5秒

对start_ip和end_ip 建立索引

ALTER TABLE  `ip_addr` ADD INDEX (  `start_ip`,`end_ip` );

再次执行 该查询语句: SELECT * FROM `ip_addr` WHERE start_ip<=1001257148 and end_ip>=1001257148 ;

查询结果相同

1 total, Query took 1.7607 sec

耗时减少到1.76秒 

效率大概提高了60%左右..但是依旧不尽如人意.

再来看看我们的粗略二分查找法的效率如何.

首先根据csv生成索引,php代码如下:

<?php
$fp=fopen('E:/source/ip-to-country.csv','r');
$fp1=fopen('E:/source/ip-to-country.csv','r');
$fp2=fopen('E:/source/index.dat','w');
$i=0;
$offset=0;
$length=0;
while(($line=fgets($fp))&&($line1=fgetcsv($fp1))){
    $length=strlen($line);
    $start_ip=$line1[0];
    $end_ip=$line1[1];
    $index=pack('L',(float)$start_ip).pack('L',(float)$end_ip).pack('L',(float)$offset).pack('S',$length);
    $offset+=$length;
    fwrite($fp2,$index);
}
fclose($fp);
fclose($fp1);
fclose($fp2);

然后同样查询 这个IP :59.173.248.188  代码如下:

<?php
$ip='59.173.248.188';
$ip=sprintf('%u',ip2long($ip));
$time=microtime(1);
$fp=fopen('E:/source/index.dat','r');
$begin = 0;
$end = filesize('E:/source/index.dat');
$start_ip = sprintf('%u',implode('', unpack('L', fread($fp, 4))));
fseek($fp,$end-10);
$end_ip = sprintf('%u',implode('', unpack('L', fread($fp, 4))));
do{
    if($end - $begin <=14){
        fseek($fp,$begin);
        $s=sprintf('%u',implode('', unpack('L', fread($fp, 4))));
        $e=sprintf('%u',implode('', unpack('L', fread($fp, 4))));
        if($ip<$s||$ip>$e) break;
        $offset = sprintf('%u',implode('', unpack('L', fread($fp, 4))));
        $length = implode('', unpack('S', fread($fp, 2)));
        break;
    }
    $middle_offset = ceil((($end - $begin) / 14) / 2) * 14 + $begin;
    fseek($fp, $middle_offset);
    $middle_ip = sprintf('%u',implode('', unpack('L', fread($fp, 4))));
    if ($ip >= $middle_ip) {
        $begin = $middle_offset;
    } else {
        $end = $middle_offset;
    }
}while(1);
 
if($length>0){
    fclose($fp);
    $fp=fopen('E:/source/ip-to-country.csv','r');
    fseek($fp,$offset);
    $line=fgetcsv($fp,$length);
}
echo implode(',',$line).'<br />';
echo microtime(1)-$time;

输出

1001127936,1001390079,CN,CHN,Wuhan, Hubei, China
0.00243091583252

查询结果一样.但是耗时在0.002s 左右...效率差不多提高了800倍...

也许会有人说这是二分查找时碰到最佳情况..只循环几次就找到了结果..我测试的结果是循环了总共循环了22次.也就是最差的查找结果哦


其实这个原理和数据库建索引的原理是一个道理.我也顺便测试了一下不建索引,直接通过csv文件一行一行去查找耗时几何

代码如下:

<?php
$ip='59.173.248.188';
$ip=sprintf('%u',ip2long($ip));
$time=microtime(1);
$fp=fopen('ip-to-country.csv','r');
while($line=fgetcsv($fp)){
    if($ip>=$line[0]&&$ip<=$line[1]){
        break;
    }
}
fclose($fp);
echo implode(',',$line)."<br />";
echo microtime(1)-$time;

输出:

1001127936,1001390079,CN,CHN,Wuhan, Hubei, China
3.92840719223 

耗时接近 4秒 和无索引的数据库查询速度相接近了.

代码和算法思路都很简单..但是却能大大的提高数据检索效率。作为程序员有时候,也需要多多思考一下这方面的问题.


扩展思维: 现在是200w行数据,如果数据扩大到 2000w行 甚至2亿行数据呢? 这种方式的效率会呈几何数级的下降.

怎么解决? 这就是所谓的大数据了.不考虑什么hadoop之类的.如果这时候要你来解决,你会用什么方案?

其中一个思路: 比如 现在csv文件扩展到2亿行数据, 那么其实我们可以把文件切分成20个不同的小文件每个文件就只有1000w行数据. 然后利用多线程编程(php5.3 开始支持多线程了), 开10个线程,同时检索10个文件.马上效率就提高了10倍.

再极端一点.把文件分成100个小文件,这样每个文件只有200w行数据, 10台机器,每台机器开10个线程,每个线程检索一个文件.

此时对单一线程来说,检索效率就和上文的例子一样了. 这样你会发现2亿行的数据处理起来和200w行的数据,时间是差不多的.

这 其实就是所谓的大数据,分布式的概念了. 当然实际应用中会比这个要复杂的多的多.


© 著作权归作者所有

共有 人打赏支持
酒逍遥

酒逍遥

粉丝 48
博文 40
码字总数 35454
作品 0
武汉
高级程序员
私信 提问
加载中

评论(11)

酒逍遥
酒逍遥

引用来自“那些年我们一起”的评论

嗯,纯真ip库返回的是地址,请问楼主知道哪儿有精确到省市级IP库么?例如,province=湖北,city=武汉。

可以看看 这个 http://emulefans.com/ip-to-country-china-130401/
那些年我们一起
那些年我们一起
嗯,纯真ip库返回的是地址,请问楼主知道哪儿有精确到省市级IP库么?例如,province=湖北,city=武汉。
酒逍遥
酒逍遥

引用来自“那些年我们一起”的评论

这个ip库好像不准,楼主可以试试这个ip,211.89.152.10。

嗯 是的..我也发现有些国内的ip 不是很准. 这个是全球版的.可能国内的ip 更新的比较慢.
你可以上那个网站下子 专门的国内ip版的试试.
其实国内ip的话, 纯真其实都比较准..我用这个主要是查全球的.国内反而要求精度不是那么高
那些年我们一起
那些年我们一起
这个ip库好像不准,楼主可以试试这个ip,211.89.152.10。
酒逍遥
酒逍遥

引用来自“唧唧”的评论

楼主的二分法查找的确不错,很精彩.但sql语句速度慢并非mysql本身的问题, 像number>=start_ip这样的条件,会筛选出一大批数据来(就用楼主的这个查询,大概要20多万条,,然后在逐个比较另外一个条件end_ip,的确要一些时间).
楼主的巧妙二分法正好避免的这个逐个比较的麻烦,因为对于有序数据来说无需一条条比较.

but,既然数据已排序,并且不可能交叉,那不是大于start_ip的第一条,就是小于end_ip的最后一条,我们也可以这样改写mysql语句:
(SELECT SQL_NO_CACHE * FROM `ip_addr` WHERE start_ip<=1001257148 limit 1) union (SELECT * FROM `ip_addr` WHERE end_ip>=1001257148 limit 1).然后从这两条里面判断应该也很快吧.

总的来说,是精彩的好文啊.

呵呵 ,是的.mysql本身也可以进行优化.在数据本身是有序的情况下,你的sql就非常适合.
速度也非常的快.

唧唧
楼主的二分法查找的确不错,很精彩.但sql语句速度慢并非mysql本身的问题, 像number>=start_ip这样的条件,会筛选出一大批数据来(就用楼主的这个查询,大概要20多万条,,然后在逐个比较另外一个条件end_ip,的确要一些时间).
楼主的巧妙二分法正好避免的这个逐个比较的麻烦,因为对于有序数据来说无需一条条比较.

but,既然数据已排序,并且不可能交叉,那不是大于start_ip的第一条,就是小于end_ip的最后一条,我们也可以这样改写mysql语句:
(SELECT SQL_NO_CACHE * FROM `ip_addr` WHERE start_ip<=1001257148 limit 1) union (SELECT * FROM `ip_addr` WHERE end_ip>=1001257148 limit 1).然后从这两条里面判断应该也很快吧.

总的来说,是精彩的好文啊.
酒逍遥
酒逍遥
嗯 其实 length 没必要写到索引中.. 因为并没有对 csv文件进行任何处理.
只需要记录每行开始的 文件指针偏移位置就可以了.
然后直接读一行数据即可.这样索引文件还能更小一点.大概22M多就行了.可以省5M多空间.
酒逍遥
酒逍遥

引用来自“那些年我们一起”的评论

我试了下你写的代码,怎么获取的数据不对呢?

呃 ,不好意思...生成索引那段 有点问题.. while 条件中缺少 小括号. 已经修正了..
你可以尝试重新生成索引 再试试..
另 多谢指正...
while那个地方之前是分成2个条件判断的..后来决定合成一个条件..于是就杯具了
酒逍遥
酒逍遥

引用来自“那些年我们一起”的评论

我试了下你写的代码,怎么获取的数据不对呢?

应该不会啊...代码我都本地执行过列
那些年我们一起
那些年我们一起
我试了下你写的代码,怎么获取的数据不对呢?
PHP-二分查找秒解析IP地理位置

通过二分查找的方法,我们可以在1秒内从19万条IP信息中找到我们所需要的IP,这大大地提高了查找速度。 资料准备:CHINAIPINFO.txt (这里面包含了中国所有的IP网段和实际地理位置的关系,可以...

咖啡绿茶不加糖
2017/12/04
0
0
二分法在IP地址查询中的应用(来自深空老大)

前段时间做数据分析,需要大量的IP地址查询(每秒钟近万次检索),首先考虑到使用数据库。数据库大概存储几十万条IP记录,记录集如下: 这样做查询需要用到如下SQL: 这样的检索显然用不到索...

岭南六少
2011/07/21
0
0
【转载】memcache分布式 [一致性hash算法] 的php实现

最近在看一些分布式方面的文章,所以就用php实现一致性hash来练练手,以前一般用的是最原始的hash取模做分布式,当生产过程中添加或删除一台memcache都会造成数据的全部失效,一致性hash就是...

hengfeng_su
2015/04/01
0
0
memcache一致性hash的php实现方法

memcache一致性hash的php实现方法 本文实例讲述了memcache一致性hash的php实现方法。分享给大家供大家参考。具体如下: 最近在看一些分布式方面的文章,所以就用php实现一致性hash来练练手,...

开元中国2015
2015/04/20
82
0
大批量IP查询和IP区域快速查询

相信做互联网开发的很多人都有一个需求,那就是获取用户的ip,并定位用户访问是哪个省哪个市的。从这个需求来看,首先需要有ip数据库,其次对于某些查不到的ip还能够定期更新ip数据库到最新的...

小天120
2014/02/11
0
6

没有更多内容

加载失败,请刷新页面

加载更多

新技术不断涌现,下一代云计算的突破口在哪里?

这是一个IT技术飞速发展的时代,在硬件基础设施的不断升级以及虚拟化网络等技术的日益成熟下,云厂商也正面临着各种新技术带来的巨大挑战。从数据中心的基础建设到云平台的系统构建再到产品底...

UCloudTech
11分钟前
0
0
走进阿里云物联网

课程介绍: 阿里云IoT,致力于实现万物互联的美好世界,为生态合作伙伴提供基于云边端一体化、人工智能、安全的物联网基础平台和内容服务能力平台,通过该平台高效连接、管理设备的同时,开放...

mcy0425
19分钟前
0
0
Kylin2.5.0环境搭建及操作记录

Apache Kylin是一个开源的分布式分析引擎,提供Hadoop/Spark之上的SQL查询接口及多维分析(OLAP)能力以支持超大规模数据,最初由eBay Inc. 开发并贡献至开源社区。它能在亚秒内查询巨大的H...

PeakFang-BOK
28分钟前
2
0
SpringBoot整合es

文档对像 @Document(indexName = "bigdata",type = "tag")public class User { @Idprivate String openid; private List<String> tags;public String getOpenid() ......

魔法王者安琪拉
32分钟前
1
0
windows下让 jar 在后台运行的办法

windows下 运行 java jar 不出现 命令行 窗口 新建一个披处理 run.bat,内容如下 @echo off start javaw -jar xx.jar exit 双击运行即可。...

glen_xu
41分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部