一 文本數據庫類目標
文本數據庫設計的目標，是實現文本等數據的組織和存取，屏蔽數據存放的具體細節，向用戶提供一個簡單方便的文本數據的插入，修改，刪除，查詢的接口。
二 文本數據庫思路
我們打算將相關的文本數據存放在同一個文件中，並以記錄為單位實現對文本數據的組織與管理。記錄可分為兩中：定長記錄和不定找記錄。對於定長記錄，我們可以用順序存放的方式組織記錄，這樣對於第Ｎ個記錄，我們可以直接以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);
}
}
?>
