【文件属性】：
文件名称：实现概述-数据流图到模块结构图的直接转换方法
文件大小：5.82MB
文件格式：PDF
更新时间：2021-06-22 07:37:14
APUE UNIX
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环境高级编程
空闲链表上第一条索引记录的位移量
散列表 索引记录
索引文件
散列表上第一条索引
记录的位移量
散列表上下一条索引
记录的位移量
数据文件
一条数据记录
一条索引记录