php二分法在IP地址查询中的应用
php二分法在IP地址查询中的应用
发布时间:2016-12-29 来源:查字典编辑
摘要:数据库大概存储几十万条IP记录,记录集如下:+----------+----------+------------+---------+--...

数据库大概存储几十万条IP记录,记录集如下:

+----------+----------+------------+---------+---------+--------+--------+

|ip_begin|ip_end|country_id|prov_id|city_id|isp_id|netbar|

+----------+----------+------------+---------+---------+--------+--------+

|0|16777215|2|0|0|0|0|

|16777216|33554431|2|0|0|0|0|

|33554432|50331647|2|0|0|0|0|

|50331648|67108863|3|0|0|0|0|

|67108864|67829759|3|0|0|0|0|

+----------+----------+------------+---------+---------+--------+--------+

这样做查询需要用到如下SQL:

<?php

$sql='SELECT*FROMi_m_ipWHEREip_begin<=$client_ipANDip_end>=$client_ip';

?>

这样的检索显然用不到索引,即使用到,MySQL查询效率也不大可能达到每秒500次以上,我做了很多并发优化,最终平均查询效率也只有每秒200次左右,实在是头痛。一开始我也有想到借鉴纯真IP库的检索方法,但是我一直对算法有抵触,也以为二分法很难,所以就没有尝试使用,直到最后没有办法了,才最终实现了二分法的IP地址检索。

从上表可以看到IP库是从0到4294967295的一个连续数值,这个数值要是拆开存储,会有几百G的数据,所以没办法使用索引也没办法哈希。最终我使用PHP将这些东东转为二进制存储,抛弃了数据库的检索。可以看到IP起止长度为一个4字节的长整型,后面的国家ID、省份ID等,可以使用2个字节的短整型来存储,总共一行数据就有18个字节,总共31万条数据,算起来也就5M的样子。具体IP库生成代码如下:

<?php

/*

IP文件格式:

374131916837580963831820000

3758096384377487359930000

377487360040265318391820000

402653184042781900791820000

429496704042949672953120000

*/

set_time_limit(0);

$handle=fopen('./ip.txt','rb');

$fp=fopen("./ip.dat",'ab');

if($handle){

while(!feof($handle)){

$buffer=fgets($handle);

$buffer=trim($buffer);

$buffer=explode("t",$buffer);

foreach($bufferas$key=>$value){

$buffer[$key]=(float)trim($value);

}

$str=pack('L',$buffer[0]);

$str.=pack('L',$buffer[1]);

$str.=pack('S',$buffer[2]);

$str.=pack('S',$buffer[3]);

$str.=pack('S',$buffer[4]);

$str.=pack('S',$buffer[5]);

$str.=pack('S',$buffer[6]);

fwrite($fp,$str);

}

}

?>

这样IP就按照顺序每18字节一个单位排列了,所以很容易就使用二分法来检索出IP信息:

functiongetip($ip,$fp){

fseek($fp,0);

$begin=0;

$end=filesize('./ip.dat');

$begin_ip=implode('',unpack('L',fread($fp,4)));

fseek($fp,$end-14);

$end_ip=implode('',unpack('L',fread($fp,4)));

$begin_ip=sprintf('%u',$begin_ip);

$end_ip=sprintf('%u',$end_ip);

do{

if($end-$begin<=18){

fseek($fp,$begin+8);

$info=array();

$info[0]=implode('',unpack('S',fread($fp,2)));

$info[1]=implode('',unpack('S',fread($fp,2)));

$info[2]=implode('',unpack('S',fread($fp,2)));

$info[3]=implode('',unpack('S',fread($fp,2)));

$info[4]=implode('',unpack('S',fread($fp,2)));

return$info;

}

$middle_seek=ceil((($end-$begin)/18)/2)*18+$begin;

fseek($fp,$middle_seek);

$middle_ip=implode('',unpack('L',fread($fp,4)));

$middle_ip=sprintf('%u',$middle_ip);

if($ip>=$middle_ip){

$begin=$middle_seek;

}else{

$end=$middle_seek;

}

}while(true);

}

以上$fp为打开ip.dat的文件句柄,由于是循环检索,所以写在函数外面,免得每次检索都要打开一次文件,30W行数据二分法最多也只需要循环7次(2^7)左右即可找到准确的IP信息。之后本来还想将ip.dat放在内存中加快检索速度,后来发现,字符串定位函数的效率,根本和文件指针的偏移定位不是在一个数量级的,所以还是放弃使用内存来存放IP库。

这个实现,使IP检索效率提高了近百倍,只是一个简单的二分法的应用,从此算法在WEB应用中不重要的观念彻底打消了。其实要实现这个,我还请教了金狐,我一开始是请他帮我生成一个纯真格式的IP库,然后用Discuz的IP查询函数来检索,不过他不肯帮我,最后造就了我的这个实践和学习。有时候,求人不如求己。

推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关阅读
网友关注
最新php教程学习
热门php教程学习
编程开发子分类