Heim >Backend-Entwicklung >PHP-Tutorial >php二分法在IP地址查询中的应用_PHP

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

WBOY
WBOYOriginal
2016-06-01 12:24:41786Durchsuche

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

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn