Application of PHP dichotomy in IP address query_PHP tutorial-PHP Tutorial-php.cn

Application of PHP dichotomy in IP address query_PHP tutorial

WBOY

Release： 2016-07-21 15:50:36

Original

810 people have browsed it

The database probably stores hundreds of thousands of IP records, and the record set is as follows:

+----------+----------+---- --------+---------+---------+--------+--------+
| ip_begin | ip_end | country_id | prov_id | city_id | isp_id | netbar |
+-----------+-----------+---------- ---+---------+---------+--------+--------+
| 0 | 16777215 | 2 | 0 | 0 | 0 |
| 16777216 | 33554431 | 2 | 0 | 0 |
| 33554432 | 50331647 | 2 | 0 | 0 | 0 | 0 |
| 50331648 | 67108863 | 3 | 0 | 0 | 0 |
| 67108864 | 67829759 | 3 | 0 | 0 0 | 0 |
+----------+--- -------+------------+---------+---------+--------+ --------+
To do this query, you need to use the following SQL:
$sql = 'SELECT * FROM i_m_ip WHERE ip_begin <= $client_ip AND ip_end > = $client_ip';
?>
Such a retrieval obviously does not use an index. Even if it is used, the MySQL query efficiency is unlikely to reach more than 500 times per second. I have done a lot of concurrency optimization, and finally the average The query efficiency is only about 200 times per second, which is really a headache. At the beginning, I also thought of using the retrieval method of the Innocence IP library, but I have always been resistant to the algorithm and thought that the dichotomy method was difficult, so I did not try to use it. It was not until I had no choice in the end that I finally realized the dichotomy IP address retrieval method. .
From the above table, you can see that the IP library is a continuous value from 0 to 4294967295. If this value is separated and stored, there will be hundreds of gigabytes of data, so there is no way to use indexes and no way to hash. In the end, I used PHP to convert these things into binary storage, abandoning database retrieval. You can see that the starting and ending length of the IP is a 4-byte long integer. The following country ID, province ID, etc. can be stored using a 2-byte short integer. A total of one row of data has 18 bytes, a total of 31 Ten thousand pieces of data only add up to 5M.The specific IP library generation code is as follows:
/*
IP file format:
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 = 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);
}
}
?>

In this way, the IPs are arranged in units of 18 bytes in order, so it is easy to use the binary method to retrieve the IP information:
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) {
                                                                                                                                                                     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)));

$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) {
                                                            (true);
}

The above $fp is the file handle to open ip.dat. Since it is a loop retrieval, it is written outside the function to avoid opening the file once for each retrieval. The 30W row data dichotomy only needs to be looped 7 times at most ( You can find accurate IP information in about 2^7). Later, I originally wanted to put ip.dat in the memory to speed up the retrieval. Later I found that the efficiency of the string positioning function was not at the same order of magnitude as the offset positioning of the file pointer, so I gave up using memory to store the IP library.
This implementation has improved the IP retrieval efficiency by nearly a hundred times. It is just a simple application of the dichotomy. From then on, the concept that the algorithm is not important in WEB applications has been completely dispelled. In fact, to achieve this, I also asked Jinhu for advice. I initially asked him to help me generate an IP library in a pure format, and then use Discuz’s IP query function to search for it. However, he refused to help me, and finally created my This practice and learning. Sometimes, it is better to ask for others than to ask for yourself.

http://www.bkjia.com/PHPjc/319312.html