php二分法在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 * FROM i_m_ip WHERE ip_begin <= $client_ip AND ip_end >= $client_ip'; 
?> 
　　这样的检索显然用不到索引，即使用到，MySQL查询效率也不大可能达到每秒500次以上，我做了很多并发优化，最终平均查询效率也只有每秒200次左右，实在是头痛。一开始我也有想到借鉴纯真IP库的检索方法，但是我一直对算法有抵触，也以为二分法很难，所以就没有尝试使用，直到最后没有办法了，才最终实现了二分法的IP地址检索。 
　　从上表可以看到IP库是从0到4294967295的一个连续数值，这个数值要是拆开存储，会有几百G的数据，所以没办法使用索引也没办法哈希。最终我使用PHP将这些东东转为二进制存储，抛弃了数据库的检索。可以看到IP起止长度为一个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查询函数来检索，不过他不肯帮我，最后造就了我的这个实践和学习。有时候，求人不如求己。 

上一个：PHP中$_SERVER的详细参数与说明
下一个：phpmyadmin的安装与使用图文教程第1/2页