IP アドレスクエリにおける PHP 二分法の適用

データベースにはおそらく数十万の IP レコードが保存されており、レコード セットは次のとおりです:


---------- ---------- -- ----- ----- --------- -------- -------- --------
|
---------- ------------ --- ----- - -------- -------- --------
| 0 0 | | 16774431 | 33554432 | 50331648 | | 67108864 | 67829759 | | 0 | 0 |
- --------- -------- --------
このクエリを実行するには、次の SQL を使用する必要があります:
$sql = 'SELECT * FROM i_m_ip WHERE ip_begin <= $client_ip AND ip_end >= $client_ip';
?>
このような検索にはインデックスは必要ありません。 MySQL のクエリ効率が 1 秒あたり 500 回を超えることはほとんどありません。同時実行の最適化を何度も行いましたが、最終的な平均クエリ効率は 1 秒あたり 200 回程度しかなく、これは本当に頭の痛い問題でした。当初はInnocence IPライブラリの検索手法を利用することも考えましたが、アルゴリズムにずっと抵抗があり、二分法は難しいと思っていたため、利用するまでは至りませんでした。仕方なく、結局二分法でIPアドレスを取得する方法を実現しました。
上の表から、IP ライブラリは 0 から 4294967295 までの連続値であることがわかります。この値を分離して格納すると、数百 GB のデータが存在するため、インデックスやインデックスを使用する方法がありません。ハッシュする方法はありません。最終的に、データベースの取得はやめて、PHP を使用してこれらをバイナリ ストレージに変換しました。 IP の開始と終了の長さが 4 バイトの長整数で、以下の国 ID、州 ID などが 2 バイトの短整数を使用して格納できることがわかります。合計 1 行のデータがあります。 18 バイト、合計 31 万個のデータを合計しても、わずか 5M になります。具体的な IP ライブラリ生成コードは次のとおりです:
/*
IP ファイル形式:
3741319168 3758096383 182 0 0 0 0
3758096384 377487359 9 3 0 0 0 0
3774873600 4026531839 182 0 0 0
4026531840 4278190079 182 0 0 0
4294967040 42949672 95 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 = destroy("t", $buffer); ($buffer as $key => $value) {
$buffer[$key] = (float)rim($value)
$str = Pack('L', $buffer[0] ); ;
$str .= パック('L', $buffer[1]);
$str .= パック('S', $buffer[2]); 'S', $buffer[3]);
$str .= パック('S', $buffer[4]);
$str .= パック('S', $buffer[5] ); ;
$str .= Pack('S', $buffer[6]);
}
}

このように、IP は 18 バイト単位で順番に配置されているため、バイナリメソッドを使用して IP 情報を取得するのが簡単です。
function getip($ip, $fp) {
fseek($ fp, 0);
$begin = 0;
$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);

if ($end - $begin ($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）））;

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

fseek($fp, $middle_seek); = implode('', unpack('L', fread($fp, 4)));
$middle_ip = sprintf('%u', $middle_ip); if ($ip >) ;= $middle_ip) {
$begin )
}

上記の $fp は ip.dat を開くためのファイルハンドルです。ループ検索なので関数の外に記述します。取得ごとにファイルを 1 回開く必要がなく、30W 行データの二分法をループする必要があるのは最大 7 回 (2 ^ 7) だけです。正確な IP 情報を見つけることができます。当初、取得を高速化するために ip.dat をメモリに置きたかったのですが、後で文字列位置決め関数の効率がファイル ポインターのオフセット位置決めと同じ桁ではないことがわかりました。 IP ライブラリを保存するためにメモリを使用します。
この実装により、IP 検索の効率が 100 倍近く向上しました。これは、二分法を単純に適用しただけであり、それ以来、WEB アプリケーションではアルゴリズムは重要ではないという概念が完全に払拭されました。実際、これを達成するために、私も最初は純粋な形式で IP ライブラリを生成し、Discuz の IP クエリ機能を使用してそれを検索するのを手伝ってほしいと Jinhu にアドバイスを求めましたが、彼は私を助けることを拒否しました。そして最終的に私のこの実践と学習を作成しました。場合によっては、自分自身に求めるよりも、他人に求める方が良い場合があります。