当前位置:首页 > PHP教程 > php应用 > 列表

PHP的实现一个高效的数据库(文件存储,NOSQL)

发布:smiling 来源: PHP粉丝网  添加日期:2015-12-12 14:57:40 浏览: 评论:0 

下文为各位整理一个PHP的实现一个高效的数据库(文件存储,NOSQL)的例子,希望对各位有帮助。

用文件的方式读写,一个文件是索引文件,另一个文件是真实的数据文件。

索引文件分为2部分,第一部分是所有的指针,记录第二部分的位置;第二部分是索引记录。所有的索引指针:是记录所有相同Hash值的key的指针,它是一个链表结构,记录在数据文件的位置和同key的下一个值。

索引记录中:每条记录有四部分,第一部分4个字节,是下一条索引的偏移量;第二部分是该记录的key,128字节;第三部分是数据偏移量,4个字节;第四部分是数据记录长度,4个字节。

我们设定文件的存储上限为262144个。

查找流程如下:

1、根据key算出hash值,获取该hash值的链表在索引文件的第一部分(所有指针区)的位置。

2、根据步骤一的位置,获取值,时间复杂度O(1);

3、根据步骤一中的值,找到索引文件中第二部分(索引记录)的位置,也就是和key相同hash值的所有指针的链表。顺着链表查找该key,获取该key在链表中存放的数据,数据只包含该key在索引文件中的位置,时间复杂度为O(n);

4、根据步骤二所获取的key在索引文件位置,得到索引文件中存放该key的信息。信息包含在真实数据文件中存放真实数据的位置。

5、根据步骤三所获取的位置,在真实数据文件中获取数据,并返回给应用程序。

测试结果:插入10000条耗时:793ms。查找10000条耗时:149ms。虽然这效率只有Redis的十分之一。。。但是请不要在意这些细节。。。

代码做了注释,上述文字有些乱。代码只实现三个方法,一个插入(如果存在则跳过),一个是查找,一个是删除。

思路来源:《PHP核心技术与最佳实践》一书。尊重作者,转载请保留该书名,代码如下:

  1. <?php 
  2. //Hash表中的元素指针个数,每个指针都是int,存储hash链表的文件偏移量 
  3. define('DB_BUCKET_SIZE', 262144); 
  4. //每条记录的key的长度 
  5. define('DB_KEY_SIZE', 128); 
  6. //一条索引记录的长度 
  7. define('DB_INDEX_SIZE', DB_KEY_SIZE + 12); 
  8.  
  9. //成功-返回码 
  10. define('DB_SUCCESS', 1); 
  11. //失败-返回码 
  12. define('DB_FAILURE', -1); 
  13. //key重复-返回码 
  14. define('DB_KEY_EXISTS', -2); 
  15.  
  16. class DB{ 
  17.     private $idx_fp
  18.     private $dat_fp
  19.     private $closed
  20.  
  21.     /** 
  22.      * Description: 打开数据库 
  23.      * @param $pathName 数据文件的存放路径 
  24.      * @return mixed 
  25.      */ 
  26.     public function open($pathName){ 
  27.         $idx_path = $pathName . '.idx'
  28.         $dat_path = $pathName . '.dat'
  29.         if(!file_exists($idx_path)){ 
  30.             $init = true; 
  31.             $mode = "w+b"
  32.         }else
  33.             $init = false; 
  34.             $mode = 'r+b'
  35.         } 
  36.         $this->idx_fp = fopen($idx_path$mode); 
  37.         if(!$this->idx_fp){ 
  38.             return DB_FAILURE; 
  39.         } 
  40.         if($init){ 
  41.             //把0x00000000转换成无符号长整型的二进制 
  42.             $elem = pack('L', 0x00000000); 
  43.             for($i=0; $i< DB_BUCKET_SIZE; $i++){ 
  44.                 fwrite($this->idx_fp, $elem, 4); 
  45.             } 
  46.         } 
  47.         $this->dat_fp = fopen($dat_path$mode); 
  48.         if(!$this->dat_fp){ 
  49.             return DB_FAILURE; 
  50.         } 
  51.  
  52.         return DB_SUCCESS; 
  53.     } 
  54.  
  55.     /** 
  56.      * Description: Times33 Hash算法 
  57.      * @param $key 
  58.      * @return int 
  59.      */ 
  60.     private function times33Hash($key){ 
  61.         $len = 8; 
  62.         $key = substr(md5($key), 0, $len); 
  63.         $hash = 0; 
  64.         for($i=0; $i<$len$i++){ 
  65.             $hash += 33 * $hash + ord($key[$i]); 
  66.         } 
  67.         //0x7FFFFFFF:一个十六进制的数是4bit,8个就是32位,就是4字节,和一个int一样大。而F是1111,7是0111,那么这个十六进制的数就是头为0,其余为1的,首位是符号位,也就是说7fffffff是最大的整数。 
  68.         //& 0x7fffffff 可以保证返回的数是正整数 
  69.         return $hash & 0x7FFFFFFF; 
  70.     } 
  71.  
  72.     /** 
  73.      * Description: 插入记录 
  74.      * @param $key 
  75.      * @param $value 
  76.      */ 
  77.     public function add($key$value){ 
  78.         $offset = ($this->times33Hash($key) % DB_BUCKET_SIZE) * 4; 
  79.  
  80.         $idxoff = fstat($this->idx_fp); 
  81.         $idxoff = intval($idxoff['size']); 
  82.  
  83.         $datoff = fstat($this->dat_fp); 
  84.         $datoff = intval($datoff['size']); 
  85.  
  86.         $keylen = strlen($key); 
  87.         $vallen = strlen($value); 
  88.         if($keylen > DB_KEY_SIZE){ 
  89.             return DB_FAILURE; 
  90.         } 
  91.         //0表示这是最后一个记录,该链再无其他记录。 
  92.         $block = pack('L', 0x00000000); 
  93.         //键值 
  94.         $block .= $key
  95.         //如果键值的长度没有达到最大长度,则用0填充 
  96.         $space = DB_KEY_SIZE - $keylen
  97.         for($i=0; $i<$space$i++){ 
  98.             $block .= pack('C', 0x00); 
  99.         } 
  100.         //数据所在文件的偏移量 
  101.         $block .= pack('L'$datoff); 
  102.         //数据记录的长度 
  103.         $block .= pack('L'$vallen); 
  104.         //尽管SEEK_SET是默认值,但是显式声明了就不怕以后官方会改变了-.- 
  105.         fseek($this->idx_fp, $offset, SEEK_SET); 
  106.         //检测该key所对应的hash值是否存在了 
  107.         $pos = @unpack('L'fread($this->idx_fp, 4)); 
  108.         $pos = $pos[1]; 
  109.         //如果key不存在 
  110.         if($pos == 0){ 
  111.             fseek($this->idx_fp, $offset, SEEK_SET); 
  112.             fwrite($this->idx_fp, pack('L'$idxoff), 4); 
  113.  
  114.             fseek($this->idx_fp, 0, SEEK_END); 
  115.             fwrite($this->idx_fp, $block, DB_INDEX_SIZE); 
  116.  
  117.             fseek($this->dat_fp, 0, SEEK_END); 
  118.             fwrite($this->dat_fp, $value$vallen); 
  119.  
  120.             return DB_SUCCESS; 
  121.         } 
  122.         //如果key存在 
  123.         $found = false; 
  124.         while($pos){ 
  125.             fseek($this->idx_fp, $pos, SEEK_SET); 
  126.             $tmp_block = fread($this->idx_fp, DB_INDEX_SIZE); 
  127.             $cpkey = substr($tmp_block, 4, DB_KEY_SIZE); 
  128.             //$cpkey==$key时返回0,小于返回负数,大于返回正数 
  129.             if(!strncmp($cpkey$key$keylen)){ 
  130.                 $dataoff = unpack('L'substr($tmp_block, DB_KEY_SIZE + 4, 4)); 
  131.                 $dataoff = $dataoff[1]; 
  132.                 $datalen = unpack('L'substr($tmp_block, DB_KEY_SIZE + 8, 4)); 
  133.                 $datalen = $datalen[1]; 
  134.                 $found = true; 
  135.                 break
  136.             } 
  137.             $prev = $pos
  138.             $pos = @unpack('L'substr($tmp_block, 0, 4)); 
  139.             $pos = $pos[1]; 
  140.         } 
  141.  
  142.         if($found){ 
  143.             return DB_KEY_EXISTS; 
  144.         } 
  145.         fseek($this->idx_fp, $prev, SEEK_SET); 
  146.         fwrite($this->idx_fp, pack('L'$idxoff), 4); 
  147.         fseek($this->idx_fp, 0, SEEK_END); 
  148.         fwrite($this->idx_fp, $block, DB_INDEX_SIZE); 
  149.         fseek($this->dat_fp, 0, SEEK_END); 
  150.         fwrite($this->dat_fp, $value$vallen); 
  151.         return DB_SUCCESS; 
  152.     } 
  153.  
  154.     /** 
  155.      * Description: 查询一条记录 
  156.      * @param $key 
  157.      */ 
  158.     public function get($key){ 
  159.         //计算偏移量,key的hash值对索引文件的大小求模,再乘4。因为每个链表指针大小为4 
  160.         $offset = ($this->times33Hash($key) % DB_BUCKET_SIZE) * 4; 
  161.         //SEEK_SET是默认的 
  162.         fseek($this->idx_fp, $offset, SEEK_SET); 
  163.         $pos = unpack('L'fread($this->idx_fp, 4)); 
  164.         $pos = $pos[1]; 
  165.  
  166.         $found = false; 
  167.         while($pos){ 
  168.             fseek($this->idx_fp, $pos, SEEK_SET); 
  169.             $block = fread($this->idx_fp, DB_INDEX_SIZE); 
  170.             $cpkey = substr($block, 4, DB_KEY_SIZE); 
  171.  
  172.             if(!strncmp($key$cpkeystrlen($key))){ 
  173.                 $dataoff = unpack('L'substr($block, DB_KEY_SIZE + 4, 4)); 
  174.                 $dataoff = $dataoff[1]; 
  175.  
  176.                 $datalen = unpack('L'substr($block, DB_KEY_SIZE + 8, 4)); 
  177.                 $datalen = $datalen[1]; 
  178.  
  179.                 $found = true; 
  180.                 break
  181.             } 
  182.             $pos = unpack('L'substr($block, 0, 4)); 
  183.             $pos = $pos[1]; 
  184.         } 
  185.         if(!$found){ 
  186.             return null; 
  187.         } 
  188.         fseek($this->dat_fp, $dataoff, SEEK_SET); 
  189.         $data = fread($this->dat_fp, $datalen); 
  190.         return $data
  191.     } 
  192.  
  193.     /** 
  194.      * Description: 删除 
  195.      * @param $key 
  196.      */ 
  197.     public function delete($key){ 
  198.         $offset = ($this->times33Hash($key) % DB_BUCKET_SIZE) * 4; 
  199.         fseek($this->idx_fp, $offset, SEEK_SET); 
  200.         $head = unpack('L'fread($this->idx_fp, 4)); 
  201.         $head = $head[1]; 
  202.         $curr = $head
  203.         $prev = 0; 
  204.         $found = false; 
  205.         while($curr){ 
  206.             fseek($this->idx_fp, $curr, SEEK_SET); 
  207.             $block = fread($this->idx_fp, DB_INDEX_SIZE); 
  208.  
  209.             $next = unpack('L'substr($block, 0, 4)); 
  210.             $next = $next[1]; 
  211.  
  212.             $cpkey = substr($block, 4, DB_KEY_SIZE); 
  213.             if(!strncmp($key$cpkeystrlen($key))){ 
  214.                 $found = true; 
  215.                 break
  216.             } 
  217.             $prev = $curr
  218.             $curr = $next
  219.         } 
  220.         if(!$found){ 
  221.             return DB_FAILURE; 
  222.         } 
  223.         //删除索引文件。 
  224.         if($prev == 0){ 
  225.             fseek($this->idx_fp, $offset, SEEK_SET); 
  226.             fwrite($this->idx_fp, pack('L'$next), 4); 
  227.         }else
  228.             fseek($this->idx_fp, $prev, SEEK_SET); 
  229.             fwrite($this->idx_fp, pack('L'$next), 4); 
  230.         } 
  231.         return DB_SUCCESS; 
  232.     } //phpfensi.com 
  233.  
  234.     public function close(){ 
  235.         if(!$this->closed){ 
  236.             fclose($this->idx_fp); 
  237.             fclose($this->dat_fp); 
  238.             $this->closed = true; 
  239.         } 
  240.     } 
  241. ?> 

测试,测试添加一万条和查找一万条,代码如下:

  1. <?php 
  2. //先include上面的类。。如果在同一个文件中就不用了。 
  3. //测试 
  4. $db = new DB(); 
  5. $db->open('/var/www/data/'); 
  6.  
  7. $startTime = microtime(true); 
  8.  
  9. //插入测试...插入10000条:成功,耗时: 793.48206520081ms 
  10. //for($i=0; $i<10000; $i++){ 
  11. //    $db->add('key'.$i, 'value'.$i); 
  12. //} 
  13.  
  14. //查找测试...查找10000条:成功,耗时: 149.08313751221ms 
  15. for($i=0; $i<10000; $i++){ 
  16.     $db->get('key'.$i); 
  17.  
  18. $endTime = microtime(true); 
  19. echo '成功,耗时: ' . (($endTime - $startTime)*1000) . 'ms'
  20. $db->close(); 
  21. ?>

Tags: PHP数据库 NOSQL

分享到: