suchen
Heimphp教程php手册php二分法在IP地址查询中的应用

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

Jun 13, 2016 pm 12:27 PM
phpzweiexistierenAdressabfrage存储应用数据库记录

数据库大概存储几十万条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

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
3 Wochen vorBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Beste grafische Einstellungen
3 Wochen vorBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. So reparieren Sie Audio, wenn Sie niemanden hören können
3 Wochen vorBy尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: Wie man alles in Myrise freischaltet
4 Wochen vorBy尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

MantisBT

MantisBT

Mantis ist ein einfach zu implementierendes webbasiertes Tool zur Fehlerverfolgung, das die Fehlerverfolgung von Produkten unterstützen soll. Es erfordert PHP, MySQL und einen Webserver. Schauen Sie sich unsere Demo- und Hosting-Services an.

MinGW – Minimalistisches GNU für Windows

MinGW – Minimalistisches GNU für Windows

Dieses Projekt wird derzeit auf osdn.net/projects/mingw migriert. Sie können uns dort weiterhin folgen. MinGW: Eine native Windows-Portierung der GNU Compiler Collection (GCC), frei verteilbare Importbibliotheken und Header-Dateien zum Erstellen nativer Windows-Anwendungen, einschließlich Erweiterungen der MSVC-Laufzeit zur Unterstützung der C99-Funktionalität. Die gesamte MinGW-Software kann auf 64-Bit-Windows-Plattformen ausgeführt werden.

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Leistungsstarke integrierte PHP-Entwicklungsumgebung

EditPlus chinesische Crack-Version

EditPlus chinesische Crack-Version

Geringe Größe, Syntaxhervorhebung, unterstützt keine Code-Eingabeaufforderungsfunktion

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung