直接转换方法：将数据流图映射为模块结构图的实现概述

16.4 实现概述 大多数数据库访问的函数库使用两个文件来存储信息：一个索引文件和一个数据文件。索 引文件包括索引值（关键字）和一个指向数据文件中对应数据记录的指针。有许多技术可用来 组织索引文件以提高按关键字查询的速度和效率，散列表和 B +树是两种常用的技术。我们采 用固定大小的散列表来组织索引文件结构，并采用链表法解决散列冲突。在介绍 d b _ o p e n时， 曾提到将建立两个文件：一个以 . i d x为后缀的索引文件和一个以 . d a t为后缀的数据文件。 我们将关键字和索引以N U L L结尾的字符串形式存储——它们不能包含任一的二进制数据。 有些数据库系统用二进制的形式存储数值数据（如用 1、2或4个字节存储一个整数）以节省空 间，这样一来使函数复杂化，也使数据库文件在不同的平台间移植比较困难。比方说，网络上 有两个系统使用不同的二进制格式存储整数，如果想要这两个系统都能够访问数据库就必须解 决这个问题（今天不同体系结构的系统共享文件已经很常见了）。按照字符串形式存储所有的 记录，包括关键字和数据，能使这一切变得简单。这确实会需要更多的磁盘空间，但随着磁盘 技术的发展，这渐渐不再构成问题。 d b _ s t o r e要求对每个关键字，最多只有一个对应的记录。有些数据库系统允许多条记录使 用同样的关键字，并提供方法访问与一个关键字相关的所有记录。另外，我们只有一个索引文 件，这意味着每个数据记录只能有一个关键字。有些数据库允许一条记录拥有多个关键字，并 且对每一个关键字使用一个索引文件。当加入或删除一条记录时，要对所有的索引文件进行相 应的修改。（一个有多个索引的例子是雇员库文件，可以将雇员号作为关键字，也可以将雇员 的社会保险号作为关键字。由于一般雇员的名字并不保证唯一，所以名字不能作为关键字。） 图1 6 - 1是数据库实现的基本结构。索引文件由三部分组成：空闲链表指针、散列表和索引 记录。图1 6 - 1 p t r字段中实际存储的是以A S C I I字符串形式记录的文件中的位移量。 图16-1 索引文件和数据文件结构 3 8 8 U N I X环境高级编程 空闲链表上第一条索引记录的位移量 散列表 索引记录 索引文件 散列表上第一条索引 记录的位移量 散列表上下一条索引 记录的位移量 数据文件 一条数据记录 一条索引记录