数据库存储介质及使用场景

（一）数据库存储设备

计算机中有两级存储，分别是主存和辅存。数据库作为一类特殊资源，主要保存在磁盘等外存介质上。根据访问数据的速度、成本和可靠性，存储介质可分成以下六类。

1.高速缓冲存储器

高速缓冲存储器是最快、最昂贵的储存介质。高速缓冲存储器一般比较小，它的使用由操作系统来管理。在数据库系统中，我们不考虑高速缓冲存储器的存储管理。

2.主存

主存又称内存或主存储器，用于存放可被处理的数据，是计算机机器指令执行操作的地方。由于其存储量小（一般以MB为单位）、成本高、存储时间短，而且发生电源故障或者系统崩溃时，里面的内容一般会丢失，因此它在数据库中仅作为数据存储的辅助实体，如作为工作区（Work Area，数据加工区）、缓冲区^[3]（Buffer Area，磁盘与主存的交换区）等。

3.快闪存储器

快闪存储器也称电子可擦除可编程只读存储器。快闪存储器不同于主存储器的地方是，在电源故障发生时数据可被保存下来。从快闪存储器读数据的时间小于100ms，大致等于从主存储器中读数据的时间。然而，向快闪存储器写数据是非常复杂的，一个数据写入一次需要4～10s，而且数据不能被直接覆盖。要覆盖已经被写过的快闪存储器，必须一次性擦除整个快闪存储器，然后它才可以被再次写入一次。快闪存储器的另一个缺点是它只支持有限的擦除次数，其范围为10 000～100 000。在低成本计算机系统中，如在嵌入至其他设备的计算机系统中，快闪存储器作为磁盘的替代物来存储少量数据（5～10MB）已经非常流行。

4.磁盘

磁盘存储器又称二级存储器或次级存储器。由于它存储量大（一般以GB为单位），能长期保存，有一定的存取速度且价格合理，因此早已成为数据库真正存放数据的物理实体。通常情况下，整个数据库都存储在磁盘上。为了能访问到数据，必须将数据从磁盘移到主存储器。完成操作后，被修改的数据必须写回磁盘。磁盘存储器为直接存取存储器，因此在磁盘上可以按任意顺序读取数据（与顺序存取存储器不同）。在发生电源故障或者系统崩溃时，磁盘存储器不会丢失数据。

5.光盘

光盘存储器最流行的形式是只读光盘（CD-ROM）。数据通过光学方法存储在光盘上，并且可以被激光器读取。用于CD-ROM存储器的光盘是不可写的，但是可以提供预先记录的数据，并且可以装入驱动器或从驱动器中移走。另一种光盘存储器是“一次写，多次读”（WORM）光盘，它允许写入数据一次，但是不允许擦除和重写这些数据。这种介质用于数据的归档存储。此外，还有磁光结合的存储设备，可使用光学方法读取以磁方法编码的数据，并且允许对旧数据进行覆盖。

6.磁带

磁带具有较大的容量（从GB到TB），价格便宜并可以脱机存放。因为磁带必须从头顺序存取，是一种顺序存取存储器，所以数据存取也比磁盘慢得多。磁带一般用于存储磁盘或主存中的拷贝数据，是一种辅助存储设备，也称为三级存储器。

磁盘为现代计算机系统提供了大容量的辅助存储，其存储容量极大，大约在几个GB到几十个GB，甚至几百个GB。一个典型的大型商业数据库需要数百个磁盘。

（二）文件组织

数据组织中，数据项是基础，相互关联的多个数据项构成记录，同质的多个记录组成文件，而数据库以文件形式组织。文件结构由操作系统的文件系统提供和管理。从文件的组织形式看，分为逻辑结构和物理结构两种。逻辑文件组织有两种方式，一种是把文件看成无结构的流式文件，另一种是把文件看成有结构的记录式文件。记录式结构分为定长记录和变长记录两种，下面分别讨论。

1.定长记录

例如，对于关系模式SC（SN，C＃，G），可设计一个文件，其中各数据项定义如下。

SN：CHAR （8）；

C＃：CHAR （6）；

G：SMALLINT。

假设一个短整数为4个字节，那么每个记录占18个字节。

在系统运行时，有两个问题。

一是如果要删除一个记录，那么必须在被删位置上填补一个记录。

二是除非每块的大小恰好是18的倍数，否则可能有的记录横跨两个块，读/写这样的记录就要访问两个块。

（1）删除方法。

在定长记录文件中删除一个记录，可采用下面三种方法之一实现。

①把被删记录后的记录依次移上来。这是一种传统的方法，实现算法简单。根据概率，删除一个记录平均要移动文件中的一半记录。

②把文件中最后一个记录填补到被删记录位置中。相对上一种方法，这种方式移动量较少。

③把被删结点用指针链接起来。在每个记录中加一个指针，在文件中增设一个文件首部。文件首部中包括文件中的有关信息，其有一个指针指向第一个被删记录位置，所有被删结点用指针链接，构成一个栈结构的空闲记录链表。

（2）插入方法。

删除方式影响插入方法。删除时如果采用把被删记录链接起来的方法，那么插入操作可采用下列方法进行：在空闲记录链表的第一个空闲记录中填上插入记录的值，同时使首部指针指向下一个空闲记录；如果空闲记录链表空，那么只能把新记录插到文件尾。删除时，前两种方式由于文件中间不存在空闲，因此插入只能在文件尾进行。

定长记录文件的插入操作比较简单，因为插入记录的长度与被删记录的长度是相等的。在变长记录文件中操作就复杂了。

2.变长记录

实际应用中定长记录格式文件较多，但为了增强文件的灵活性，在数据库系统中有时需要文件中的记录是变长格式。例如，一个文件中有多种不同记录类型的记录，文件中允许记录类型的字段是变长的，允许记录中某字段可以出现重复组等。

变长记录的表示有字节串形式和定长形式两种。

（1）变长记录的字节串表示形式。

①尾标志法。这种形式是把每个记录看成连续的字节串，然后在每个记录的尾部附加“记录尾标志符”，表明记录结束。

②记录长度法。字节串表示形式的另一种方式是在记录的开始加一个记录长度的字段，读取数据时以此作为记录结束与否的标志。

字节串表示形式实现算法简单，但有两个主要缺点：其一，由于各记录的长度不一，因此被删记录的位置难以重新使用：其二，如果文件中的记录要加长，则很难实现，必须把记录移到他处才能实现，而移动的代价是很大的。

由于上述两个缺点，所以现在一般不使用字节串表示形式。在实际应用中，往往使用的是一种改进的字节串表示形式，称为“分槽式页”（Slotted Page Structure）。

在每块的开始处设置一个“块首部”，块首部中包括下列信息。

①块中记录数目。

②指向块中自由空间尾部的指针。

③登记每个记录的开始位置和大小信息。

在块中实际记录紧连着，并靠近块尾部存放。块中自由空间也紧连着，在块的中间。插入总是从自由空间尾部开始，并在块首部登录其插入记录的开始位置和大小。

记录删除时，只要在块首部将该记录的大小减1即可。同时，把被删记录左边的记录移过来填补，使实际记录仍然紧连着。当然，此时首部记录的信息也要修改。记录的伸缩也可使用这样的方法。在块中移动记录的代价也不高，这是因为一块的大小最多只有4KB。

在分槽式页结构中，要求其他指针不能直接指向记录本身，而是指向块首部中的记录信息登记项，这样块中记录的移动就独立于外界因素了。

（2）变长记录的定长表示形式。(www.xing528.com)

在文件系统中，往往采用一个或多个定长记录来表示变长记录的方法。具体实现时有两种技术：

①预留空间^[4]技术。取所有变长记录中最长的一个记录的长作为存储空间的记录长度来存储变长记录，如果变长记录短于存储记录长度，那么在主多余空间处填上某个特定的空值或记录尾标志符。该方法一般在大多记录的长度接近最大长度时才使用，否则使用时空间浪费很大。

②指针^[5]技术。记录长度相差太大时，预留空间的方法导致空间浪费较大，此时最为有效的形式就是指针技术。

（三）记录的组织

一个数据库往往由多个相互关联的文件构成，一个文件往往包含成千上万个记录。也就是说，记录是组成数据库的基础。这些记录总是要存放在磁盘存储器上。建立数据库不是目的，目的主要是在建立好的数据库平台上实现各种查询检索要求，即数据库处于不停的运行状态，所以查询效率就是应用中较为敏感的问题。存取效率不仅与存储介质有关，还与文件中记录的组织方式和存取方法有关。不同组织方式的文件的存取方法是不一样的，并且存取效率往往差别极大。

文件中记录的组织方式有四种。

1.无序文件

无序文件也称为堆文件，严格按记录输入顺序数据进行组织。记录的存储顺序与关键码没有直接的联系，常用来存储那些将来使用，但目前尚不清楚如何使用的记录。此类组织既可用于定长记录文件，也可用于非定长记录文件；记录的存储方法可以采用跨块记录存储方法，也可以采用非跨块记录存储方法。

无序文件的操作比较简单，其文件头部存储它的最末一个磁盘块的地址。插入一个记录时，首先读文件头，找到最末磁盘块地址，把最末磁盘块读入主存缓冲区，然后在缓冲区内把新记录存储到最末磁盘块的末尾，最后把缓冲区中修改过的最末磁盘块写回原文件。

无序文件查找效率比较低。要查找特定记录，必须从文件的第一个记录开始检索，直到发现满足条件的记录为止。如果满足条件的记录不止一个，那么就需要搜索整个文件。一般情况下，特定唯一记录的检索平均需搜索该文件所占磁盘块的一半。

无序文件的删除操作比较复杂，常用的方法主要有以下三种。

第一种方法，首先找到被删记录所在的磁盘块，然后读到主存缓冲区，在缓冲区中删除记录，最后把缓冲区内容写回到磁盘文件。这种方法会使文件中出现空闲的存储空间，需要周期性地整理存储空间，以避免存储空间的浪费。

第二种方法，在每个记录的存储空间中增加一标志位，标识记录删除与否，一般该标志常为空。删除一个记录时，将此记录的标志位置“1”，以后查找记录时跳过有该标志的记录。这种方法也需要周期性地整理存储空间，以避免存储空间的浪费。

第三种方法常用于定长记录文件，即删除一个记录时，总是把文件末尾记录移到被删记录位置。对于无序定长记录文件，若要修改记录值，只要找到记录所在的磁盘块，读入主存缓冲区，在缓冲区中修改记录，并写回磁盘即可。无序变长记录文件一般采用先删除再插入的方法来实现。

2.有序文件

有序文件是指记录按某个（或某些）域的值的大小顺序组织，一般较为常用的是按关键字的升序或降序排列。也就是说，每个记录增加一指针字段，根据主键的大小用指针把记录链接起来。该组织的文件由于按关键字先后有序，所以可实现分块查找、折半查找和插值查找，查询效率较高。起始建立文件时，应尽可能使记录的物理顺序和查找键值的顺序一致。这样在访问数据时可减少文件块访问的次数，提高查询效率。若文件记录个数为N，则折半法查找的时间复杂性为O（lbN），插值查找的时间复杂性为O（blbN）。

顺序文件可以很方便地按查找键的值的大小顺序读出所有的记录。顺序文件上的插入和删除比较复杂，需要保持文件的顺序，耗费时间较大。删除操作可以通过修改指令实现，或建立删除标志位，周期性整理存储空间以便插入时使用。

顺序文件中插入新记录时必须首先找到这个记录的正确位置，然后移动文件的记录，为新记录准备存储空间，最后插入记录。此时，移动和新记录的插入位置密切相关，平均移动量为文件记录的一半。由此可见，插入操作是相当及时的。为了减少插入操作的时间复杂性，可以在每个磁盘块为新记录保留一部分空闲空间，以减少记录插入时的移动量。若采用指针方式组织记录，插入时需要两步操作：首先在指链中找到插入的位置，然后找到记录的块内，检查自由空间中是否有空闲记录。若有空闲记录，那么在该位置插入新记录，并加入指针链中；若无空闲记录，那么将新记录插入溢出块中。

对于查询条件定义在非排序域的查找操作来说，顺序文件没有提供任何优越性，查询操作按无序文件从第一个记录开始顺序搜索，查找时间与无序文件相同。

顺序文件的修改比较麻烦。若记录定长，修改的是非排序域，处理方法也是先找到记录读入内存缓冲区，修改后写回磁盘；修改排序域时，先删除修改记录，再插入修改后的记录。有序变长记录文件一般采用先删除再插入的方法来实现。顺序文件初始建立时，其物理顺序与查找键值顺序一般是一致的，但是在经过多次插入或删除操作后，这种一致的状态就会受到破坏，记录检索的速度会明显降低。此时就应该对文件重新组织一次，使其物理顺序和查找键值的顺序一致，以提高查找速度。

3.聚类文件

在关系系统中，相互关联的数据用基本表进行组织，一个基本表对应一个关系。在小型数据库系统中，数据量小，每个关系处理成一个文件。这种文件称为单记录类型文件，文件中每个记录是定长的，文件之间是分离的，没有联系。数据联系要通过关键码和查询语句的操作来实现。此时，一般的操作系统能处理这种文件。生活中一般使用的文件均属于此类。

随着数据量的增大，传统的单记录类型文件组所实施的各类操作使系统的性能和查询速度明显下降。采用聚集技术可降低I/O操作次数，提高查询度。通过在职工记录上建立链接，此后按职工检索其成绩数据时，搜索速度明显的变快了。可见在这种组织中，逻辑上相互关联的多个关系中的记录可集中存储在一个文件中，不同关系中有联系的记录存储在同一块内，通过降低I/O操作次数可极大提高查找速度。

形成聚类文件的基本文件是独立建立和管理的，物理结构也是独立的，只是在具体的应用中通过特定的DBMS建立聚类组织。

4.Hash文件

Hash（哈稀）文件又称为散列文件，是一种支持快速存取的文件存储方法。如果用该方式存储一个文件，必须指定文件的一个（或一组）域为查询的关键字，该域常称为Hash域。然后定义一个Hash域上的函数——Hash函数，以此函数的值作为记录查询的地址。

（1）散列概念。

根据记录的查找键值，使用一个函数计算得到函数值，作为磁盘块的地址，对记录进行存储和访问。这种方法称为散列方法。查询时该函数的值找到记录所在的磁盘块，读入主存缓冲区，然后在主存缓冲区中找到记录存储时也是根据Hash域计算存储块号，存入相应单元。在数据库技术中，一般使用“桶”作为基本的存储单位。一个桶可以存放多个记录。每个桶对应一个磁盘块，有唯一的编号。

散列技术中涉及一个Hash函数H。函数H是从K（所有查找键值的集合）到B（所有桶地址的集合）的一个函数，它把每个查找键值映象到地址集合中。

在文件中检索查找键值为K的记录，首先也是算H（K），求出该记录的桶地址，然后在桶内查找。在散列方法中，由于不同查找键值的记录可能对应于同一个桶号，因此一个桶内记录的查找键值可能是不相同的。所以，在桶内查找记录时必须检查查找键值是否为所需的值。在散列文件中进行删除操作时，一般先用前述方法找到想要删除的记录，然后直接从桶内删去即可。

（2）散列函数。

使用散列方法时，首先要有一个好的散列函数。好的散列函数在把查找键值转换成存储地址（桶号）时，一般满足下面两点：第一，地址的分布是均匀的，即产生的桶号尽量不能聚堆；第二，地址的分布是随机的，即所有散列函数值不受查找键值各种顺序的影响。

在日常应用中，最常使用的Hash函数是“质数余法”。

采用Hash方法时，总希望能通过计算将记录均匀分配到存储单元中去。实际上，无论采用哪一种方法，都不可避免地会产生碰撞现象，即两个或多个键号经过计算所得到的结果相同而发生冲突。

（3）散列方法。

下面介绍三种常用的Hash方法。

①简单Hash方法。

采用固定个数的Hash桶，即把文件划分为N个Hash桶，每个Hash桶对应一个磁盘块且都有一个编号。为了实现Hash编号到磁盘块地址的映射，每个Hash文件都具有一个Hash桶目录。第一号Hash桶的目录存储该Hash桶对应的磁盘块地址。

显然，每个Hash桶对应的磁盘块存储都具有相应Hash函数值的记录。如果文件的数据在Hash属性上分布不均匀，就可能产生桶溢问题，其处理方法采用上述封闭散列方法完成。查找记录时分两种情况处理。如果在Hash文件上进行形如“A＝a”的查询，其中A为Hash域，a为常数，则先计算H（A），得到桶号i，查阅桶目录找到该桶磁盘块链第一个磁盘块的地址，并顺着链扫描检查每一块，直到找到满足条件的记录或证明没有满足条件的记录：若上述A不是Hash域，则需要按无序文件的查找方法完成检索操作。

插入记录可以按如下方法处理：使用Hash函数计算插入记录的桶号，在桶的磁盘块链上寻找空闲空间，将记录存入。若桶上所有块均无空闲空间，此时向系统申请一个磁盘块，将新记录插入，并将新块链入桶的磁盘块链中。

Hash文件上的删除操作也分两种情况。如果已知想要删除记录的Hash域值，则运行Hash函数计算想要删除记录的桶号i，在桶的磁盘块链上找到想要删除记录，将其删除；如果不知道想要删除记录的Hash域值，则需要使用无序文件上记录删除的方法处理记录。删除记录后，如果当前磁盘块为空，则释放该磁盘块。

修改记录时，若想要修改的是Hash域，则通过先查询再删除后插入来完成；如果修改非Hash域，则先进行查找，将记录读入内存缓冲区，在缓冲区中完成修改，并写回磁盘。简单Hash方法也有自己的不足。第一，只能有效地支持Hash域上具有相等比较的数据操作。如果数据操作的条件不建立在Hash域上或不是相等比较，则数据操作的处理时间与无序文件相同。第二，由于Hash桶的数量一成不变，当文件记录较少时，将浪费大量存储空间。当文件记录超过一定数量以后，磁盘块链将会很长，影响记录的存取效率。

下面介绍的动态Hash方法，可能在某些方面会比简单Hash方法好一些。

②动态Hash方法。

在动态Hash方法中，Hash桶与磁盘块一一对应。此时Hash桶的数量不是固定的，而是随文件记录的变化而增加或减少。初始Hash文件只有一个Hash桶，当记录增加，这个Hash桶溢出时，它被划分为两个Hash桶，原Hash桶中的记录也被分为两部分。Hash值的第一位为1的记录被分配到一个Hash桶，Hash值的第一位为0的记录被分配到另一个Hash桶。当Hash桶再次溢出时，每个Hash桶被按上述规则划分为两个Hash桶。动态Hash方法需要一个用二叉树表示的目录。

Hash桶的划分过程是这样进行的：当插入一个具有01开始的Hash值的记录时，这个记录便被插入第三个Hash桶，产生溢出。这时，第三个Hash桶被划分为两个Hash桶，Hash值为010开始的记录被存储到划分出来的第一个Hash桶，Hash值为011开始的记录存储到划分出来的第二个Hash桶。当两个相邻Hash桶中记录的总数不超过一个磁盘块容量时，又可以将这两个Hash桶合并为一个Hash桶。

二叉树目录的级数随Hash桶的分裂与合并而增加或减少。如果选定的Hash函数能够把记录均匀地分布到各个Hash桶，二叉树目录将是一个平衡的二叉树。

③扩展的Hash方法。

扩展的Hash方法的Hash桶目录是一个含2d个磁盘块地址的一维数组，其中d称为Hash桶目录的全局深度。数据记录 Hash域值的前d位确定了所在的Hash桶编号。每个Hash桶对应的磁盘块都有局部深度，即d′，是确定Hash桶依赖的Hash函数值的位数。