第二章数据库的存储结构.doc

第2章 数据库的存储结构本章学习目标本章主要介绍了基本的文件组织方式及各自的特点，并在此基础上介绍了系统所采用的倒排表、索引链接文件与多重链表文件索引、+树等快速文件查找处理方法。通过本章学习，读者应该掌握以下内容：l l 顺序文件、链表文件、随机存取文件、索引组织文件等文件组织方式的特点l l 倒排表的操作l l +树的组织结构与基本操作在数据库系统设计时必须考虑如何在机器上实现的问题，要求能将各种数据存储在机器内，而且要能反映各种数据之间的联系；要求存储、维护尽可能方便高效；要求检索 、使用数据操作简单，运行效率高。为此要讨论各种存储组织结构和各类索引结构。数据库是利用文件系统来完成数据的存取的，数据及相关联系可在一个文件中存放，也可分别存放；文件有顺序文件，随机文件等不同类型；顺序文件又有按某个码排序的文件及按记录录入先后次序存放的文件等不同。2.1基本文件组织2.1.1顺序文件组织在顺序文件中，记录被物理地按地址次序排列，排列顺序为按某一码值的升或降序，也可为记录录入的先后次序。按码值排序时，其顺序还与存储方式有关。有按二进制数和ASCII码存储两种形式，如按前者，根据码值数值大小排序。如按后者，可视为字符串，对二个字符串比较时，从左边第一个字符起进行比较，直到对应字符不相同为止，此时该二字符的ASCII码值较大者对应的字符串较大。例如“ABCDEF”和“ABZ”二个串，第三个字符对应不相同，其左边各字符对应都相同，则因“ABZ”的第三个字符的ASCII码值较大，这个串的值也就较大。采用这类排序文件，优点是在查找时可利用二分法，插值算法和分区算法等方法加快查找速度，缺点是在进行数据录入，修改、删除时要花费大量时间用于排序，非常耗时。而且，对于数据库数据的检索要求将是多方面的，例如按姓名查找某个人，或者按专业来查找一批人，或者按姓名与专业来查找一批人等，不可能按每一种检索要求生成一个排序文件，因为那样做占据空间太多，维护也无法进行。因此一般维护工作量大或检索内容较多的系统，都采取按记录录入先后次序安排记录的方式顺序存放数据。再利用索引文件加快查找速度。VFP数据表文件就采用顺序文件组织方式，同时提供多种索引方式以利于数据查找和使用。2.1.2 链表结构文件组织链表结构组织的文件的基本特点是数据在物理上可以任意存放，利用指针表现数据间的逻辑关系。指针又分为单链表，环链表，双向链表等不同形式。在数据库中，这种结构的优点是记录的增删容易实现，其主要问题在于只能按指针顺序检索，速度较慢。IMS数据库中记录不等长，采用链表结构组织数据，检索时一般从根片段值开始，根据根片段值的关键字大小进行查找。利用顺序文件和其他结构文件相结合进行存储，例如采用顺序文件ISAM和溢出顺序文件OSAM或顺序文件ISAM和虚拟存储文件VSAM两个文件来存放数据，将所有记录开始部分划分成等长的一段，在ISAM中按顺序方式存放；每条记录剩余部分按先后次序存放于第二个文件中，第一个文件中数据通过指针与第二个文件相联系。由于在第一个文件中每个记录取出部分均等长，因此可较容易计算欲检索内容的大致存放位置，从而大大加快检索速度。例如图1.4 数据存储结构如图2.1所示。 这类结构可以实现从头开始循链表查询上述问题，这是层次数据库组织数据的方法之一。在关系数据库VFP中，设计有备注字段（M）和通用字段(G)两种数据类型，前者用于存放如履历、文件内容、使用说明等这样一些数据。后者用于存放如相片、图片、数值文件等内容，各条记录中这类数据内容可有可无，长度相差甚远，如用等长方式存储，则占用存储空间太多，许多是空的，不便管理也影响效率。在VFP中采用DBF、 FPT、 TBK三种文件分别存放一般数据、备份字段数据、通用字段数据，在DBF文件中，相应的备注（M）型和通用（G）型数据单元中只存放指针，指向相应在FPT和TBK文件中的内容。在DBTG网状数据库中，“系”结构采用了双向链表和环链表结构两种指针结构。使用单向链表从系主查找成员比较方便，但要查找每个结点的前趋结点则困难。使用双向链表，每条记录有一个指针指向按顺序它的下一个结点，同时又有一个指针指向其前趋结点，这样就可解决上述二个问题，删除操作也将变得容易。环链表是一个首尾相接的线性表，查找时可以从任意一个单元开始直至遍历整个环，也易于从一个环进入到另一个环。DBTG网状数据库还采用了指针阵列，指向系主记录的物主指针等结构。2.1.3随机存取文件组织（Hash文件组织）这类文件组织利用散列（Hash）函数Y=F（X）把码值映射成记录存储地址，直接存取。其中X为码值，y为地址。知道码值立即可算出地址，一般说来查找效率很高。影响这类存储方法效率的关键在于冲突发生的频率，所谓冲突，是指多个记录计算后取得的存储地址相同，必须采用一定的算法处理其存储位置。采用这类文件组织需要设计恰当的Hash函数，以求尽可能减少冲突并设计发生冲突时的算法。为减小冲突，常利用“桶”作为编址的基本单位。把若干存储单元作为一组并以同样的地址加以标识。例如图2.2所示，一个有N个桶的Hash文件，每个桶可装K条记录，当桶已装满后按溢出处理方式处理。上述存储结构也是IMS采用的一种存储结构。2.2索引文件组织记录按录入先后次序存储，数据维护比较方便，但检索速度较慢。其原因之一是因为数据库的数据量比较大，在对它处理时，一般需经过多次内外存数据交换，多次访问磁盘与寻道的速度远较机内数据传送和CPU处理速度要慢得多，检索速度一般决定于读写盘次数，访问次数越多，检索速度就越慢。每次读写盘交换的最大数据存储区称为块，在块内数据检索时间常可忽略不计。其二，是因为对检索内容未予排序，只能采用顺序查找方式。若供查询记录数为N时，平均查找到一条记录约需N/2次比较。采用排序文件在数据库系统中一般不具实用性，因为排序文件与原文件规模相同，不可能对各类检索生成排序文件。为此数据库常采用索引文件组织，目的在于提高检索效率。2.2.1 索引文件用户检索要求总是针对某一个属性或某几个属性进行。例如查找姓名为王平的记录是针对姓名检索；求年龄大于25的学生记录是针对年龄检索；求姓王且年龄大于25的学生记录是针对姓名和年龄检索。我们称查找针对的属性或属性组为查找字。 索引项由查找字值和指针组成，结构为：(查找字值，指针)。由索引项构成、并按查找字排序的文件称索引文件。对每条记录生成一个索引项的索引文件又称稠密索引。由于索引项远小于一般记录长度，因此索引文件规模远小于原文件。如果内外存交换数据的单位为块，一个索引文件的大小大于块的大小，不能一次将索引文件调入内存，可再建立高一层索引，可以将原索引文件分段，取每段最末一个索引项的查找字值及其在索引文件中的地址指针构成该级索引项，这样构成的索引文件称稀疏索引。可以一级级建下去直到索引文件的大小不超过块大小为止。在检索时，首先从最高层索引查起，找到欲查记录在下一级索引的哪一块中，再一级级查下去，直到查到欲查记录(或证实文件中无欲查记录)，从原文件中取出检索结果。这样将使内外存互访次数降至最小，读盘次数借助直接存取技术可小到等于索引级数加1。 索引文件规模小，容易维护，在VFP中有二类索引文件，独立索引文件（.IDX文件）和复合结构索引文件（.CDX文件）。使用独立索引文件前要求先打开索引文件。如在打开索引的情况下，对原表进行录入、修改、删除等操作，索引文件均会自动更新。如在对数据维护之前未打开索引文件，则在数据维护完成后必须重建索引或更新索引。在VFP中可将多个索引保存在一个文件中，其文件名与表名相同， 后缀为CDX，称为复合结构索引文件，在使用表时，该文件中索引将被自动打开。复合结构索引文件在建库或修改库结构时建立。VFP中索引有四种类型：1.主索引，每个表只能建一个主索引。其索引关键字中不允许有重复值。2.候选索引，每个表可建多个候选索引，其索引关键字中不允许有重复值。3.唯一索引，允许出现重复值，但利用它只保存重复值第一个值的索引项。4.普通索引，允许出现重复值，可决定记录处理顺序。无任何索引打开时，显示或处理的顺序按存入先后次序，称物理顺序。若有索引打开，显示或处理顺序按当前索引排序顺序，称为逻辑顺序。2.2.2 非关键字索引文件如果查找字值是无重复的，利用上述索引文件可以很快查到记录。但是许多查找内容的值是可以重复的，如班级名称，专业名称，职务，性别等，在一个表中会有许多相同的取值；还有一些查找内容，检索目标涉及多个属性，例如查询计算机专业全体班干部数据，就涉及专业和职务两方面属性。这时采用前述索引文件查询的速度仍较慢，为此需设计其它索引结构。1.索引链接文件与多重链表文件索引。索引链接文件由非关键字索引构成的索引表及若干个链接文件构成。非关键字索引的索引项由查找字和一个指针组成，每个索引项的指针指向其范围内第一条记录的地址，该范围内其他记录由指针顺序相连，如图2.3所示，查找字是职称。这种索引链接文件对于每一个查找字可关联多条记录，用于非关键字索引查找有较高效率。例如上例中，查有哪些老师是教授，共有多少名教授，所有教授的数据等这类问题。使用索引链接文件就比较方便，循第一条链查就可以了。实际问题又往往涉及二个以上检索条件，例如查所有男教授数据等。可建立多个索引，多个链表，这类文件又称为索引多链表文件。例对职称建立一个索引链表，对性别建立一个链表，如欲查找所有男教授数据，可先查出所有教授姓名，再在性别链中查出这些教授有哪些在男性链表中，取出这些教授的数据。参见图2.4。循教授链查职工有王平、李斌，再循男性链查，可以知道他们都为男教授。上述方法对非关键字查找能提高查找效率，但是对每一个条件的查找都只能循链表进行，当链表较长时，查找并不方便。我们还看到，查找效率与算法有关，例如上例中，如先按性别查出全体男教师记录，再查哪些为教授，需比较三次，而先查哪些为教授再查其中哪些为男性，只需比较二次。这种方法如要查某个范围内数据也不方便，例如要查找职称为副教授以上的男教师记录，则需先查出所有男教师记录，再分别在教授、副教授等系列链表中逐一核对，算法比较复杂。2. 倒排表倒排表索引项由查找关键字及相关记录地址(指针)构成，如图2.5所示。由倒排表进行组合条件查询时,对每一条件在倒排表中查出满足条件的记录的地址集合，之后进行求交集的运算，找到满足组合条件的记录，之后就可从主文件中查出相应数据。例如求工资大于1000元副教授职称以上男教工数据，则可分别得到工资为1100元的集合1，工资1200元的集合3 ，求得工资大于1000元教师地址集合，1U3=1，3；再求教授的集合1，3和副教授集合2，求得副教授职称以上教师地址集合1，3 U 2=1,2,3，再由男教师地址集合1,3,4等三个集合求取交集1，31,2,31, 3,4=1，3。如只求满足条件的教工人数，可回答为二，如要进一步取出相应记录数据，再在主文件中读取，为王平、李斌，十分快捷。倒排表各个指针列宽度不等，结构较复杂，维护较麻烦，但比多重链表文件要简单。 2.3 B+树文件随着文件增大，索引文件结构也将逐渐复杂，使查找性能、维护性能下降，数据顺序扫描性能会下降，我们希望索引在数据录入、删除时保持其有效性，在这一方面B+树索引文件具有良好性能。B+树索引文件采用多枝平衡树结构，以块为结点，除根外，每个结点中数据量要求装满一半以上，若一块最多能包含N条数据，就要求任何时候除根结点外每块数据量至少为N/2条数据，根结点每块数据量可以为1到N条数据（不受“至少为N/2条数据”的限制）。在根和枝中存放的是路标值和指针，指针数总比路标值数多一，每个路标值左指针所指块的最大路标值或最大关键字值都小于等于该路标值，而右指针所指块的最大路标值或最大关键字值都大于该路标值。在根和枝中一块最多可以存放N个路标值。在叶中存放的是关键字值，若一块最多可存放M个关键字值（允许MN），则要求最少存入M/2 条关键字值，每个结点中数据按关键字值大小顺序排列，所有叶结点按顺序由指针链接。例如表1.4中关于老师的索引，其结构如图2.6所示（本例为使图形简单，M取2，N取4），底层（页结点）每个节点最多存二条数据。如果查找关键字x4，我们从根查起，因“x4”“x3”再从x3的右枝往下查；最后在叶结点中查到x4。访盘次数共三次。由上可知，查到一条记录访盘次数等于树的深度。由于采用多枝平衡树，对于一个记录总数为k的数据库，如根和枝上容纳路标值总数为N，它和查到一条记录访盘次数L之间满足：1+logN+1(k+1)L2+logN+1(K+1)/2)由于N较大，因而即使记录数K很大，L也很小。例如K=1M，N=100，则1+logN+1(k+1)=4，2+logN+1(K+1)/2)=4.85，可见访盘次数为4至5次,而采用一般索引方法,平均访盘次数可能高达5000次。此外，如我们欲继续查出所有教研室号为02的记录的位置，只需在叶结点链中查找，在B+树中查找也十分快捷。现在许多数据系统由于采用了这类索引方式管理数据，使其查询速度大大提高。2.4 小 结本章重点讲述了数据库文件存储的各种实现技术，包括顺序文件组织方式、链表结构文件组织方式、索引技术、随机存取的文件组织方式以及B+树索引技术。顺序文件组织方式中记录是物理相邻地依次排列。链表结构组织的文件的基本特点是数据在物理上可以任意存放，利用