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核心技术与最佳实践》一书。尊重作者,转载请保留该书名,代码如下:
- <?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;
- } //phpfensi.com
- 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();
- ?>
Tags: PHP数据库 NOSQL
- 上一篇:php入门级教程:PHP大小写问题
- 下一篇:利用PHP实现Hash表功能
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)