搜索
第五章数据库文件存储技术主要内容5.1文件组织5.2索引技术5.3哈希技术5.1文件组织在外部存储设备中，数据库以文件形式组织，而文件有记录组成。从文件的组织形式看，分为逻辑结构和物理结构两种。逻辑结构文件组织有两种方式，一种是把文件看成无结构的流式文件，另一种是把文件看成有结构的记录式文件文件中记录的组织方式有堆文件、顺序文件、聚集文件和哈希文件四种。（1）堆文件在堆文件中，记录可以放在文件的任何位置上，一般以输入顺序为序。（2）顺序文件在顺序文件中，记录按查找某个关键码值的大小顺序组织存储的。（3）聚集文件在聚集文件中，一个文件可以存储多个关系记录，不同的关系中有联系的记录存储在同一块内，可以提高查找速度和I/O速度。（4）哈希文件把根据记录的某个属性值通过哈希函数求得值作为记录的存储地址（即“块号”），这种技术通常与索引技术连用。5.1.1文件组织形式本节讨论逻辑文件中的记录在物理文件中将如何实现记录式结构分为定长记录和变长记录两种1.定长记录一般在文件中的记录有固定长度，这种长度一般都是一由文件记录确定。例如：对于关系模式SC（Snum,Cnum,Score）可以设计一个文件，其中各数据项定义如下：Snum：CHAR（8）；Cnum：CHAR（9）；Score：SMALLINT；SnumCnumScoreS03101C0293S030303C0183S030402C0368S030304C0368S030404C0490S030101C0687S030102C0477S030304C0486S030101C0586S030101C0489图5.1定长记录的文件SnumCnumScoreS03101C0293S030402C0368S030304C0368S030101C0687S030304C0486S030101C0489图5.2删除记录2，5，7，9后的文件结构如上图每条记录包含姓名、学号、班级三条信息，在每条记录中对应的信息占相同的字节数，所以每条记录的长度一定，构成一个含有四条记录的定长记录文件。在系统运行时存在两个问题：（1）删除：删除后是在其位置补充一个记录还是忽略这个位置。（2）长度：若物理上每个块的大小不等于每个记录的长度倍数，则必然在读这样的记录时要访问两个块。⑴删除方法在定长记录文件中删除一个记录，可采用下面三种方法之一实现：l)把被删记录后的记录依次移上来。这是一种传统方法，实现思想简单。根据概率，删除一个记录平均要移动文件中的一半记录。2)把文件中最后一个记录填补到被删记录位置。相对上一种方法，这种方式移动量较少。3)把被删结点用指针链接起来。在每个记录中增加一个指针，在文件中增设一个文件首部。文件首部中包括文件中有关信息，其中有一个指针指向第一个被删记录位置，所有被删结点用指针链接，构成一个栈结构的空闲记录链表。譬如在图5.1中删除记录2、5、7、9文件如图5.2图5.3变长记录的字节串表示形式⑵插入方法删除方式影响插入方法。删除时如果采用把被删记录链接起来的方法，那么插入操作可采用下列方法：在空闲记录链表的第一个空闲记录中，填上插入记录的值，同时使首部指针指向下一个空闲记录；如果空闲记录链表为空，那么，只能把新记录插到文件尾。删除时如果采用前两种方式，由于文件中间不存在空闲，所以插入只能在文件尾进行。定长记录文件的插入操作比较简单，因为插人记录的长度与被删记录的长度是相等的。在变长记录文件中操作就复杂多了。2.变长记录两种形式：①变长记录的字节串表示形式；②变长记录的定长表示形式。⑴变长记录的字节串表示形式①尾标志法这种形式是把每个记录看成连续的字节串，然后在每个记录的尾部附加“记录尾标志符”（∧）,表明记录结束。图5.1的定长记录文件可以用图5.3的格式表示。②记录长度法字节串表示形式的另一种方式是在记录的开始加一个记录长度的字段来实现，读取数据时以此作为记录结束与否的标志。字节串表示形式实现算法简单，但有两个主要缺点；其一，由于各记录的长度不一，因此被删记录的位置难于重新使用；其二，如果文件中的记录要加长，则很难实现，必须把记录移到它处才能实现，移动的代价是很大的往往使用的是一种改进的字节串表示形式，称为“分槽式页”(Slotted-pageStructure),如图5.4所示。记录数目自由空间块首部记录大小记录位置在每块的开始处设置一个“块首部”，块首部中包括下列信息：①块中记录的数目；②指向块中自由空间尾部的指针；③登记每个记录的开始位置和大小的信息。⑵变长记录的定长表示形式1)预留空间技术预留空间技术是取所有变长记录中最长的一个记录的长度作为存储空间的记录长度，来存储变长记录。如果变长记录短于存储记录长度，那么在多余空间处填上某个特定的空值或记录尾标志符。例如图5.3的字节串表示形式可以用图5.5的预留空间技术实现。该方法一般在大多数记录的长度接近最大长度时才使用，否则使用时空间浪费很大。2)指针技术记录长度相差太大时，预留空间的方法会导致空间浪费较大，此时最为有效的形式就是指针技术。譬如图5.6中把属于同一个学生的记录链接起来。图5.6的缺点是，同一条链中，只有第一个记录中姓名是有用的，后面记录中姓名空间浪费了。为解决这个问题，可使用改进的指针形式，在一个文件中使用两种块，即固定块和溢出块。用固定块存放每条链中第一个记录，其余记录全放在溢出块中。这两种块中记录的长度可以不一样，但同一种块内的记录是定长的。图5.7表示文件的固定块和溢出块结构。5.1.2顺序文件组织顺序文件是指记录按某个（或某些）域的值的大小顺序组织，一般最为常用的是按关键字的升序或降序排列，即每个记录增加一个指针字段，根据主键的大小用指针把记录链接起来。该组织的文件由于按关键字先后有序，所以可实现分块查找、折半查找和插值查找，查询效率较高。起始建立文件时，应尽可能使记录的物理顺序和查找键值的顺序一致。这样在访问数据时可减少对文件块访问的次数，提高查询效率。图5.8是顺序文件的例子，记录按Snum值升序排列。顺序文件可以很方便地按查找码的值的大小顺序读出所有的记录。删除操作可以通过修改指针实现；或建立删除标志位，周期性整理存储空间以便插入时使用。顺序文件中插入新记录必须首先找到这个记录的正确位置，然后移动文件的记录，为新记录准备存储空间，最后插入记录。采用指针方式组织记录，插入时需要分两步操作：首先在指针链中找到插入的位置；然后在找到记录的块内，检查自由空间中是否有空闲记录，若有空闲记录，那么在该位置插入新记录，并加入到指针链中，若无空闲记录，那么将新记录插入到溢出块中。在图5.8中插入一个新记录（S030101,C03,80），就得到图5.9。5.1.3聚集文件组织在关系数据库中一般一个文件存储一个关系，而在聚集文件组织中一个文件可以存储多个关系的记录，不同关系中有联系的记录存储在一起可以提高查找速度。在关系系统中，相互关联的数据用基本表进行组织，一个基本表对应一个关系。在小型数据库系统中，数据量小，每个关系处理成一个文件。这种文件称为单记录类型文件，文件中每个记录是定长的，文件之间是分离的，没有联系。数据联系要通过关系码和查询语句的操作实现。此时，一般的操作系统便能管理这种文件。随着数据量的增大，传统的单记录类型文件组织所实施的各类操作使系统的性能和查询速度明显下降。例如：教学数据库中S1(Snum,Sname,Sbirth，Ssex,)，SC(Snum,Cnum,Score)，如果将每个关系组织成一个文件，那么查找学生的成绩，就要做连接操作：SELECTS1.Snum,Sname,Cnum,ScoreFROMS1，SCWHERES1.Snum=SC.Snum当关系S1和SC数据量很大时，上述查询操作由于I/0次数较多，其速度是很慢的。如果把S1和SC的数据放在一个文件内，并且尽可能把每个学生的信息和其成绩放在相邻位置上，那么在读学生信息时，能够把学生信息和连在一起的成绩信息一次读到内存里，可大大降低I/O操作次数，提高系统效率。这种新的文件组织形式即为聚集文件。该文件允许一个文件由多个关系的记录组成，即多记录类型文件。聚集文件的管理由数据库系统实现。5.2索引技术5.2.1基本概念索引是一种表形式的数据结构,由给定的一个或一组数据项组成。设ki(i=1,2,…，n)为某一关系(表)中按其某种逻辑顺序排列的主码值，其对应的记录RKi的地址为A(RKi)，索引的实质是按照记录的主码值将记录进行分类，并建立主码值到记录位置的地址指针。图5.12是一种学生关系及其索引的图示表示方式。S030101。S030303。S030102。。S030402。S030304。…………………………任伟平S030402……徐圣孟S030304……张璐S030303……冯玉亮S030102……雷吉平S030101数据区（学生关系S）主码数据指针索引表图5.12学生关系索引方式索引的组织方式主要有线性索引和树形索引两类。线性索引是一种按照索引项中数据项的值排序的索引方式，其中数据项一般为主码。也就是说，线性索引一般是如图5.11的按照主码值排序的一种索引方式。树型索引是将索引组织成树形结构,树形索引既能进行快速查找,又易于索引结构的动态变化。最常用的树形结构的索引是B树及其变种B+树。5.2.2顺序索引1．稠密索引(DenseIndex)在稠密索引方式中，按主码值排序建立索引项,但记录的存放顺序是任意的。由于索引项的个数与记录的个数相等,也就是说索引项较多,所以称为稠密索引。对于稠密索引来说,由于数据记录的存放顺序是任意的,所以实现对关系中记录删、插、改的关键是索引表中主码值的查找问题。由于按主码值排序的稠密索引表相当一个顺序文件,主码值的查找可以用顺序文件的查找方法,即当主码值不大时采用顺序扫描方式,当主码值较大时采用二分查找等方式。稠密索引的优点是查找、更新数据记录方便,存取速度快,记录无须顺序排列。缺点是索引项多,索引表大,空间代价大。2.稀疏索引（SparseIndex)在稀疏索引方式中,所有数据记录按主码值顺序存放在若干个块中,每个块的最大主码值(即该块最后一个数据记录的主码值)和该块的起始地址组成一个索引项,每个块中的索引项按主码值顺序排列组成索引表。由于是每个块只有一个索引项,也就是说索引项较少，所以称为稀疏索引。5.2.3B+树索引文件图5.13给出了B+树的模型表示形式，它的上面是一棵B树，由存放各级索引的索引块组成；下面是所有叶结点组成的一个顺序集，由存放记录索引项的记录索引块组成。在B+树中，由于出现在B树索引中的主码值均要出现在叶结点中，所以B树索引中的索引项就仅能起路标作用了。也就是说，由于B+树中主码值所属的数据记录的位置直到叶结点才给出来，所以在查询时，即使在非叶结点上找到了与给定值相等的主码值，也必须继续向下直到叶结点为止。随机查询顺序查询 Ｂ树索引 （索引块）顺序集 （记录索引块）图5.13B+树的模型B+树基本上遵从B树的定义和约定。而一棵m阶的B+树与一棵m阶的B树的区别在于：(1)在B+树的叶结点中包含了B+树中的全部主码值，且其中的所有索引项按其主码值的递增顺序从左到右而顺序链接；而在B树中，由于主码值分布在各个索引层上，所以叶结点中没有包含B树中的全部主码值，且各叶结点间的主码值没有顺序链接。(2)在B+树中，所有非叶结点包含了其子树中的最大(或最小)主码值；而在B树中，非叶结点中的主码值不再出现在其子树中。(3)在B+树中，查询任何数据记录所经历的路径是等长的；而在B树中，不同数据记录的查询路径是不等长的。(4）在B+树中可以采用两种方式进行查询，当随机查询时，通过B树索引找到要查找的数据记录，从根部开始找；当顺序查询时，通过顺序集找到要查找的数据记录，从顺序集的链头或通过B树索引得到某一顺序结点并开始查找。而在B树中，只有从根部随机查找的一种