PHP的實現一個高效的數據庫（文件存儲，NOSQL）

下文為各位整理一個PHP的實現一個高效的數據庫（文件存儲，NOSQL）的例子，希望對各位有幫助。

 用文件的方式讀寫，一個文件是索引文件，另一個文件是真實的數據文件。
索引文件分為2部分，第一部分是所有的指針，記錄第二部分的位置；第二部分是索引記錄。所有的索引指針：是記錄所有相同Hash值的key的指針，它是一個鏈表結構，記錄在數據文件的位置和同key的下一個值。
索引記錄中：每條記錄有四部分，第一部分4個字節，是下一條索引的偏移量；第二部分是該記錄的key，128字節；第三部分是數據偏移量，4個字節；第四部分是數據記錄長度，4個字節。
我們設定文件的存儲上限為262144個。

查找流程如下：

1、根據key算出hash值，獲取該hash值的鏈表在索引文件的第一部分（所有指針區）的位置。
2、根據步驟一的位置，獲取值，時間復雜度O(1)；
2、根據步驟一中的值，找到索引文件中第二部分（索引記錄）的位置，也就是和key相同hash值的所有指針的鏈表。順著鏈表查找該key，獲取該key在鏈表中存放的數據，數據只包含該key在索引文件中的位置，時間復雜度為O(n)；
3、根據步驟二所獲取的key在索引文件位置，得到索引文件中存放該key的信息。信息包含在真實數據文件中存放真實數據的位置。
4、根據步驟三所獲取的位置，在真實數據文件中獲取數據，並返回給應用程序。

測試結果：插入10000條耗時：793ms。查找10000條耗時：149ms。雖然這效率只有Redis的十分之一。。。但是請不要在意這些細節。。。

代碼做了注釋，上述文字有些亂。代碼只實現三個方法，一個插入（如果存在則跳過），一個是查找，一個是刪除。

思路來源：《PHP核心技術與最佳實踐》一書。尊重作者，轉載請保留該書名。

 代碼如下 復制代碼

<?php
//Hash表中的元素指針個數，每個指針都是int，存儲hash鏈表的文件偏移量
define('DB_BUCKET_SIZE', 262144);
//每條記錄的key的長度
define('DB_KEY_SIZE', 128);
//一條索引記錄的長度
define('DB_INDEX_SIZE', DB_KEY_SIZE + 12);

//成功-返回碼
define('DB_SUCCESS', 1);
//失敗-返回碼
define('DB_FAILURE', -1);
//key重復-返回碼
define('DB_KEY_EXISTS', -2);

class DB{
    private $idx_fp;
    private $dat_fp;
    private $closed;

    /**
     * Description: 打開數據庫
     * @param $pathName 數據文件的存放路徑
     * @return mixed
     */
    public function open($pathName){
        $idx_path = $pathName . '.idx';
        $dat_path = $pathName . '.dat';
        if(!file_exists($idx_path)){
            $init = true;
            $mode = "w+b";
        }else{
            $init = false;
            $mode = 'r+b';
        }
        $this->idx_fp = fopen($idx_path, $mode);
        if(!$this->idx_fp){
            return DB_FAILURE;
        }
        if($init){
            //把0x00000000轉換成無符號長整型的二進制
            $elem = pack('L', 0x00000000);
            for($i=0; $i< DB_BUCKET_SIZE; $i++){
                fwrite($this->idx_fp, $elem, 4);
            }
        }
        $this->dat_fp = fopen($dat_path, $mode);
        if(!$this->dat_fp){
            return DB_FAILURE;
        }

        return DB_SUCCESS;
    }

    /**
     * Description: Times33 Hash算法
     * @param $key
     * @return int
     */
    private function times33Hash($key){
        $len = 8;
        $key = substr(md5($key), 0, $len);
        $hash = 0;
        for($i=0; $i<$len; $i++){
            $hash += 33 * $hash + ord($key[$i]);
        }
        //0x7FFFFFFF：一個十六進制的數是4bit，8個就是32位，就是4字節，和一個int一樣大。而F是1111，7是0111，那麼這個十六進制的數就是頭為0，其余為1的，首位是符號位，也就是說7fffffff是最大的整數。
        //& 0x7fffffff 可以保證返回的數是正整數
        return $hash & 0x7FFFFFFF;
    }

    /**
     * Description: 插入記錄
     * @param $key
     * @param $value
     */
    public function add($key, $value){
        $offset = ($this->times33Hash($key) % DB_BUCKET_SIZE) * 4;

        $idxoff = fstat($this->idx_fp);
        $idxoff = intval($idxoff['size']);

        $datoff = fstat($this->dat_fp);
        $datoff = intval($datoff['size']);

        $keylen = strlen($key);
        $vallen = strlen($value);
        if($keylen > DB_KEY_SIZE){
            return DB_FAILURE;
        }
        //0表示這是最後一個記錄，該鏈再無其他記錄。
        $block = pack('L', 0x00000000);
        //鍵值
        $block .= $key;
        //如果鍵值的長度沒有達到最大長度，則用0填充
        $space = DB_KEY_SIZE - $keylen;
        for($i=0; $i<$space; $i++){
            $block .= pack('C', 0x00);
        }
        //數據所在文件的偏移量
        $block .= pack('L', $datoff);
        //數據記錄的長度
        $block .= pack('L', $vallen);
        //盡管SEEK_SET是默認值，但是顯式聲明了就不怕以後官方會改變了-.-
        fseek($this->idx_fp, $offset, SEEK_SET);
        //檢測該key所對應的hash值是否存在了
        $pos = @unpack('L', fread($this->idx_fp, 4));
        $pos = $pos[1];
        //如果key不存在
        if($pos == 0){
            fseek($this->idx_fp, $offset, SEEK_SET);
            fwrite($this->idx_fp, pack('L', $idxoff), 4);

            fseek($this->idx_fp, 0, SEEK_END);
            fwrite($this->idx_fp, $block, DB_INDEX_SIZE);

            fseek($this->dat_fp, 0, SEEK_END);
            fwrite($this->dat_fp, $value, $vallen);

            return DB_SUCCESS;
        }
        //如果key存在
        $found = false;
        while($pos){
            fseek($this->idx_fp, $pos, SEEK_SET);
            $tmp_block = fread($this->idx_fp, DB_INDEX_SIZE);
            $cpkey = substr($tmp_block, 4, DB_KEY_SIZE);
            //$cpkey==$key時返回0，小於返回負數，大於返回正數
            if(!strncmp($cpkey, $key, $keylen)){
                $dataoff = unpack('L', substr($tmp_block, DB_KEY_SIZE + 4, 4));
                $dataoff = $dataoff[1];
                $datalen = unpack('L', substr($tmp_block, DB_KEY_SIZE + 8, 4));
                $datalen = $datalen[1];
                $found = true;
                break;
            }
            $prev = $pos;
            $pos = @unpack('L', substr($tmp_block, 0, 4));
            $pos = $pos[1];
        }

        if($found){
            return DB_KEY_EXISTS;
        }
        fseek($this->idx_fp, $prev, SEEK_SET);
        fwrite($this->idx_fp, pack('L', $idxoff), 4);
        fseek($this->idx_fp, 0, SEEK_END);
        fwrite($this->idx_fp, $block, DB_INDEX_SIZE);
        fseek($this->dat_fp, 0, SEEK_END);
        fwrite($this->dat_fp, $value, $vallen);
        return DB_SUCCESS;
    }

    /**
     * Description: 查詢一條記錄
     * @param $key
     */
    public function get($key){
        //計算偏移量，key的hash值對索引文件的大小求模，再乘4。因為每個鏈表指針大小為4
        $offset = ($this->times33Hash($key) % DB_BUCKET_SIZE) * 4;
        //SEEK_SET是默認的
        fseek($this->idx_fp, $offset, SEEK_SET);
        $pos = unpack('L', fread($this->idx_fp, 4));
        $pos = $pos[1];

        $found = false;
        while($pos){
            fseek($this->idx_fp, $pos, SEEK_SET);
            $block = fread($this->idx_fp, DB_INDEX_SIZE);
            $cpkey = substr($block, 4, DB_KEY_SIZE);

            if(!strncmp($key, $cpkey, strlen($key))){
                $dataoff = unpack('L', substr($block, DB_KEY_SIZE + 4, 4));
                $dataoff = $dataoff[1];

                $datalen = unpack('L', substr($block, DB_KEY_SIZE + 8, 4));
                $datalen = $datalen[1];

                $found = true;
                break;
            }
            $pos = unpack('L', substr($block, 0, 4));
            $pos = $pos[1];
        }
        if(!$found){
            return null;
        }
        fseek($this->dat_fp, $dataoff, SEEK_SET);
        $data = fread($this->dat_fp, $datalen);
        return $data;
    }

    /**
     * Description: 刪除
     * @param $key
     */
    public function delete($key){
        $offset = ($this->times33Hash($key) % DB_BUCKET_SIZE) * 4;
        fseek($this->idx_fp, $offset, SEEK_SET);
        $head = unpack('L', fread($this->idx_fp, 4));
        $head = $head[1];
        $curr = $head;
        $prev = 0;
        $found = false;
        while($curr){
            fseek($this->idx_fp, $curr, SEEK_SET);
            $block = fread($this->idx_fp, DB_INDEX_SIZE);

            $next = unpack('L', substr($block, 0, 4));
            $next = $next[1];

            $cpkey = substr($block, 4, DB_KEY_SIZE);
            if(!strncmp($key, $cpkey, strlen($key))){
                $found = true;
                break;
            }
            $prev = $curr;
            $curr = $next;
        }
        if(!$found){
            return DB_FAILURE;
        }
        //刪除索引文件。
        if($prev == 0){
            fseek($this->idx_fp, $offset, SEEK_SET);
            fwrite($this->idx_fp, pack('L', $next), 4);
        }else{
            fseek($this->idx_fp, $prev, SEEK_SET);
            fwrite($this->idx_fp, pack('L', $next), 4);
        }
        return DB_SUCCESS;
    }

    public function close(){
        if(!$this->closed){
            fclose($this->idx_fp);
            fclose($this->dat_fp);
            $this->closed = true;
        }
    }
}
?>

測試，測試添加一萬條和查找一萬條：

 代碼如下 復制代碼

<?php
//先include上面的類。。如果在同一個文件中就不用了。
//測試
$db = new DB();
$db->open('/var/www/data/');

$startTime = microtime(true);

//插入測試...插入10000條：成功，耗時： 793.48206520081ms
//for($i=0; $i<10000; $i++){
//    $db->add('key'.$i, 'value'.$i);
//}

//查找測試...查找10000條：成功，耗時： 149.08313751221ms
for($i=0; $i<10000; $i++){
    $db->get('key'.$i);
}

$endTime = microtime(true);
echo '成功，耗時： ' . (($endTime - $startTime)*1000) . 'ms';
$db->close();
?>