＋设为首页 ＋添加到收藏夹
16.1 引言 【相关文章:linux修改MAC地址/locale】 【扩展阅读:加班/太晚睡/工作忙会导致的后果】 在八十年代早期，unix环境被认为不适合运行多用户数据库系统（见stonebr 【扩展信息:linux 配gdm】 aker[1981]与weinberger[1982]）。早期的系统，如version 7，因为没有提供任 何形式的ipc机制（除了半双工管道），也没有提供任何形式的记录锁机制，所以 确实不适合运行多用户数据库。新一些的系统，象svr4与4.3+bsd，则为运行可靠 的、多用户的数据库系统提供了一个适合的环境。很多商业公司在许多年前就已提 供这种系统。 在本章中，我们设计一个简单的、多用户数据库的函数库。通过此函数库提供 的c语言函数，其他程序可以访问数据库中的记录。这个c函数库只是一个完整的数 据库的很小的一部分，并不包括其他很多部分，如查询语言等，关于其他部分可以 参阅专门介绍数据库的书。我们感兴趣的是一个数据库函数库与unix的接口，以及 这些接口与前面各章节的关系（如12.3节的记录锁）。 16.2 历史 dbm（3）是一个在unix系统中很流行的数据库函数库，它由ken thompson开发 ，使用了动态hash结构。最初，它与version 7一起提供，并出现在所有berkeley 的版本中，也包含在berkeley的svr4兼容函数库中。seltzer与yigit[1991]中有关 于dbm函数库使用的动态hash算法历史的详细介绍，以及这个库的其它实现方法。 但是，这些实现的一个致命缺点是它们都不支持多个进程对数据库的并发修改。它 们都没有提供并发控制（如记录锁）。 4.3+bsd提供了一个新的库db(3)，这个库支持3种不同的访问方式：（a）面向 记录，（b）hash与（c）b树。同样，db也没有提供并发控制（这一点在db手册的 bugs栏中说得很清楚）。seltzer与olson[1992]中说以后的版本将提供象大部分商 业数据库系统一样的并发控制功能。 绝大部分商业的数据库函数库提供多进程并发修改一个数据库所需要的并发控 制。这些系统一般都使用我们在12.3节中介绍的建议记录锁，并且用b+树来实现他 们的数据库。 16.3 函数库 在本节中，我们定义了这个数据库函数库的c语言接口，在下一节中再讨论其 实现。 当打开一个数据库时，通过返回值得到一个db结构的指针。这一点很象通过f open得到一个file结构的指针（5.2节），以及通过opendir得到一个dir结构的指 针（4.21节）。我们将用此指针作为参数来调用以后的数据库函数。 如果db_open成功返回 ，则将建立两个文件：pathname.idx 与pathname.dat，pathname.idx是索引文件 ，pathname.dat是数据文件。oflag被用作第二个参数传递给open（3.3节），表明 这些文件的打开模式（只读、读写或如果文件不存在则建立等）。如果需要建立新 的数据库，mode将作为第三个参数传递给open（文件访问权限）。 当我们不再使用数据库时，调用db_close来关闭数据库。db_close将关闭索引 文件与数据文件，并释放数据库使用过程中分配的所有用于内部缓冲的存储空间。 当我们向数据库中加入一条新的记录时，必须提供一个此记录的主键，以及与 此主键相联系的数据。如果此数据库存储的是人事信息，主键可以是雇员号，数据 可以是此雇员的姓名、地址、电话号码、受聘日等等。我们的实现要求主键必须是 唯一的（比方说，我们不会有两个雇员记录有同样的雇员号）。 #include "db.h" int db_store( db *db, const char *key, const char *data, int flag ) ; 返回：0表示成功，非0表示错误（见 key与data是由null结束的字符串。它们可以包含除了null外的任何字符，如 换行符。 flag只能是db_insert（加一条新记录）或db_replace（替换一条已有的记录 ）。这两个常数定义在db.h头文件中。如果我们使用db_replace，而记录不存在， 返回值为-1。如果我们使用db_insert，而记录已经存在，返回值为1。 通过提供主键key可以从数据库中取出一条记录。 #include "db.h" char *db_fetch( db *db, const char *key ) ; 返回：指向数据的指针表示成功，null表示记录没有找到。 如果记录找到了，返回的指针指向与主键联系在一起的数据。 通过提供主键key我们也可以从数据库中删除一条记录。 #include "db.h" int db_delete( db *db, const char *key ) ; 返回：0表示成功，-1表示记录没有找到。 除了通过主键访问数据库外，也可以一条一条记录地访问数据库。为此，我们首 先调用db_rewind回到数据库的第一条记录，再调用db_nextrec来读每个顺序的记 录。 #include "db.h" void db_rewind( db *db ) ; char *db_nextrec( db *db, char *key ) ; 返回：如果成功返回指向数据的指针，null表示到了数据库的 如果key是非null的指针，db_nextrec将当前记录的主键存入key中。 db_nextrec不保证记录访问的次序，只保证每一条记录被访问恰好一次。如果 我们顺序存储三条主键分别为a、b、c的记录，我们无法确定db_nextrec将按什么 顺序返回这三条记录。它可能按b、a、c的顺序返回，也可能按其它顺序。实际的 顺序由数据库的实现决定。 这七个函数提供了数据库函数库的接口。接下来介绍我们的实现。 16.4 实现概述 大多数数据库访问的函数库使用两个文件来存储信息：一个索引文件与一个数 据文件。索引文件包括索引值（主键）与一个指向数据文件中对应数据记录的指针 。有许多技术可用来组织索引文件以提高按键查询的速度与效率，hash表与b+树是 两种常用的技术。我们采用固定大小的hash表来组织索引文件结构，并采用链表法 解决hash冲突。在介绍db_open时，我们曾提到将建立两个文件：一个以.idx为后 缀的索引文件与一个以.dat为后缀的数据文件。 我们将主键与索引以null结尾的字符串形式存储--它们不能包含任意的二进制 数据。有些数据库系统用二进制的形式存储数值数据（如用1、2或4个字节存储一 个整数）以节省空间，这样一来使函数复杂化，也使数据库文件在不同的平台间移 植比较困难。比方说，我们在网络上有两个系统使用不同的二进制格式存储整数， 如果我们想要这两个系统都能够访问数据库就必须解决这个问题（今天不同体系结 构的系统共享文件已经很常见了）。按照字符串形式存储所有的记录，包括主键与 数据，能使这一切变得简单。这确实会需要更多的磁盘空间，但随着磁盘技术的发 展，这渐渐不再构成问题。 db_store要求对每个主键，最多只有一个对应的记录。有些数据库系统允许多 条记录使用同样的主键，并提供方法访问与一个主键相关的所有记录。另外，我们 只有一个索引文件，这意味着每个数据记录只能有一个主键。有些数据库允许一条 记录拥有多个键，并且对每一个键使用一个索引文件。当加入或删除一条记录时， 要对所有的索引文件进行相应的修改。（一个有多个索引的例子是雇员库文件，我 们可以将雇员号作为键，也可以将雇员的社会保险号作为键。由于一般雇员的名字 并不保证唯一，所以名字不能作为键。） 图16.1是我们的数据库实现的基本结构。索引文件由三部分组成：空闲链表指 针、hash表与索引记录。图16.1中所有叫做ptr的字段中实际存储的是以ascii字符 串形式记录的在文件中的偏移量。 图16.1 索引文件与数据文件结构 当给定一个主键要在数据库中寻找一条记录时，db_fetch根据主键计算hash值 ，由此hash值可确定一条hash链（chain ptr字段可以为0，表示一条空的hash链） 。沿着这条hash链，我们可以找到所有有同样hash值的索引记录。当我们遇到一个 索引记录的chain ptr字段为0时，表示我们到达了此hash链的末尾。 下面让我们来看一个实际的数据库文件。程序16.1建立了一个新的数据库，并 且加入了三条记录。由于我们将所有的字段都以ascii字符串的形式存储在数据库 中，所以我们可以用任何标准的unix工具来查看索引文件与数据文件。 $ ls -l db4.* -rw-r--r-- 1 stevens 28 oct 30 06:42 db4.dat -rw-r--r-- 1 stevens 28 oct 30 06:42 db4.idx $ cat db4.idx 0 53 35 0 10alpha:0:6 0 10beta:6:14 17 11gamma:20:8 $ cat db4.dat data1 data for beta record3 #include "db.h" ... 下一页
