|
原文发表于凤凰花论坛：http://www.fenghuanghua.com/bbs/viewthread.php?tid=34&extra=page%3D1 有兴趣的朋友可以在那里讨论。 纯真数据库是国内用的最多的ip-地理信息数据库，虽然不怎么专业，但是数据蛮全的，数据结构也比较合理。
关于纯真数据库的数据结构，可以看一下lumaqq的文档，里面有一点说的不太清楚，就是里面的ip和地理信息不是一对一，是多对一，所以ip一般是ip段。查询的时候是查询ip地址落在哪个段。
纯真数据库的查询算法也已经有人实现了：http://www.itlearner.com/article/2008/4055.shtml
用的是线性表的二分查询。
纯真数据库比较大，大约有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',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格式保存，以 （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
