原文發(fā)表于鳳凰花論壇：http://www.fenghuanghua.com/bbs/viewthread.php?tid=34&extra=page%3D1 有興趣的朋友可以在那里討論。 純真數(shù)據(jù)庫(kù)是國(guó)內(nèi)用的最多的ip-地理信息數(shù)據(jù)庫(kù)，雖然不怎么專業(yè)，但是數(shù)據(jù)蠻全的，數(shù)據(jù)結(jié)構(gòu)也比較合理。

關(guān)于純真數(shù)據(jù)庫(kù)的數(shù)據(jù)結(jié)構(gòu)，可以看一下lumaqq的文檔，里面有一點(diǎn)說(shuō)的不太清楚，就是里面的ip和地理信息不是一對(duì)一，是多對(duì)一，所以ip一般是ip段。查詢的時(shí)候是查詢ip地址落在哪個(gè)段。

純真數(shù)據(jù)庫(kù)的查詢算法也已經(jīng)有人實(shí)現(xiàn)了：http://www.survivalescaperooms.com/article/2008/4055.shtml

用的是線性表的二分查詢。

純真數(shù)據(jù)庫(kù)比較大，大約有60萬(wàn)的記錄，上面的算法基本上可以接受了，平均查詢效率在2ms左右，對(duì)于單機(jī)程序，完全可以忽略，但是對(duì)于并發(fā)比較大的系統(tǒng)，比如統(tǒng)計(jì)系統(tǒng)，這樣的效率還不夠。

既然數(shù)據(jù)是線性存儲(chǔ)的，那么就可以采用分段查詢，預(yù)先將數(shù)據(jù)隔成段，查詢時(shí)，先找到相應(yīng)的段，然后進(jìn)行二分查詢。

二分查詢的平均查找長(zhǎng)度是：lg(n+1)-1
那么分塊詢找+二分查詢的平均查找長(zhǎng)度就是：（設(shè)塊數(shù)為N）分塊也進(jìn)行二分查找，所以查找塊的平均長(zhǎng)度是lg(N+1)-1，每塊長(zhǎng)度是n/N ，所以最終長(zhǎng)度是：lg(N+1)-1 + lg(n/N+1)-1

根據(jù)上面的公式，代入n可以算出一個(gè)最佳塊數(shù)N，也就是最佳查詢時(shí)間了。數(shù)據(jù)量越大，查詢速度越快，數(shù)據(jù)量比較小的表就沒(méi)必要分塊了。

我高數(shù)學(xué)得不好，不知道對(duì)不對(duì)。請(qǐng)大蝦指正，另外幫忙算一下6249322條數(shù)據(jù)的最佳塊數(shù)。

修改后的代碼如下：（function separate($count)是我添加的分塊函數(shù)，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記錄的總條數(shù)（不包含版本信息記錄）
     *
     * @var int
     */
    var $totalip;

    /**
     * 返回讀取的長(zhǎng)整型數(shù)
     *
     * @access private
     * @return int
     */
    function getlong() {
        //將讀取的little-endian編碼的4個(gè)字節(jié)轉(zhuǎn)化為長(zhǎng)整型數(shù)
        $result = unpack('Vlong', fread($this->fp, 4));
        return $result['long'];
    }

    /**
     * 返回讀取的3個(gè)字節(jié)的長(zhǎng)整型數(shù)
     *
     * @access private
     * @return int
     */
    function getlong3() {
        //將讀取的little-endian編碼的3個(gè)字節(jié)轉(zhuǎn)化為長(zhǎng)整型數(shù)
        $result = unpack('Vlong', fread($this->fp, 3).chr(0));
        return $result['long'];
    }

    /**
     * 返回壓縮后可進(jìn)行比較的IP地址
     *
     * @access private
     * @param string $ip
     * @return string
     */
    function packip($ip) {
        // 將IP地址轉(zhuǎn)化為長(zhǎng)整型數(shù)，如果在PHP5中，IP地址錯(cuò)誤，則返回False，
        // 這時(shí)intval將Flase轉(zhuǎn)化為整數(shù)-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格式保存，以 主站蜘蛛池模板： 沁源县| 威信县| 白山市| 菏泽市| 仙居县| 青川县| 大关县| 揭东县| 黔南| 庆城县| 沧州市| 普宁市| 岳池县| 宁陕县| 昌平区| 鸡泽县| 沽源县| 张家港市| 金塔县| 手游| 昌都县| 禹城市| 柳林县| 京山县| 麦盖提县| 西和县| 阳东县| 清河县| 本溪市| 海阳市| 洱源县| 涞水县| 温宿县| 柏乡县| 怀柔区| 南丰县| 抚宁县| 米泉市| 公主岭市| 尼木县| 浪卡子县|