网站运营 | 站长学院 | 技术文档 | 成语 | 歇后语 | 桌面壁纸 | 帝国时代 | 代码收藏 | IP地址查询 | 生活百科 | 生日密码 | CSS压缩 | 用户评论

php二分法在IP地址查询中的应用

【 更新时间:2011-04-05 | 字体:
[导读]数据库大概存储几十万条IP记录>,记录集如下: +----------+----------+------------+---------+---------+--------+--------+ | ip_begin | ip_end | country_id | prov_id | city_id | isp_id | netbar | +--------...

数据库大概存储几十万条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 * FROM i_m_ip WHERE ip_begin <= $client_ip AND ip_end >= $client_ip';
?>
  这样的检索显然用不到索引,即使用到,MySQL查询效率也不大可能达到每秒500次以上<,我做了很多并发优化><,最终平均查询效率也只有每秒200次左右>,实在是头痛。一开始我也有想到借鉴纯真IP库的检索方法,但是我一直对算法有抵触,也以为二分法很难>,所以就没有尝试使用,直到最后没有办法了,才最终实现了二分法的IP地址检索。
  从上表可以看到IP库是从0到4294967295的一个连续数值<,这个数值要是拆开存储>,会有几百G的数据>,所以没办法使用索引也没办法哈希>。最终我使用PHP将这些东东转为二进制存储<,抛弃了数据库的检索?>?梢钥吹絀P起止长度为一个4字节的长整型>,后面的国家ID>、省份ID等,可以使用2个字节的短整型来存储<,总共一行数据就有18个字节,总共31万条数据,算起来也就5M的样子<。具体IP库生成代码如下:
<?php
/*
IP文件格式:
3741319168 3758096383 182 0 0 0 0
3758096384 3774873599 3 0 0 0 0
3774873600 4026531839 182 0 0 0 0
4026531840 4278190079 182 0 0 0 0
4294967040 4294967295 312 0 0 0 0
*/
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 ($buffer as $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信息:
function getip($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查询函数来检索>,不过他不肯帮我,最后造就了我的这个实践和学习>。有时候<,求人不如求己。

友荐云推荐
  • 转载请注明来源:网站运营 网址:http://www.chinawobo.com/ 向您的朋友推荐此文章
  • 特别声明: 本站除部分特别声明禁止转载的专稿外的其他文章可以自由转载,但请务必注明出处和原始作者<>。文章版权归文章原始作者所有。对于被本站转载文章的个人和网站,我们表示深深的谢意。如果本站转载的文章有版权问题请联系我们,我们会尽快予以更正。
RSS订阅
  • QQ邮箱
  • 填写您的邮件地址,订阅我们的精彩内容:
更多
© 2014 网站运营 - T086.com(原itlearner.com)
微商货源 | 冠珠陶瓷 | 迪威乐云商devmsn | 易奇八字 | wwe美国职业摔角 | 八字算命 | 河南旅游景点大全 |
RunTime:6.02ms QueryTime:7