数据|数据库
一 文本数据库类目标
文本数据库设计的目标，是实现文本等数据的组织和存取，屏蔽数据存放的具体细节，向用户提供一个简单方便的文本数据的插入，修改，删除，查询的接口。
二 文本数据库思路
我们打算将相关的文本数据存放在同一个文件中，并以记录为单位实现对文本数据的组织与管理。记录可分为两中：定长记录和不定找记录。对于定长记录，我们可以用顺序存放的方式组织记录，这样对于第Ｎ个记录，我们可以直接以N*RceLength定位它在文件中的存放位置，对于读取，插入，更新操作来说，顺序存入的组织方式会使它们的实现变得非常简单且快捷；然而在删除记录的时候，麻烦就来了，要继续保持记录在数据库中的顺序存放，在实施删除操作后，我们还必须将后面的所有记录向前移动一个记录单位，在记录个数相对少并且记录长度相对小的情况下，这种前移数据所付出的代价还是可以接受的，当记录个数变的很多，或者记录长度大的情况下，一个记录的删除往往会伴随着大量数据的移动，这种代价却变的非常高。
以定长记录的方式存入数据使得很多操作变的非常便捷，然而除了上面所讲的数据删除不利的因素外，定长记录还有一个非常明显的不足，那就是在记录的长短不一的情况下，以定长的方式存放记录可能会浪费很多的空间，因为我们必须以所有记录中最大的那个记录长度为所有记录的长度，用这样的记录空间存放短的数据难免有点大才小用。解决这个问题，我们很快就会想到不定找记录的方式，就是允许文件中不同的记录占据必要的空间而不必使用统一的长度。不定长记录的方式完美的解决了空间浪费的问题，然而却失去了定长记录能快速定位的特性，使得对数据的各种操作变的格外的麻烦甚至不可能。
我们必须设计一种巧妙方式要组织数据，使得它不仅能像定长方式那样快速地定位数据库的记录，又能像不定长方式那样节省数据空间，尽量减少数据删除所付出的代价。而要拥有这样的特性，必然是这两种方式的结合。我们用一个文件以不定长的方式存放实际数据，解决了空间浪费问题；另外我们还设立一个辅助的文件，用于记录这些数据的定位信息，定位信息以定长的方式组织与存放，可以解决记录的快速定位问题。为了后面讨论的方便，我们不妨给这两个文件命个名，存放实际数据的文件我们称它为数据文件(dbf)，存入定位信息的文件我们称之为索引文件(indx)。
我们来分析一下这种组织方式的具体实现。插入数据时，我们根据存入数据的大小从数据文件(dbf)中分配一个合适的可用空间，并将数据存入此处，然后在索引文件(indx)添加一个新记录用于存放实际数据在数据文件(dbf)中的定位信息，如是一个新的记录就这样子被插入到数据库中了。读取记录时，我们先从索引文件(indx)中取得实际数据的定位信息，然后根据这些定位信息到dbf中定位并读取记录的实际内容，因为定位信息是定长方式存放，它可以非常直接地从indx中获取。删除数据的时候，我们只需简单地从索引文件中删除对应的定位记录就可以达到目的，而无需对数据文件进行任何操作，定位记录从索引中删除后，此记录虽然在数据文件中依然存在却永远都不会再被访问到而被闲置。为了更有效的利用空间，我们在进行删除操作的时候并不只作如此简单的处理，我们还设立一个额外文件，用于记录数据文件中这些因删除而被闲置的空间，以便在合适的时候，使得这些闲置空间被再度存放实际数据。此文件也以的方式记录闲置空间信息，我们称这个文件为闲置空间文件(left)。更新数据也相对复杂，如果新的数据长度小于原数据的长度，我们可以简单地将新数据存原来的位置，这种情况下我们只需对数据文件(dbf)进行更新操作。而当新数据所需空间大于原始空间的时候，我们只能放弃原空间而另寻地方存放数据，这里除了对dbf进行写操作外，还得更新记录在indx中的定位信息，并在left文件中添加被放弃的空间信息.
三 文本数据库的精细设计与算法
上面简单地分析了文本数据库的实现方法。下面根据我的实例来介绍文本数据库的精细设计与具体算法。
首先，我们简地介绍上面提到的三个文件的数据结构。
对于数据文件dbf,记录是不定长而且是无序存放（为什么是无序，下面会有介绍）的，不需要太多的说明。
索引文件indx以定长并且是顺序的方式存放记录，也就说每个记录的长度一致为RcdLength,而且第N个记录存放在文件中的N*RcdLength处.每个记录的格式如下:
记录编号(ID)|偏移位置(LOC)|数据长度(Length)
其中，ID是数据库每个出现过的记录的唯一编号，不同的记录以此来唯一标识自己，相当于数据库的健值。ID编号由系统递增分配；LOC记录实际数据在数据文件dbf中存入的首位置，length则表示此数据在dbf中所占用的空间。值得提出的是，ID编号N的记录并不一定是数据库中的第N个记录，ID用以标识记录的身分，而第N个记录的N则是指记录在数据库中的物理(对应于indx)与逻辑位置(对应于dbf)；还有，length记录的是该数据所占用的空间大小而并一定等同于数据的实际长度（为什么？）.
ID,LOC,Length均为无符号整数，所以indx中每个记录的占用4*3＝12个字节的空间，这很利于记录的顺序存放和删除。
我们还约定,indx文件中第一个记录并不是用于记录数据的定位信息，而用于记录整个数据库的相关信息，其中ID用于存入已被分
配的最大ID编号，LOC用于记录数据库中的实际记录个数，length用于记录数据文件dbf的末端位置。可以看出,ID值是递增的，在没有
进行任何删除操作之前，ID值与LOC永远相等，如删除操作,LOC必然小于ID值。另外，length值在很多情况下并不与数据文件bdf的大
小相等，如我们在dbf的末端为一个新记录分配了100个字节的空间而写入的实际数据只有90，那个length值要比dbf的大小大10.
left文件的记录结构与组织方式和indx类似却更为简单，它只有两个字段：
偏移位置(LOC)|空间长度(Length)
其中，LOC表示闲置空间在dbf中的起始位置,Length表示此闲置空间的长度。同样，left文件中的第一个记录不用来记录闲置空间
信息，而是记录自己的相关信息,第一个记录的LOC值或Length用于记录left文件中的闲置空间条数也就是本文件和实际记录个数。
数据结构已经陈述完备，下面我们根据代码来谈谈实际算法：
<?
class TxtDB //文本数据库类
{
var $name=''; //文本数据库名
var $path=''; //数据库路径
var $isError; //出错代码
var $dbh; //数据文件dbf指针
var $indxh; //索引文件indx指针
var $lfth; //闲置空间文件left指针
var $lckh;
var $rcdCnt=0;//数据库的记录个数
var $maxID=0; //数据库已分配的最大ID编号
var $leftCnt=0;//闲置空间个数
var $DBend=0; //DBF文件末端指针
/*初始化函数*/
function TxtDB($name,$path='dbm')
{
$this->name=$name;
$this->path=$path.'/'.$name;
$this->isError=0;
$path=$this->path;
if ($name!='')
{
mkdir($this->path,0777);//创建数据库目录
//创建或打开数据库文件
if (!file_exists($path.'/'.$name.'.tdb')) $this->dbh=fopen($this->path.'/'.$name.'.tdb','w+');
else $this->dbh=fopen($path.'/'.$name.'.tdb','r+');
if (!file_exists($path.'/'.$name.'.indx')) $this->indxh=fopen($this->path.'/'.$name.'.indx','w+');
else $this->indxh=fopen($path.'/'.$name.'.indx','r+');
if (!file_exists($path.'/'.$name.'.lft')) $this->lfth=fopen($this->path.'/'.$name.'.lft','w+');
else $this->lfth=fopen($this->path.'/'.$name.'.lft','r+');
//为保证数据库操作的原子性，对数据进行加锁保护
$this->lckh=fopen($this->path.'/'.$name.'.lck','w');
flock($this->lckh,2);
fwrite($this->lckh,'lck');//阻塞其它并发进程对数据库的并行操作
//获取数据库的相关信息
$rcd=$this->getRcd(0);//从indx文件中读取首个记录
$this->rcdCnt=$rcd[id];
$this->maxID=$rcd[loc];
$this->DBend=$rcd[len];
$rcd=$this->getLeft(0);//从left文件中读取首个记录
$this->leftCnt=$rcd[loc];
}
else $this->isError=1;
}
/*设置indx的定位信息*/
function setRcd($rid,$id,$loc,$len)
{
fseek($this->indxh,$rid*12);
//移动文件指针至记录处
$str=pack('III',$id,$loc,$len);
//将整数压缩到字符串中
fwrite($this->indxh,$str,12);
//将定定位信息 ID|LOC|Len 写入indx的第rid个记录
}
/*获取定位信息*/
function getRcd($rid)
{
fseek($this->indxh,$rid*12);
//移至记录处
$str=fread($this->indxh,12);
//记取记录
$rcd=array();
//将压缩的字符串还原为整数
$rcd[id]=str2int($str);
$rcd[loc]=str2int(substr($str,4,4));
$rcd[len]=str2int(substr($str,8,4));
return $rcd;//返回第rid个记录的定位信息
}
/*设置闲置空间记录*/
function setLeft($lid,$loc,$len)
{
fseek($this->lfth,$lid*8);
$str=pack('II',$loc,$len);
fwrite($this->lfth,$str,8);
}
/*记取第lid个闲置空间信息*/
function getLeft($lid)
{
fseek($this->lfth,$lid*8);
$str=fread($this->lfth,8);
$rcd[loc]=str2int($str);
$rcd[len]=str2int(substr($str,4,4));
return $rcd;
}
/*结束数据库操作并释放数据加锁*/
function close()
{
fclose($this->dbh);
fclose($this->indxh);
fclose($this->lfth);
fclose($this->lckh);
}
/*从闲置空间中寻找一个大小最少为len的空间
使用最佳适用法 */
function seekSpace($len)
{
$res=array('loc'=>0,'len'=>0);
if ($this->leftCnt<1) return $res;
//没有闲置空间
$find=0;
$min=1000000;
//遍历所有闲置空间信息
for ($i=$this->leftCnt;$i>0;$i--)
{
$res=$this->getLeft($i);
//找寻到大小刚好合适的空间
if ($res[len]==$len) {$find=$i;break;}
//找到可用的闲置空间
else if($res[len]>$len)
{
//力图找到一个最合适的空间
if ($res[len]-$len<$min)
{
$min=$res[len]-$len;
$find=$i;
}
}
}
if ($find)
{
//找到了合适的闲置空间
//读取闲置空间信息
$res=$this->getLeft($find);
//用left文件删除此闲置空间的记录信息
fseek($this->lfth,($find+1)*8);
$str=fread($this->lfth,($this->leftCnt-$find)*8);
fseek($this->lfth,$find*8);
fwrite($this->lfth,$str);
//更新闲置空间记录数
$this->leftCnt--;
$this->setLeft(0,$this->leftCnt,0);
//返回获得的闲置空间结果
return $res;
}
else //失败返回
{
$res[len]=0;
return $res;
}
}
/*插入记录至数据库content为记录内容,len限定记录的长度*/
function insert($content,$len=0)
{
$res=array('loc'=>0);
//记录长度没有指定则根据数据实际长度指定
if (!$len) $len=strlen($content);
//试图从闲置空间中获取一块可用的空间
if ($this->leftCnt) $res=$this->seekSpace($len);
if (!$res[len])
{
//没有找到可用的闲置空间则从数据文件末端分配空间
$res[loc]=$this->DBend;
$res[len]=$len;
}
//更新数据文件末端指针
if ($res[loc]+$res[len]>$this->DBend) $this->DBend=$res[loc]+$res[len];
$this->maxID++;//更新最大ID编号
$this->rcdCnt++;//更新数据库记录个数
//将更新永久写入数据库
$this->setRcd(0,$this->rcdCnt,$this->maxID,$this->DBend);
$this->setRcd($this->rcdCnt,$this->maxID,$res[loc],$res[len]);
//将实际数据写入从dbf分配的空间处
fseek($this->dbh,$res[loc]);
fwrite($this->dbh,$content,$len);
//成功返回新记录的编号
return $this->maxID;
}
/*寻找编号为ID的记录在数据库中的位置编号N*/
/*因为ID编号在indx中升序排列可使用二分查找大大提高查询速度*/
function findByID($id)
{
//数据库中没有记录或者编号超过当前最大ID编号
if ($id<1 or $id>$this->maxID or $this->rcdCnt<1) return 0;
$left=1;
$right=$this->rcdCnt;
while($left<$right)//实施二分查找
{
$mid=(int)(($left+$right)/2);
if ($mid==$left or $mid==$right) break;
$rcd=$this->getRcd($mid);
if ($rcd[id]==$id) return $mid;
else if($id<$rcd[id]) $right=$mid;
else $left=$mid;
}
$rcd=$this->getRcd($left);
if ($rcd[id]==$id) return $left;
$rcd=$this->getRcd($right);
if ($rcd[id]==$id) return $right;
//查找成功返回位置编号N
return 0;//失败返回0
}
/*从数据库中删除编号为ID的记录*/
function delete($id)
{
//查找此记录在数据库中的位置编号
$rid=$this->findByID($id);
if (!$rid) return;//不存在ID号为id的记录
$res=$this->getRcd($rid);//获取此记录的定位信息
//从索引文件中删除此记录的定位信息
fseek($this->indxh,($rid+1)*12);
$str=fread($this->indxh,($this->rcdCnt-$i)*12);
fseek($this->indxh,$rid*12);
fwrite($this->indxh,$str);
//更新数据库记录个数并永久写入数据库
$this->rcdCnt--;
$this->setRcd(0,$this->rcdCnt,$this->maxID,$this->DBend);
//将此记录在dbf所占用的空间登记到闲置空间队列
$this->leftCnt++;
$this->setLeft(0,$this->leftCnt,0);
$this->setLeft($this->leftCnt,$res[loc],$res[len]);
}
/*更新ID编号为id的记录内容*/
/*len用于重新限定记录的内容*/
function update($id,$newcontent,$len=0)
{
//将ID编号转化为位置编号N
$rid=$this->findByID($id);
if (!$rid) return;//不存的ID编号
if (!$len) $len=strlen($newcontent);
//获取此记录定位信息
$rcd=$this->getRcd($rid);
//更新的内容长度超出记录原来分配的空间
if ($rcd[len]<$len)
{
//放弃原空间并将此空间录入闲置空间队列
$this->leftCnt++;
$this->setLeft(0,$this->leftCnt,0);
$this->setLeft($this->leftCnt,$rcd[loc],$rcd[len]);
//在dbf末端为此记录重新分配空间
$rcd[loc]=$this->DBend;
$rcd[len]=$len;
$this->DBend+=$len;
//更新数据库信息
$this->setRcd(0,$this->rcdCnt,$this->maxID,$this->DBend);
$this->setRcd($rid,$rcd[id],$rcd[loc],$rcd[len]);
}
//写入新数据
fseek($this->dbh,$rcd[loc]);
fwrite($this->dbh,$newcontent,$len);
}
/*根据位置编号获取记录内容*/
function selectByRid($rid)
{
//数据以ID编号与实际数据content二元组返回
$res=array('id'=>0,'content'=>'');
//错误的位置编号
if ($rid<1 or $rid>$this->rcdCnt) return $res;
//读取定位信息
else $rcd=$this->getRcd($rid);
$res[id]=$rcd[id];
$res[len]=$rcd[len];
//根据定位信息从dbf中读取实际数据
fseek($this->dbh,$rcd[loc]);
$res[content]=fread($this->dbh,$rcd[len]);
return $res;
}
/*根据ID编号获取记录内容*/
function select($id)
{
//将ID编号转换成位置编号再调用上面的函数
return $this->selectByRid($this->findByID($id));
}
/*数据库备份*/
function backup()
{
copy($this->path.'/'.$this->name.'.tdb',$this->path.'/'.$this->name.'.tdb.bck');
copy($this->path.'/'.$this->name.'.indx',$this->path.'/'.$this->name.'.indx.bck');
copy($this->path.'/'.$this->name.'.lft',$this->path.'/'.$this->name.'.lft.bck');
}
/*从备份中恢复*/
function recover()
{
copy($this->path.'/'.$this->name.'.tdb.bck',$this->path.'/'.$this->name.'.tdb');
copy($this->path.'/'.$this->name.'.indx.bck',$this->path.'/'.$this->name.'.indx');
copy($this->path.'/'.$this->name.'.lft.bck',$this->path.'/'.$this->name.'.lft');
}
/*清除数据库*/
function drop()
{
unlink($this->path.'/'.$this->name.'.tdb');
unlink($this->path.'/'.$this->name.'.indx');
unlink($this->path.'/'.$this->name.'.lft');
}
/*清空数据库记录*/
function reset()
{
setRcd(0,0,0);
setLeft(0,0);
}
}
?>
