📄 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 + -