?? 16.htm
字號:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 3.0">
<title>C:\WINDOWS\Desktop\UnixProg\7.htm</title>
</head>
<body>
<font SIZE="2">
<h1 align="center">第十六章 一個數據庫函數庫 </h1>
<p>16.1 引言 </p>
<p>在八十年代早期，Unix環境被認為不適合運行多用戶數據庫系統（見Stonebr
</p>
<p>aker[1981]和Weinberger[1982]）。早期的系統，如Version 7，因為沒有提供任
</p>
<p>何形式的IPC機制（除了半雙工管道），也沒有提供任何形式的記錄鎖機制，所以
</p>
<p>確實不適合運行多用戶數據庫。新一些的系統，象SVR4和4.3+BSD，則為運行可靠
</p>
<p>的、多用戶的數據庫系統提供了一個適合的環境。很多商業公司在許多年前就已提
</p>
<p>供這種系統。 </p>
<p>在本章中，我們設計一個簡單的、多用戶數據庫的函數庫。通過此函數庫提供
</p>
<p>的C語言函數，其他程序可以訪問數據庫中的記錄。這個C函數庫只是一個完整的數
</p>
<p>據庫的很小的一部分，并不包括其他很多部分，如查詢語言等，關于其他部分可以
</p>
<p>參閱專門介紹數據庫的書。我們感興趣的是一個數據庫函數庫與Unix的接口，以及
</p>
<p>這些接口與前面各章節的關系（如12.3節的記錄鎖）。 </p>
<p>16.2 歷史 </p>
<p>dbm（3）是一個在Unix系統中很流行的數據庫函數庫，它由Ken Thompson開發
</p>
<p>，使用了動態Hash結構。最初，它與Version 7一起提供，并出現在所有Berkeley
</p>
<p>的版本中，也包含在Berkeley的SVR4兼容函數庫中。Seltzer和Yigit[1991]中有關
</p>
<p>于dbm函數庫使用的動態Hash算法歷史的詳細介紹，以及這個庫的其它實現方法。
</p>
<p>但是，這些實現的一個致命缺點是它們都不支持多個進程對數據庫的并發修改。它
</p>
<p>們都沒有提供并發控制（如記錄鎖）。 </p>
<p>4.3+BSD提供了一個新的庫db(3)，這個庫支持3種不同的訪問方式：（a）面向
</p>
<p>記錄，（b）Hash和（c）B樹。同樣，db也沒有提供并發控制（這一點在db手冊的
</p>
<p>BUGS欄中說得很清楚）。Seltzer和Olson[1992]中說以后的版本將提供象大部分商
</p>
<p>業數據庫系統一樣的并發控制功能。 </p>
<p>絕大部分商業的數據庫函數庫提供多進程并發修改一個數據庫所需要的并發控
</p>
<p>制。這些系統一般都使用我們在12.3節中介紹的建議記錄鎖，并且用B+樹來實現他
</p>
<p>們的數據庫。 </p>
<p>16.3 函數庫 </p>
<p>在本節中，我們定義了這個數據庫函數庫的C語言接口，在下一節中再討論其
</p>
<p>實現。 </p>
<p>當打開一個數據庫時，通過返回值得到一個DB結構的指針。這一點很象通過f
</p>
<p>open得到一個FILE結構的指針（5.2節），以及通過opendir得到一個DIR結構的指
</p>
<p>針（4.21節）。我們將用此指針作為參數來調用以后的數據庫函數。
</p>
<p>如果db_open成功返回 </p>
<p>，則將建立兩個文件：pathname.idx 和pathname.dat，pathname.idx是索引文件
</p>
<p>，pathname.dat是數據文件。oflag被用作第二個參數傳遞給open（3.3節），表明
</p>
<p>這些文件的打開模式（只讀、讀寫或如果文件不存在則建立等）。如果需要建立新
</p>
<p>的數據庫，mode將作為第三個參數傳遞給open（文件訪問權限）。 </p>
<p>當我們不再使用數據庫時，調用db_close來關閉數據庫。db_close將關閉索引
</p>
<p>文件和數據文件，并釋放數據庫使用過程中分配的所有用于內部緩沖的存儲空間。
</p>
<p>當我們向數據庫中加入一條新的記錄時，必須提供一個此記錄的主鍵，以及與
</p>
<p>此主鍵相聯系的數據。如果此數據庫存儲的是人事信息，主鍵可以是雇員號，數據
</p>
<p>可以是此雇員的姓名、地址、電話號碼、受聘日等等。我們的實現要求主鍵必須是
</p>
<p>唯一的（比方說，我們不會有兩個雇員記錄有同樣的雇員號）。 </p>
<p>#include "db.h" </p>
<p>int db_store( DB *db, const char *key, const char *data, int flag ) ; </p>
<p>返回：0表示成功，非0表示錯誤（見 </p>
<p>key和data是由NULL結束的字符串。它們可以包含除了NULL外的任何字符，如
</p>
<p>換行符。 </p>
<p>flag只能是DB_INSERT（加一條新記錄）或DB_REPLACE（替換一條已有的記錄
</p>
<p>）。這兩個常數定義在db.h頭文件中。如果我們使用DB_REPLACE，而記錄不存在，
</p>
<p>返回值為-1。如果我們使用DB_INSERT，而記錄已經存在，返回值為1。
</p>
<p>通過提供主鍵key可以從數據庫中取出一條記錄。 </p>
<p>#include "db.h" </p>
<p>char *db_fetch( DB *db, const char *key ) ; </p>
<p>返回：指向數據的指針表示成功，NULL表示記錄沒有找到。 </p>
<p>如果記錄找到了，返回的指針指向與主鍵聯系在一起的數據。 </p>
<p>通過提供主鍵key我們也可以從數據庫中刪除一條記錄。 </p>
<p>#include "db.h" </p>
<p>int db_delete( DB *db, const char *key ) ; </p>
<p>返回：0表示成功，-1表示記錄沒有找到。 </p>
<p>除了通過主鍵訪問數據庫外，也可以一條一條記錄地訪問數據庫。為此，我們首
</p>
<p>先調用db_rewind回到數據庫的第一條記錄，再調用db_nextrec來讀每個順序的記
</p>
<p>錄。 </p>
<p>#include "db.h" </p>
<p>void db_rewind( DB *db ) ; </p>
<p>char *db_nextrec( DB *db, char *key ) ; </p>
<p>返回：如果成功返回指向數據的指針，NULL表示到了數據庫的 </p>
<p>如果key是非NULL的指針，db_nextrec將當前記錄的主鍵存入key中。 </p>
<p>db_nextrec不保證記錄訪問的次序，只保證每一條記錄被訪問恰好一次。如果
</p>
<p>我們順序存儲三條主鍵分別為A、B、C的記錄，我們無法確定db_nextrec將按什么
</p>
<p>順序返回這三條記錄。它可能按B、A、C的順序返回，也可能按其它順序。實際的
</p>
<p>順序由數據庫的實現決定。 </p>
<p>這七個函數提供了數據庫函數庫的接口。接下來介紹我們的實現。
</p>
<p>16.4 實現概述 </p>
<p>大多數數據庫訪問的函數庫使用兩個文件來存儲信息：一個索引文件和一個數
</p>
<p>據文件。索引文件包括索引值（主鍵）和一個指向數據文件中對應數據記錄的指針
</p>
<p>。有許多技術可用來組織索引文件以提高按鍵查詢的速度和效率，Hash表和B+樹是
</p>
<p>兩種常用的技術。我們采用固定大小的Hash表來組織索引文件結構，并采用鏈表法
</p>
<p>解決Hash沖突。在介紹db_open時，我們曾提到將建立兩個文件：一個以.idx為后
</p>
<p>綴的索引文件和一個以.dat為后綴的數據文件。 </p>
<p>我們將主鍵和索引以NULL結尾的字符串形式存儲--它們不能包含任意的二進制
</p>
<p>數據。有些數據庫系統用二進制的形式存儲數值數據（如用1、2或4個字節存儲一
</p>
<p>個整數）以節省空間，這樣一來使函數復雜化，也使數據庫文件在不同的平臺間移
</p>
<p>植比較困難。比方說，我們在網絡上有兩個系統使用不同的二進制格式存儲整數，
</p>
<p>如果我們想要這兩個系統都能夠訪問數據庫就必須解決這個問題（今天不同體系結
</p>
<p>構的系統共享文件已經很常見了）。按照字符串形式存儲所有的記錄，包括主鍵和
</p>
<p>數據，能使這一切變得簡單。這確實會需要更多的磁盤空間，但隨著磁盤技術的發
</p>
<p>展，這漸漸不再構成問題。 </p>
<p>db_store要求對每個主鍵，最多只有一個對應的記錄。有些數據庫系統允許多
</p>
<p>條記錄使用同樣的主鍵，并提供方法訪問與一個主鍵相關的所有記錄。另外，我們
</p>
<p>只有一個索引文件，這意味著每個數據記錄只能有一個主鍵。有些數據庫允許一條
</p>
<p>記錄擁有多個鍵，并且對每一個鍵使用一個索引文件。當加入或刪除一條記錄時，
</p>
<p>要對所有的索引文件進行相應的修改。（一個有多個索引的例子是雇員庫文件，我
</p>
<p>們可以將雇員號作為鍵，也可以將雇員的社會保險號作為鍵。由于一般雇員的名字
</p>
<p>并不保證唯一，所以名字不能作為鍵。） </p>
<p>圖16.1是我們的數據庫實現的基本結構。索引文件由三部分組成：空閑鏈表指
</p>
<p>針、Hash表和索引記錄。圖16.1中所有叫做ptr的字段中實際存儲的是以ASCII字符
</p>
<p>串形式記錄的在文件中的偏移量。 </p>
<p>圖16.1 索引文件和數據文件結構 </p>
<p>當給定一個主鍵要在數據庫中尋找一條記錄時，db_fetch根據主鍵計算Hash值
</p>
<p>，由此Hash值可確定一條Hash鏈（chain ptr字段可以為0，表示一條空的Hash鏈）
</p>
<p>。沿著這條Hash鏈，我們可以找到所有有同樣Hash值的索引記錄。當我們遇到一個
</p>
<p>索引記錄的chain ptr字段為0時，表示我們到達了此Hash鏈的末尾。 </p>
<p>下面讓我們來看一個實際的數據庫文件。程序16.1建立了一個新的數據庫，并
</p>
<p>且加入了三條記錄。由于我們將所有的字段都以ASCII字符串的形式存儲在數據庫
</p>
<p>中，所以我們可以用任何標準的Unix工具來查看索引文件和數據文件。
</p>
<p>$ ls -l db4.* </p>
<p>-rw-r--r-- 1 stevens 28 Oct 30 06:42 db4.dat </p>
<p>-rw-r--r-- 1 stevens 28 Oct 30 06:42 db4.idx </p>
<p>$ cat db4.idx </p>
<p>0 53 35 </p>
<p>0 10Alpha:0:6 </p>
<p>0 10beta:6:14 </p>
<p>17 11gamma:20:8 </p>
<p>$ cat db4.dat </p>
<p>data1 </p>
<p>Data for beta </p>
<p>Record3 </p>
<p>#include "db.h" </p>
<p>int </p>
<p>main(void) </p>
<p>{ </p>
<p>DB *db; </p>
<p>if ( (db = db_open("db4", O_RDWR | O_CREAT | O_TRUNC, </p>
<p>FILE_MODE)) == NULL) </p>
<p>err_sys("db_open error"); </p>
<p>if (db_store(db, "Alpha", "data1", DB_INSERT) != 0) </p>
<p>err_quit("db_store error for alpha"); </p>
<p>if (db_store(db, "beta", "Data for beta", DB_INSERT) != 0) </p>
<p>err_quit("db_store error for beta"); </p>
<p>if (db_store(db, "gamma", "record3", DB_INSERT) != 0) </p>
<p>err_quit("db_store error for gamma"); </p>
<p>db_close(db); </p>
<p>exit(0); </p>
<p>} </p>
<p>程序16.1 建立一個數據庫并向其寫三條記錄 </p>
<p>為了使這個例子簡單，我們將每個ptr字段的大小定為4個ASCII字符，將Hash
</p>
<p>表的大小（Hash鏈的條數）定為3。由于每一個ptr記錄的是一個文件偏移量，所以
</p>
<p>4個ASCII字符限制了一個索引文件或數據文件的大小最多只能為10000字節。在后
</p>
<p>面的16.8節做一些性能方面的測試時，我們將ptr字段的大小設為6（這樣文件的大
</p>
<p>小可以達到1000000字節），將Hash表的大小設為100。 </p>
<p>索引文件的第一行為 </p>
<p>0 53 35 0 </p>
<p>分別為空閑鏈表指針（0，表示空閑鏈表為空），和三個Hash鏈表的指針：53
</p>
<p>，35和0。下一行 </p>
<p>0 10Alpha:0:6 </p>
<p>顯示了一條索引記錄的結構。第一個4字符的字段（0）表示這一條記錄是此H
</p>
<p>ash鏈的最后一條。下一個4字符的字段（10）為idx len，表示此索引記錄剩下部
</p>
<p>分的長度。我們通過兩個read操作來讀取一條索引記錄：第一個read讀取這兩個固
</p>
<p>定長度的字段（chain ptr和idx len），然后再根據idx len來讀取后面的不定長
</p>
<p>部分。剩下的三個字段為：key（主鍵）、dat off（在數據文件中的偏移量）和d
</p>
<p>at len（數據記錄的長度）。這三個字段用分隔符隔開，在這里我們使用的是分號
</p>
<p>。由于此三個字段都是不定長的，所以我們需要一個專門的分隔符，而且這個分隔
</p>
<p>符不能出現在主鍵中。最后用一個回車符結束這一條索引記錄。由于在idx
len中 </p>
<p>已經有了記錄的長度，所以這個回車符并不是必須的，加上回車符是為了把各條索
</p>
<p>引記錄分開，這樣就可以用標準的Unix工具如cat和more來查看索引文件。key是我
</p>
<p>們將記錄加入數據庫時選擇的主鍵。數據記錄在數據文件中的偏移為0，長度為6。
</p>
<p>從數據文件中我們看到數據記錄確實從0開始，長度為6個字節。（與索引文件一樣
</p>
<p>，我們在這里自動在每條數據記錄的后面加上一個回車符，以便于使用Unix工具。
</p>
<p>在調用db_fetch時，此回車符不作為數據返回。） </p>
<p>如果在這個例子中跟蹤三個Hash鏈，我們看到第一條Hash鏈上的第一條記錄的
</p>
<p>偏移量是53（gamma）。這條鏈上的下一條記錄的偏移量為17（Alpha），并且是這
</p>
<p>條鏈上的最后一條記錄。第二條Hash鏈上的第一條記錄的偏移量是35（beta），且
</p>
<p>是此鏈上最后一條記錄。第三條Hash鏈為空。 </p>
<p>請注意索引文件中索引記錄的順序和數據文件中對應數據記錄的順序與我們在
</p>
<p>程序16.1中調用db_store的順序一樣。由于我們在調用db_open時使用了O_TRUNC標
</p>
<p>志，索引文件和數據文件都被截斷，整個數據庫相當于從新初始化。在這種情形下
</p>
<p>，db_store將新的索引記錄和數據記錄添加到對應的文件末尾。在后面我們將看到
</p>
<p>db_store也可以重復使用這兩個文件中因刪除記錄而生成的空間。 </p>
<p>在這里使用固定大小的Hash表作為索引是一個妥協。當每個Hash鏈均不太長時
</p>
<p>，這個方法能保證快速的查找。我們的目的是能夠快速地查找任意的鍵，同時又不
</p>
<p>使用太復雜的數據結構，如B樹或動態可擴充Hash表。動態可擴充Hash表的優點是
</p>
<p>能保證僅用兩次磁盤操作就能找到數據記錄（詳見Selter和Yigit[1991]）。B樹能
</p>
<p>夠讓我們用鍵的順序來遍歷數據庫（采用Hash表的db_nextrec函數就做不到這一點
</p>
<p>）。 </p>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -