数据库原理及应用 《数据库原理及应用》课程组 Jmun_jsjxy@163.com 2007.3 荆楚理工学院

第二章 数据的存储技术 2007.3 荆楚理工学院

【本章要点】 第二章 文件组织是数据库的物理基础，它直接影响数据库的性能。本章主要介绍文件组织、索引技术和B+树文件的基本概念。 2007.3 荆楚理工学院

物理文件：是数据库真实存在的基本单位，对数据库的任何访问（增、删、改、查询），最终都将转换为在物理文件上的响应操作。 2.1 文件组织 文件组织：就是按一定的逻辑结构（如顺序结构、随机结构、链表结构、树结构等）把有关的数据记录组织成为逻辑文件，并用体现这种逻辑结构的物理存贮形式把文件中的数据存放到外存上，－－构成物理文件。 物理文件：是数据库真实存在的基本单位，对数据库的任何访问（增、删、改、查询），最终都将转换为在物理文件上的响应操作。 文件组织是数据库的物理基础，它直接影响数据库的性能。 2007.3 荆楚理工学院

2.1.1 顺序文件组织 在顺序文件中，记录被物理邻接地按地址次序排列，排列顺序为按某一码值的升序或降序，也可为按记录录入的先后次序。 2.1 文件组织 2.1.1 顺序文件组织 在顺序文件中，记录被物理邻接地按地址次序排列，排列顺序为按某一码值的升序或降序，也可为按记录录入的先后次序。 1、按码值排序时，其顺序还与存储方式有关。有按二进制数和ASCII码存储两种形式。前者，根据码值数值大小排序；后者，视为字符串。 其优点是查找方法较为灵活，可利用二分法，插值算法和分区算法等方法加快查找速度。 缺点是在进行数据录入、修改、删除时要花费大量时间用于排序，非常耗时，且要求空间连续成片，不便于维护。 2007.3 荆楚理工学院

2.1 文件组织 2.1.1 顺序文件组织 2、按记录录入的先后次序 一般维护工作量大或检索内容较多的系统，都采取按记录录入先后次序安排记录的方式顺序存放数据。再利用索引文件加快查找速度。如VFP数据表文件就采用顺序文件组织方式，同时提供多种索引方式以利于数据查找和使用。 2007.3 荆楚理工学院

2.1.2 链表结构文件组织 其基本特点是数据在物理上可以任意存放，利用指针表现数据间的逻辑关系。 2.1 文件组织 2.1.2 链表结构文件组织 其基本特点是数据在物理上可以任意存放，利用指针表现数据间的逻辑关系。 指针又分为单链表、环链表、双向链表等不同形式。 这种结构的优点是记录的增删容易实现，缺点在于只能按指针顺序检索，速度较慢。 2007.3 荆楚理工学院

2.1 文件组织 2.1.2 链表结构文件组织 在关系数据库VFP中的备注字段（M）和通用字段(G)两种数据类型，其数据单元中也只存放指针，指向相应在FPT和TBK文件中的内容。以节省存储空间，提高效率。 在DBTG网状数据库中，“系”结构采用了双向链表和环链表结构两种指针结构。此外还采用了指针阵列，指向系主记录的物主指针等结构。 2007.3 荆楚理工学院

2.1 文件组织 2.1.3 随机存取文件组织（Hash文件组织） 随机文件的基本思想就是在记录的关键字值与其地址之间建立某种联系，文件的记录则按这种关系进行存取。 随机文件可分为三种结构方式： 1、直接地址结构：当知道某个记录的地址时，可直接使用这个地址进行存取。该结构存取效率高，但用户必须知道每个记录的具体地址。 2、索引结构：就是通过一个二元表（索引表）来建立记录的关键字与其地址之间的联系。 2007.3 荆楚理工学院

2.1 文件组织 2.1.3 随机存取文件组织（Hash文件组织） 3、散列（Hash）文件：是一种著名的随机结构文件。它是利用散列（Hash）函数 y=f(x) 把码值映射成记录存储地址，直接存取。其中 x 为码值，y 为地址。 为减小冲突，常利用“桶”作为编址的基本单位。把若干存储单元作为一组并以同样的地址加以标识。一个桶可由若干块组成，存放若干个记录，一个存储区可由若干桶组成。如图所示。 2007.3 荆楚理工学院

由于桶地址的总数目一般比可能的关键字值的总数目少得多，因而同一桶地址记录可能大于桶的容量，称之为“冲突”。 2.1 文件组织 2.1.3 随机存取文件组织（Hash文件组织） 由于桶地址的总数目一般比可能的关键字值的总数目少得多，因而同一桶地址记录可能大于桶的容量，称之为“冲突”。 必须采用恰当的Hash算法处理其存储位置，并设计发生冲突时的算法，以求尽可能减少冲突。 2007.3 荆楚理工学院

2.2.1 索引文件 数据库采用索引文件组织的目的：提高检索效率。 2.2 索引文件 2.2.1 索引文件 数据库采用索引文件组织的目的：提高检索效率。 索引项由查找关键字值和指针组成，通过指针就可找到含有此关键字值的记录，其结构为：(查找关键字值，指针)。 多个索引项构成按查找关键字排序的文件称索引文件。 索引通常置于磁盘或内存，但内存中一般只存放最高级索引。 2007.3 荆楚理工学院

2.2 索引文件 2.2.1 索引文件 如果内外存交换数据的单位为块，又一个索引文件的大小大于块的大小，不能一次将索引文件调入内存，可再建立高一层索引：将原索引文件分段，取每段最末一个索引项的关键字值及其在索引文件中的地址指针构成该级索引项，这样构成的索引文件称稀疏索引。 稀疏索引文件的查找效率很高，但这种索引对记录的插入或删除很不方便。 2007.3 荆楚理工学院

对每条记录生成一个索引项的索引文件称稠密索引。 2.2 索引文件 2.2.1 索引文件 对每条记录生成一个索引项的索引文件称稠密索引。 稠密索引的优点是数据记录可任意存放，这样除查找方便外，增、删数据记录也比稀疏索引方便。缺点是其索引项多，耗费空间且查找比稀疏索引文件多一次操作。 2007.3 荆楚理工学院

2.2 索引文件 2.2.2 非关键字索引文件 对于查找的内容会有许多相同的取值，或检索目标涉及多个属性的情况，采用前述关键字索引文件查询的速度仍较慢，为此需设计如下几种索引文件结构。 1、索引链接文件与多重链表文件索引 索引链接文件由范围索引构成的索引表及若干个链接文件构成。 范围索引的索引项由范围关键字和一个指针组成，每个索引项的指针指向其范围内第一条记录的地址，该范围内其他记录由指针顺序相连。如图所示，范围关键字是职称。 2007.3 荆楚理工学院

2.2.2 非关键字索引文件 对于涉及二个以上检索条件的问题，可建立多个索引，多个链表文件，称为索引多链表文件。以提高对非关键字查找的效率。 2.2 索引文件 2.2.2 非关键字索引文件 对于涉及二个以上检索条件的问题，可建立多个索引，多个链表文件，称为索引多链表文件。以提高对非关键字查找的效率。 例如欲从主文件表中查找所有男教授数据。可对职称建立一个索引链表，对性别建立一个链表，先查出所有教授姓名，再在性别链中查出这些教授有哪些在男性链表中，取出这些教授的数据。参见例表 2007.3 荆楚理工学院

2.2.2 非关键字索引文件 2、倒排表 如要查某个范围内数据，采用倒排表算法比较简单。 2.2 索引文件 2.2.2 非关键字索引文件 2、倒排表 如要查某个范围内数据，采用倒排表算法比较简单。 倒排表索引项由查找关键字及相关记录地址(指针)构成 。 一个倒排表的例子。 倒排表文件结构能很好地支持多字段的组合条件查询，此时，对每一条件在倒排表中查出满足条件的记录的地址集合，之后进行求交集的运算，找到满足组合条件的记录，之后就可从主文件中查出相应数据。 2007.3 荆楚理工学院

在根和枝中存放的是关键字值和指针，指针数总比关键字数多“1”。 2.3 B+树文件组织 B+树索引文件采用多枝平衡树结构，以块为结点，除根外，每个结点中数据量要求装满一半以上，即非根结点一块若能包含N条数据，就要求任何时候数据量至少为N/2条数据。 在根和枝中存放的是关键字值和指针，指针数总比关键字数多“1”。 2007.3 荆楚理工学院

例如教材表1.4中老师索引，其结构如图所示，这里M取4，N取2。 2.3 B+树文件组织 若一块最多可存放M个关键字值 及M+1个指针（M≠N，M>>N），则要求最少存入M/2 条关键字值和1+M/2条指针，每个关键字值左指针所指块的最大关键字值都小于等于该关键字值，而右指针所指块的最大关键字值都大于该关键字值，每个结点中数据按关键字值大小顺序排列，所有叶结点按顺序由指针链接。 例如教材表1.4中老师索引，其结构如图所示，这里M取4，N取2。 2007.3 荆楚理工学院

1+logN+1(k+1)≤L≤2+logN+1((K+1)/2) 2.3 B+树文件组织 查找一条记录访盘次数等于树的深度。 对于一个记录总数为K的数据库，如根和枝上容纳关键字总数为N，则查到一条记录访盘次数L满足关系： 1+logN+1(k+1)≤L≤2+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次。 故许多数据库管理系统采用这类索引方式管理数据，使其查询速度大大提高。 2007.3 荆楚理工学院

例题解析 1.常用的数据库文件存储结构方式有哪些?举出每种方式的一个实例。 顺序文件组织方式（如VFP数据表文件）、链表结构文件组织方式（如IMS数据库，VFP中的备注字段和通用字段）、索引技术（如VFP中的索引文件）、随机存取的文件组织方式（一些网状数据库中的数据库码）以及B+树索引技术（现在大多数数据系统都采用这种技术）。 2007.3 荆楚理工学院

例题解析 2.索引技术的主要特点是什么? 索引文件规模小，容易维护，查找速度快。 3.简述Hash算法的基本思想。 要点：Hash算法是利用散列（Hash）函数 y=f(x) 来建立记录的关键字与其地址之间的联系。即关键字作为自变量x （码值），经过某种变换转换成相应的存储地址y ，直接存取。 Hash算法常利用“桶”作为编址的基本单位。把若干存储单元作为一组并以同样的地址加以标识。 2007.3 荆楚理工学院

例题解析 4.什么是B+树索引? B+树索引文件采用多枝平衡树结构，以块为结点，除根外每个结点中数据量要求装满一半以上，即非根结点一块若能包含N条数据，就要求每块任何时候数据量至少为N／2条数据。在根和枝中存放的是关键字值和指针，指针数总比关键字数多一，每个关键字值左指针所指块的最大关键字值都小于等于该关键字值，而右指针所指块的最大关键字值都大于该关键字值，每个结点中数据按关键字值大小顺序排列，所有叶结点按顺序由指针链接。 2007.3 荆楚理工学院

5.在VFP中备注字段类型的数据和通用类型的数据有什么特点，在存储这些数据时采用了什么方式进行存放? 2.3 B+树文件组织 5.在VFP中备注字段类型的数据和通用类型的数据有什么特点，在存储这些数据时采用了什么方式进行存放? 在VFP中采用FPT、TBK文件分别存放备份字段数据、通用字段数据，在DBF文件中，相应的备注（M）型和通用（G）型数据单元中只存放指针，指向相应在FPT和TBK文件中的内容。 2007.3 荆楚理工学院

例题解析 例题解析 6.在VFP中采用了哪些索引类型，各有何特点? VFP中索引有四种类型： 主索引，每个表只能建一个主索引。其索引关键字中不允许有重复值。 候选索引，每个表可建多个候选索引，其索引关键字中不允许有重复值。 惟一索引，允许出现重复值，但利用它只保存重复第一个值的索引项。 普通索引，允许出现重复值，可决定记录处理顺序。 2007.3 荆楚理工学院