16.4实现概述

大多数数据库访问的函数库使用两个文件来存储信息：一个索引文件和一个数据文件。索引文件包括索引值（关键字）和一个指向数据文件中对应数据记录的指针。许多技术可以用来组织索引文件以提高按关键字查询的速度和效率，散列表和B+树是两种常用的技术。在这个实现中，我们采用固定大小的散列表来组织索引文件结构，并采用链表法解决散列冲突。

在介绍db_open时，我们曾提到将建立两个文件：一个以.idx为后缀的索引文件和一个以.dat为后缀的数据文件。关键字和索引以NULL结尾的字符串形式存储——它们不能包含任何二进制数据。有些数据库系统用二进制形式存储数值数据（如用1、2或4个字节存储一个整数）以节省空间，这样一来使函数复杂化，也使数据库文件在不同平台间移植比较困难。比如，网络上有两个系统使用不同的二进制格式存储整数，如果想要这两个系统都能访问同一个数据库，就必须解决这个问题（今天不同体系结构的系统共享文件已经很常见了）。按照字符串形式存储所有记录，包括关键字和数据，能使这一切变得简单。这确实会需要更多的磁盘空间，但随着磁盘技术的发展，这渐渐不再构成问题。

db_store要求每个关键字最多只有一个对应的记录。有些数据库系统允许多条记录使用同样的关键字，并提供方法访问与一个关键字相关的所有记录。我们只有一个索引文件，这意味着每个数据记录只能有一个关键字。有些数据库允许一条记录拥有多个关键字，并且对每一个关键字使用一个索引文件。当加入或删除一条记录时，要对所有的索引文件进行相应的修改。

一个有多个索引的例子是雇员库文件，可以将雇员号作为关键字，也可以将雇员的社会保险号作为关键字。由于一般雇员的名字并不保证唯一，所以名字不能作为关键字。

图16-1是数据库实现的基本结构。索引文件由三部分组成：空闲链表指针、散列表和索引记录。图16-1中的ptr字段实际存储的是以ASCII字符串形式记录的文件中的位移量。

想要了解更多关于散列表和散列冲突的内容，可以参考《散列表与散列冲突》。如果对散列表的实现原理感兴趣，可以查看《散列表实现》和《数据结构散列表》。这些资源将进一步阐述散列表的设计与应用，让你对数据库索引结构有更深的理解。