Author：David |
English Version 【转载时请务必以超链接形式标明文章原始出处和作者信息及本声明】
URL：http://blog.iyi.cn/start/2007/04/ipphp.html 原文发表于凤凰花论坛：http://www.fenghuanghua.com/bbs/viewthread.php?tid=34&extra=page%3D1 有兴趣的朋友可以在那里讨论。 纯真数据库是国内用的最多的ip-地理信息数据库，虽然不怎么专业，但是数据蛮全的，数据结构也比较合理。
关于纯真数据库的数据结构，可以看一下lumaqq的文档，里面有一点说的不太清楚，就是里面的ip和地理信息不是一对一，是多对一，所以ip一般是ip段。查询的时候是查询ip地址落在哪个段。
纯真数据库的查询算法也已经有人实现了：http://www.coolcode.cn/?p=16
用的是线性表的二分查询。
纯真数据库比较大，大约有60万的记录，上面的算法基本上可以接受了，平均查询效率在2ms左右，对于单机程序，完全可以忽略，但是对于并发比较大的系统，比如统计系统，这样的效率还不够。
既然数据是线性存储的，那么就可以采用分段查询，预先将数据隔成段，查询时，先找到相应的段，然后进行二分查询。
二分查询的平均查找长度是：lg(n+1)-1
那么分块询找+二分查询的平均查找长度就是：（设块数为N）分块也进行二分查找，所以查找块的平均长度是lg(N+1)-1，每块长度是n/N ，所以最终长度是：lg(N+1)-1 + lg(n/N+1)-1
根据上面的公式，代入n可以算出一个最佳块数N，也就是最佳查询时间了。数据量越大，查询速度越快，数据量比较小的表就没必要分块了。
我高数学得不好，不知道对不对 请大虾指正，另外帮忙算一下6249322条数据的最佳块数。
修改后的代码如下：（function separate($count)是我添加的分块函数，if($separator){}所在部分是二分查找块）
<?php测试脚本：
/**
* IP 地理位置查询类
* 增加分块查询算法
*
* @author 马秉尧
* @version 1.5
* @copyright 2005 CoolCode.CN
* @modified by david blog:blog.iyi.cn bbs:www.fenghuanghua.com
*/
class IpLocation {
/**
* QQWry.Dat文件指针
*
* @var resource
*/
var $fp;
/**
* 第一条IP记录的偏移地址
*
* @var int
*/
var $firstip;
/**
* 最后一条IP记录的偏移地址
*
* @var int
*/
var $lastip;
/**
* IP记录的总条数（不包含版本信息记录）
*
* @var int
*/
var $totalip;
/**
* 返回读取的长整型数
*
* @access private
* @return int
*/
function getlong() {
//将读取的little-endian编码的4个字节转化为长整型数
$result = unpack('Vlong', fread($this->fp, 4));
return $result['long'];
}
/**
* 返回读取的3个字节的长整型数
*
* @access private
* @return int
*/
function getlong3() {
//将读取的little-endian编码的3个字节转化为长整型数
$result = unpack('Vlong', fread($this->fp, 3).chr(0));
return $result['long'];
}
/**
* 返回压缩后可进行比较的IP地址
*
* @access private
* @param string $ip
* @return string
*/
function packip($ip) {
// 将IP地址转化为长整型数，如果在PHP5中，IP地址错误，则返回False，
// 这时intval将Flase转化为整数-1，之后压缩成big-endian编码的字符串
return pack('N', intval($ip));
}
/**
* 返回读取的字符串
*
* @access private
* @param string $data
* @return string
*/
function getstring($data = "") {
while (ord($char = fread($this->fp, 1)) > 0) { // 字符串按照C格式保存，以/0结束
$data .= $char; // 将读取的字符连接到给定字符串之后
}
return $data;
}
/**
* 返回地区信息
*
* @access private
* @return string
*/
function getarea() {
$byte = fread($this->fp, 1); // 标志字节
switch (ord($byte)) {
case 0: // 没有区域信息
$area = "";
break;
case 1:
case 2: // 标志字节为1或2，表示区域信息被重定向
fseek($this->fp, $this->getlong3());
$area = $this->getstring();
break;
default: // 否则，表示区域信息没有被重定向
$area = $this->getstring($byte);
break;
}
return $area;
}
/**
* 将索引分成指定的块
*
* @access public
* @param int $count
* @return array
*/
function separate($count){
if (!$this->fp) return null; // 如果数据文件没有被正确打开，则直接返回空
$l = 0; // 搜索的下边界
$u = $this->totalip; // 搜索的上边界
$step = floor($u/$count);
for($i=0; $i<$count; $i++){
fseek($this->fp, $this->firstip + $i * $step * 7);
$separator[$i] = strrev(fread($this->fp, 4)); // 获取中间记录的开始IP地址
// strrev函数在这里的作用是将little-endian的压缩IP地址转化为big-endian的格式
}
return $separator;
}
/**
* 根据所给 IP 地址或域名返回所在地区信息
*
* @access public
* @param string $ip, array $separator
* @return array
*/
function getlocation($ip, $separator = 0) {
if (!$this->fp) return null; // 如果数据文件没有被正确打开，则直接返回空
$location['ip'] = ip2long($ip);
$ip = $this->packip($location['ip']); // 将输入的IP地址转化为可比较的IP地址
// 不合法的IP地址会被转化为255.255.255.255
$l = 0; // 搜索的下边界
$u = $this->totalip; // 搜索的上边界
$findip = $this->lastip; // 如果没有找到就返回最后一条IP记录（QQWry.Dat的版本信息）
if($separator){
$count = count($separator);
$step = floor($u/$count);
for($i=0; $i<$count-1; $j = floor(($count + $i) / 2)){//二分查找所在区间
if($i>1000)break;
if($ip<$separator[$j]){
if($ip>$separator[$j-1]){
$l = 1;
$i = $j;
$u = $j * $step;
break;
}else{
$count = $j;
}
}else{
$i = $j;
}
}
if($l){
$l = ($i-1)*$step;
}else{
$l = $i * $step;
}
}
while ($l <= $u) { // 当上边界小于下边界时，查找失败
$i = floor(($l + $u) / 2); // 计算近似中间记录
fseek($this->fp, $this->firstip + $i * 7);
$beginip = strrev(fread($this->fp, 4)); // 获取中间记录的开始IP地址
// strrev函数在这里的作用是将little-endian的压缩IP地址转化为big-endian的格式
// 以便用于比较，后面相同。
if ($ip < $beginip) { // 用户的IP小于中间记录的开始IP地址时
$u = $i - 1; // 将搜索的上边界修改为中间记录减一
}else{
fseek($this->fp, $this->getlong3());
$endip = strrev(fread($this->fp, 4)); // 获取中间记录的结束IP地址
if ($ip > $endip) { // 用户的IP大于中间记录的结束IP地址时
$l = $i + 1; // 将搜索的下边界修改为中间记录加一
} else { // 用户的IP在中间记录的IP范围内时
$findip = $this->firstip + $i * 7;
break; // 则表示找到结果，退出循环
}
}
}
//获取查找到的IP地理位置信息
fseek($this->fp, $findip);
$location['beginip'] = long2ip($this->getlong()); // 用户IP所在范围的开始地址
$offset = $this->getlong3();
fseek($this->fp, $offset);
$location['endip'] = long2ip($this->getlong()); // 用户IP所在范围的结束地址
$byte = fread($this->fp, 1); // 标志字节
switch (ord($byte)) {
case 1: // 标志字节为1，表示国家和区域信息都被同时重定向
$countryOffset = $this->getlong3(); // 重定向地址
fseek($this->fp, $countryOffset);
$byte = fread($this->fp, 1); // 标志字节
switch (ord($byte)) {
case 2: // 标志字节为2，表示国家信息又被重定向
fseek($this->fp, $this->getlong3());
$location['country'] = $this->getstring();
//fseek($this->fp, $countryOffset + 4);
//$location['area'] = $this->getarea();
break;
default: // 否则，表示国家信息没有被重定向
$location['country'] = $this->getstring($byte);
//$location['area'] = $this->getarea();
break;
}
break;
case 2: // 标志字节为2，表示国家信息被重定向
fseek($this->fp, $this->getlong3());
$location['country'] = $this->getstring();
//fseek($this->fp, $offset + 8);
//$location['area'] = $this->getarea();
break;
default: // 否则，表示国家信息没有被重定向
$location['country'] = $this->getstring($byte);
//$location['area'] = $this->getarea();
break;
}
if ($location['country'] == "纯真网络" || $location['country'] == " CZ88.NET") { // CZ88.NET表示没有有效信息
$location['country'] = "未知";
}
//if ($location['area'] == " CZ88.NET") {
// $location['area'] = "";
//}
return $location;
}
/**
* 构造函数，打开 QQWry.Dat 文件并初始化类中的信息
*
* @param string $filename
* @return IpLocation
*/
function IpLocation($filename = "QQWry.Dat") {
$this->fp = 0;
if (($this->fp = @fopen($filename, 'rb')) !== false) {
$this->firstip = $this->getlong();
$this->lastip = $this->getlong();
$this->totalip = ($this->lastip - $this->firstip) / 7;
//注册析构函数，使其在程序执行结束时执行
register_shutdown_function(array(&$this, '_IpLocation'));
}
}
/**
* 析构函数，用于在页面执行结束后自动关闭打开的文件。
*
*/
function _IpLocation() {
if ($this->fp) {
fclose($this->fp);
}
$this->fp = 0;
}
}
?>
<?php我的测试结果：
include('iplocation.php');
$ip = "66.249.72.235";
$iplocation = new IpLocation();
$separator = $iplocation->separate(1000);//分成1000块
$mtime = explode(' ', microtime());
$starttime = $mtime[1] + $mtime[0];
$location = $iplocation->getlocation($ip);//没有分块的查询
$mtime = explode(' ', microtime());
$endtime = $mtime[1] + $mtime[0];
var_dump($endtime-$starttime);
$mtime = explode(' ', microtime());
$starttime = $mtime[1] + $mtime[0];
$location = $iplocation->getlocation($ip, $separator);//含有分块的查询
$mtime = explode(' ', microtime());
$endtime = $mtime[1] + $mtime[0];
var_dump($endtime-$starttime);
//
?>
float 0.00144290924072
float 0.000945091247559
单一数据，没有普遍性，有兴趣的同学可以随机生成些数据试试。
分块是需要缓存的，不然每次分块的时间也是很长的，有兴趣的同学可以实现一下。另外，计算最佳分块的方法也可以加进去。