实现概述-hds ams 2500用户手册

16.4实现概述

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

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

d b _ s t o r e要求对每个关键字，最多只有一个对应的记录。有些数据库系统允许多条记录使用同样的关键字，并提供方法访问与一个关键字相关的所有记录。我们只有一个索引文件，这意味着每个数据记录只能有一个关键字。有些数据库允许一条记录拥有多个关键字，并且对每一个关键字使用一个索引文件。当加入或删除一条记录时，要对所有的索引文件进行相应的修改。（一个有多个索引的例子是雇员库文件，可以将雇员号作为关键字，也可以将雇员的社会保险号作为关键字。由于一般雇员的名字并不保证唯一，所以名字不能作为关键字。）

图16-1是数据库实现的基本结构。索引文件由三部分组成：空闲链表指针、散列表和索引记录。图16-1 p t r字段中实际存储的是以A S C I I字符串形式记录的文件中的位移量。更多关于散列表和散列冲突的信息，可以参考这篇文章 散列表与散列冲突。

图16-1索引文件和数据文件结构

散列表上第一条索引记录的位移量

散列表上下一条索引记录的位移量

数据文件一条数据记录

一条索引记录

了解更多关于数据存储与索引的内容，请点击 数据存储与索引。