第7章数据库存储结构

1、第7章 数据库存储结构目 录B+树索引树索引7.4文件组织文件组织7.1记录组织记录组织7.2顺序索引顺序索引7.37.57.6物理数据库设计物理数据库设计散列散列存储介质的分类 几种有代表性的存储介质：高速缓冲存储器(cache)、主存储器(main memory)、快闪存储器(flash memory)、磁盘存储器(magnetic-disk storage)、光存储器(optical storage)和磁带存储器(tape storage)等。 计算机的三级存储体系 ：根据不同存储介质的速度和成本，可以把它们按层次结构组织起来，层次越高，每单位存储容量价格越贵，但速度越快。如图7-1所示

2、。 存储易失性问题 ：易失性存储在设备断电后将丢失所有内容。一级存储为易失性存储，而二、三级存储系统都是非易失性存储。 磁盘的主要性能指标访问时间(access time)是从发出读写请求到数据开始传输之间的时间。 为了访问(即读或写)磁盘上指定扇区的数据，磁盘臂首先需要移动以定位到正确的磁道，所需时间称为寻道时间(seek time)； 然后等待磁盘旋转直到指定的扇区出现在它下方，所需的时间称为旋转等待时间(rotational latency time) 。 访问时间=寻道时间+旋转等待时间。数据传输率(data-tranfer rate)是从磁盘获得数据或者向磁盘存储数据的速率。 磁盘的

3、平均故障时间(mean time to failure, MTTF)是指磁盘无故障连续运行时间的平均值。磁盘块(block)是一个逻辑单元，它是包含固定数目的连续扇区。数据在磁盘和主存储器之间以块为单位传输。 存储访问 缓冲区(buffers)是主存储器中用于存储磁盘块的副本的区域。缓冲区中的每个块总有一个副本存放在磁盘上，但是在磁盘上的副本可能比在缓冲区中的副本旧。 负责缓冲区空间分配和管理的子系统称为缓冲区管理器。 数据库系统通过缓冲区实现对磁盘上数据的存储访问。 在数据库管理系统中，数据的存取过程如图7-2所示。 具体步骤如下：(1) 应用程序通过DML向DBMS发出存取请求，如Sele

4、ct语句；(2) 对命令进行语法检查，正确后检查语义和用户权限（通过数据字典DD），并决定是否接收；(3) 执行查询优化，将命令转换成一串单记录的存取操作序列；(4) 执行存取操作序列反复执行以下各步，直到结束：(5) 在缓冲区中找记录，若找到转在缓冲区中找记录，若找到转(10)，否则转，否则转(6)；(6) 查看存储模式，决定从哪个文件、用什么方式读取物理记录；查看存储模式，决定从哪个文件、用什么方式读取物理记录；(7) 根据根据(6)的结果向操作系统的结果向操作系统(OS)发出读取记录的命令；发出读取记录的命令；(8) OS执行该命令，并读取记录数据；执行该命令，并读取记录数据；(9) 在

5、在OS控制下，将读出的记录送入控制下，将读出的记录送入系统缓冲区系统缓冲区；(10) RDBMS根据查询命令和根据查询命令和DD的内容导出用户所要读取的记录格式；的内容导出用户所要读取的记录格式；(11) RDBMS将数据从将数据从系统缓冲区系统缓冲区中送入中送入用户工作区用户工作区；(12) RDBMS将执行状态信息将执行状态信息(成功或不成功等成功或不成功等)返回给应用程序；返回给应用程序；(13) 应用程序对工作区中读出的数据进行相应处理。应用程序对工作区中读出的数据进行相应处理。定长记录与变长记录 文件在逻辑上可看作记录的序列，这些记录被映射到磁盘的物理块上。 用文件表示逻辑数据模型的

6、不同方式：定长记录和变长记录 所谓定长记录指文件中所有记录均具有同样的字节长度，如图7-3所示： 这种简单的方法明显地有两个问题： 删除一条记录比较困难。要么填充被删空间，要么标记被删记录； 除非块的大小恰好是记录大小的倍数，否则有的记录会跨块存储。对于跨块存储的记录的访问需要涉及两次磁盘I/O操作。 一般对被删除结点做标记，且使用空闲记录链表来管理记录的插入和删除，如图7-4所示：n 在文件开始处，分配一定数量的字节作为在文件开始处，分配一定数量的字节作为文件头文件头(file header)，文件头中存储有关文件的各种信息。到目前为止，需要在文件文件头中存储有关文件的各种信息。到目前为止，

7、需要在文件头中存储的信息只有一个，即第一条被删除记录头中存储的信息只有一个，即第一条被删除记录(即第一条可用即第一条可用记录记录)的地址。的地址。 变长记录指文件中的记录具有不同的存储字节数。 在数据库系统中，以下几种情况会导致使用变长记录： 多种记录类型(即多个关系表)在一个文件中存储； 允许记录类型中包含一个或多个变长字段； 允许记录类型中包含重复字段，如数组等。 有多种变长记录的存储管理技术，这里仅介绍分槽页结构(slotted-page structure)。分槽页结构一般用于在块中组织记录，如图7-5所示。 每个块的开始处有一个块头，块头中包含的信息有： 块头中已存储的条目(entr

8、y)个数#E(number of entries)； 块中空闲空间的末尾地址EFS(end of free space)； 条目数组，每个条目中存储了该条目所对应变长记录的大小ES(entry size)和地址EP (entry pointer)。目 录B+树索引树索引7.4文件组织文件组织7.1记录组织记录组织7.2顺序索引顺序索引7.37.57.6物理数据库设计物理数据库设计散列散列文件组织 文件中组织记录的常用方法有：堆文件组织、顺序文件组织、多表聚集文件组织、B+树文件组织和散列（hashing）文件组织等。本节对前3种进行介绍。 堆文件组织 ：一条记录可以放在文件中的任何地方，只要那

9、个地方有空间存放该记录。也就是说，文件中的记录是没有顺序的，是堆积起来的。通常每个关系使用一个单独的文件。 顺序文件组织：顺序文件是为了高效地按某个搜索码的顺序排序处理记录而设计的。为了快速地按搜索码的顺序获取记录，通常通过指针把记录逻辑上有序地链接起来。每个记录的指针指向搜索码顺序的下一条记录。同时，为了减少顺序文件处理中磁盘块的访问数量，在物理上按搜索码顺序或者尽可能地接近搜索码顺序存储记录。如图7-6所示： 顺序文件中插入操作的处理： 在文件中定位按搜索码顺序处于插入记录之前的那条记录（记为记录A）。 如果记录A所在块中有空记录(可能删除后留下来的空间)，就在这里插入新的记录；否则将新记

10、录插入在一个溢出块中。 不管哪种情况，都要调整指针，使其能按搜索码顺序把记录链接起来。 插入情况如图7-7所示：多表聚集文件组织 问题的提出：两个关系中作连接运算时，最坏的情况下，每个相匹配的记录都处在不同的磁盘块中，这将导致为获取所需的每一条记录都要读取一个磁盘块。 问题的解决 ：将两个关系的元组混合在一起聚集存储，从而支持高效的连接运算。如图7-8所示的两个关系，为了支持高效连接运算，可以采用图7-9所示的多表聚集文件结构。n 多表聚集文件组织多表聚集文件组织(Multitable Clustering File Organization)是是一种在每一个块中存储两个或多个关系的相关记录的

11、文件结一种在每一个块中存储两个或多个关系的相关记录的文件结构。构。n 对于图对于图7-9所示的所示的多表聚集文件结构多表聚集文件结构，可以加速，可以加速特定连接特定连接的处的处理，但是它将导致理，但是它将导致其它类型查询的处理变慢其它类型查询的处理变慢。在图。在图7-10中，中，通过指针将一个关系中的所有记录链接起来以方便查找。通过指针将一个关系中的所有记录链接起来以方便查找。 目 录B+树索引树索引7.4文件组织文件组织7.1记录组织记录组织7.2顺序索引顺序索引7.37.57.6物理数据库设计物理数据库设计散列散列 两种基本的索引类型： 顺序索引(ordered index)：基于搜索码的

12、值的顺序排列，包括索引顺序文件和B+树索引文件等。 顺序索引主要用于支持快速地对文件中的记录进行顺序或随机地访问。顺序索引的结构是按顺序存储搜索码的值，并将搜索码的值与包含该搜索码值的记录关联起来 。索引基本概念 l 散列索引散列索引(hash index)：通过搜索码值的散列函数：通过搜索码值的散列函数(也称哈希函也称哈希函数数)的值将所有记录平均、随机地分布到若干个散列桶中。的值将所有记录平均、随机地分布到若干个散列桶中。n 搜索码搜索码(search key)：用于在文件中查找记录的属性或：用于在文件中查找记录的属性或属性集。经常需要在一个文件上建立多个索引，此时该属性集。经常需要在一个

13、文件上建立多个索引，此时该文件就有多个搜索码。文件就有多个搜索码。 建立了索引的文件称为索引文件。索引文件中的记录自身可以按照某种排序顺序存储。一个索引文件可以有多个索引，分别对应于不同的搜索码。 如果索引文件中的记录按照某个搜索码值指定的顺序物理存储，那么该搜索码对应的索引就称为主索引(primary index)，也叫聚集索引(clustering index)。 与此相反，搜索码值顺序与索引文件中记录的物理顺序不同的那些索引称为辅助索引(secondary index)或非聚集索引(nonclustering index)。 索引基本概念 对索引技术的评价需要全面考虑以下因素： 访问类型

14、：索引能有效支持的数据访问类型。例如，根据指定的属性值进行查询，根据给定的属性值的范围进行查询。 访问时间：通过索引找到一条特定记录或记录集所需要的时间。 插入时间：在文件中插入一条新记录所需要的时间，包括找到插入新记录的正确位置和插入该记录所需要的时间以及更新索引结构所需要的时间。 删除时间：在文件中删除一条记录所需要的时间，包括找到待删除记录的正确位置和删除该记录所需要的时间以及更新索引结构所需要的时间。 空间开销：索引结构所需要的额外存储空间。一般来说，索引是用空间代价来换取系统性能的提高，这就要进行空间与时间的折衷。索引顺序文件 建立了主索引的索引文件称为索引顺序文件(index-se

15、quential file)。也就是说，索引顺序文件是按某个搜索码值物理有序存储。 对于索引顺序文件，顺序索引有两类：稠密索引和稀疏索引。 稠密索引。对应索引文件中搜索码的每一个值在索引中都有一个索引记录(或称为索引项)。每一个索引项包含搜索码值和指向具有该搜索码值的第一个数据记录的指针，如图7-11所示，其中studentName是搜索码。 稀疏索引。稀疏索引只为索引文件中搜索码的某些值建立索引记录(或称为索引项)。每一个索引项包含搜索码值和指向具有该搜索码值的第一个数据记录的指针，如图7-12所示。多级索引 即使采用稀疏索引，对于一个大型数据库而言，索引本身也可能变得很大。 如果索引过大，

16、主存中不可能读入所有的索引块，也就是大部分索引块只能存储在磁盘上，这样在查询处理过程中，搜索索引就必须读大量的磁盘块。 通过多级索引技术能够较好地解决上述问题。所谓多级索引就是在索引之上再建立索引。 像对待其他顺序文件那样对待索引，在聚集索引上再构造一个稀疏索引，如图7-13所示。 事实上索引就是一个顺序文件，索引记录是按搜索码值有序存放的。多级索引 索引的更新 删除记录 ：为了删除数据文件中的一条记录，系统首先要查找定位该记录，记待删除记录的搜索码值为KD。 接下来的操作要分稠密索引和稀疏索引来讨论。 对于稠密索引，如图7-11所示， 索引更新的规则如下： 如果被删除的记录是唯一具有KD值的

17、记录，则从索引中删除相应的索引项(索引记录)，如删除“刘方晨”的记录。 否则（即搜索码值为KD的记录有多条），采取如下操作： 如果索引项中存储的指针指向待删除的记录，则更新该指针，使其指向文件中的下一条数据记录， 如删除学号为0701001的“李小勇”的记录； 否则索引不必更新，如删除学号为0803025的“李小勇”的记录。 对于稀疏索引，如图7-12所示，索引更新的规则如下：1、如果索引中不包含搜索码值为、如果索引中不包含搜索码值为KD的索引项，则索引不必更的索引项，则索引不必更新，新，如删除如删除“李小勇李小勇”、“王红敏王红敏”的记录的记录。 对于稀疏索引，如图7-12所示，索引更新的规

18、则如下：2、否则（即索引中包含搜索码值为、否则（即索引中包含搜索码值为KD的索引项）的索引项）2.1 如果被删除的记录在数据文件中是唯一具有如果被删除的记录在数据文件中是唯一具有KD值的记值的记录，采取如下操作：录，采取如下操作： 用数据文件中下一个搜索码值的记录更新该索引项用数据文件中下一个搜索码值的记录更新该索引项(包括搜包括搜索码值和指针都要更新索码值和指针都要更新)，如删除如删除“李宏冰李宏冰”的记录的记录； 如果数据文件中下一个搜索码值的记录在索引中已经有一个如果数据文件中下一个搜索码值的记录在索引中已经有一个索引项，则删除该索引项，索引项，则删除该索引项，如删除如删除“刘方晨刘方晨

19、”的记录的记录。 对于稀疏索引，如图7-12所示，索引更新的规则如下：2.2 否则否则(即索引中包含搜索码值为即索引中包含搜索码值为KD的索引项，且数据文的索引项，且数据文件中包含多条搜索码值为件中包含多条搜索码值为KD的记录的记录)，采取如下操作：，采取如下操作：如果索引项中存储的指针指向待删除的记录，则更如果索引项中存储的指针指向待删除的记录，则更新该指针，使其指向文件中的下一条数据记录，新该指针，使其指向文件中的下一条数据记录，如如删除学号为删除学号为0701008的的“王王 红红”的记录的记录；否则索引不必更新，否则索引不必更新，如删除学号为如删除学号为0703045的的“王王 红红”

20、的记录的记录。 插入记录 对于稠密索引，如图7-11所示。 如果待插入记录的搜索码值不在索引中，则把该搜索码值插入到索引中，如插入一条姓名为“彭国强”的记录； 否则索引不必更新，如插入一条学号为0701004、姓名为“王 红”的记录。 对于稀疏索引，假设索引为每个块保存一个索引项。 如果系统产生一个新块 (不是指溢出块)，将新块中第一条记录的搜索码值(即新块中最小的搜索码值)插入到索引中建立一个索引项，新建的索引项指向新块。 如果没有新块产生，且插入记录在该块中具有最小的且唯一的搜索码值，则更新索引中指向该块的索引项的搜索码值；否则索引不必更新。 多级索引的插入和删除算法是对上述算法的一个简单

21、扩充。 在插入或删除时，对底层索引的更新如上所述。 而对于第二层而言，底层索引就是一个包含索引记录的按搜索码值有序的顺序文件。因此，如果底层索引发生改变(插入或删除索引记录)，第二层索引就可以像上面描述的那样进行更新。 如果还有更高层的索引，类似处理。辅助索引 在数据文件中，记录按主索引而不是辅助索引的搜索码值顺序物理存储，因此具有同一个搜索码值的记录可能分布在文件的各个地方。 所以，辅助索引必须是稠密索引，即对于每个搜索码值都必须有一个索引项，而且该索引项要存放指向数据文件中具有该搜索码值的所有记录的指针。 可以通过指针桶的方式实现，即将数据文件中具有该搜索码值的所有记录的指针存放在一个指针

22、桶中，索引项中的指针域再存放指向指针桶的指针(可以理解为指向指针数组的指针)。如图7-14所示。 索引顺序文件组织的最大不足在于： 随着文件的增大，索引查找的性能和数据顺序扫描的性能都会下降。 虽然这种性能下降可以通过对文件进行重组来弥补，但频繁地进行重组也是我们所不希望的。目 录B+树索引树索引7.4文件组织文件组织7.1记录组织记录组织7.2顺序索引顺序索引7.37.57.6物理数据库设计物理数据库设计散列散列B+树索引的结构 B+树索引的结构满足： B+树索引是一个多级索引，但其结构不同于多级顺序索引。 B+树索引采用平衡树结构，即每个叶结点到根的路径长度相同。江宏江宏李勇李勇彭好彭好王

23、红王红刘强刘强黄红黄红黄勇黄勇江宏江宏李冰李冰李立李立李勇李勇刘欢刘欢指 向 文 件 记指 向 文 件 记录录刘强刘强 孟晨孟晨 聂东聂东彭好彭好邱南邱南王红王红 张可张可赵雪赵雪指向文件记录指向文件记录B+树索引的结构 B+树索引的结构满足： B+树索引是一个多级索引，但其结构不同于多级顺序索引。 B+树索引采用平衡树结构，即每个叶结点到根的路径长度相同。 B+树索引中的所有结点的结构都相同，它最多包含n-1个搜索码值K1, K2, , Kn-1，以及n个指针P1, P2, , Pn，每个结点中的搜索码值升序存放，即如果ij，那么KiKj。典型的B+树索引中的结点结构如图7-15所示。 每个

24、非叶结点有 n/2 到n个孩子结点，n对特定的树是固定的。B+树索引的结构树索引的结构 叶结点的结构：对i=1, 2, , n-1，指针Pi指向具有搜索码值Ki的一条文件记录或指向一个指针桶，且指针桶中的每个指针指向具有搜索码值Ki的一条文件记录。桶结构只在搜索码不是候选码且文件记录不按搜索码顺序存放时才使用。指针Pn有特殊的作用，稍后再讨论。江宏江宏李勇李勇彭好彭好王红王红刘强刘强黄红黄红黄勇黄勇江宏江宏李冰李冰李立李立李勇李勇刘欢刘欢指 向 文 件 记指 向 文 件 记录录刘强刘强 孟晨孟晨 聂东聂东彭好彭好邱南邱南王红王红 张可张可赵雪赵雪指向文件记录指向文件记录 每个叶结点最多可存放n

25、-1个搜索码值，最少也要存放 (n-1)/2 个搜索码值。各个叶结点中的搜索码值不重复且不相交，并要使B+树索引成为稠密索引，即数据文件中的所有互不相同的搜索码值必须在某个叶结点出现且只出现一次。 每个叶结点中的搜索码值升序排列，所以可以利用各个叶结点的指针Pn将所有叶结点按搜索码值的排序顺序链接在一起。这种叶结点的链接排序能够高效地实现对数据文件的顺序处理，而B+树索引中的其他结构能够高效地实现对数据文件的随机处理。如图7-16所示。 B+树索引的结构 非叶结点的结构： B+树索引中的非叶结点形成叶结点上的一个多级(稀疏)索引。 非叶结点的结构与叶结点相同，只不过非叶结点中的所有指针都是指向

26、B+树中下一层结点的指针。 每个非叶结点最多可存放n个指针(对应于存放n-1个搜索码)，最少也要存放 n/2 个指针(对应于存放 (n-1)/2 个搜索码)。 一个结点中存放的指针数称为该结点的扇出。B+树索引的结构 假设一个非叶结点中存放了m个指针， n/2 mn。 若mnr/fr，否则肯定会发生桶溢出。其中nr表示将要存储的记录总数，fr表示一个桶中能存放的记录数目。当然，这是以在选择散列函数时记录总数已知为前提的。 偏斜。某些桶分配到的记录比其他桶多，所以，即使其他桶仍有空间，有些桶仍可能溢出，称为桶偏斜。 偏斜发生的原因有两个： 多个记录可能具有相同的搜索码值； 所选择的散列函数可能会

27、造成搜索码值的分布不均匀。桶溢出的处理 桶溢出的处理方法：主要有闭散列和开散列二种方法。 闭散列： 如果一条记录必须插入桶b中，而桶b已满，系统会为桶b提供一个溢出桶，并将此记录插入到这个溢出桶中。 如果溢出桶也满了，系统会再提供一个溢出桶，如此继续下去。 一个给定桶的所有溢出桶用一个链接列表链接在一起，如图所示. 使用这种链接列表的溢出处理称为溢出链。溢出链的散列结构称为闭散列。 桶溢出的处理 开散列： 它的桶的数量是固定的，没有溢出链； 当一个桶满了以后，系统将记录插入到初始桶集合B的其他桶中去。 选择其他桶的策略有： 使用下一个(按轮转顺序)未满的桶，该策略称为线性探查法； 用进一步计算

28、散列函数的方法（再散列法）。 散列索引 散列索引(hash index)将搜索码值及其相应的文件记录指针组织成散列文件结构。 散列索引的构建方法： 将散列函数作用于一条文件记录的搜索码值，以确定索引项的散列桶； 将由该搜索码值以及相应文件记录指针组成的索引项存入散列桶(或溢出桶)中。 图7-22所示的是Student文件的一个辅助散列索引，其搜索码是studentNo，散列函数是计算studentNo值的各位数字之和后按5取模。由于studentNo是主码，所以每个搜索码值只对应一个记录指针。一般情况下，每个搜索码值可能对应多个指针。散列索引散列索引 散列索引只能是一种辅助索引结构。 散列索引

29、从来不需要作为主索引(聚集索引)来使用，因为一个文件如果自身是按散列组织的，就不必再在其上另外建立一个独立的散列索引了。 不过，既然散列文件组织能像索引那样提供对记录的直接访问，不妨就认为以散列形式组织的文件上也有一个聚集散列索引了。 动态散列 前面介绍的散列技术称为静态散列，它要求在选择散列函数时就知道记录的总数，即桶的数量必须事先确定。 然而，大多数数据库都会随时间而变大。对于规模变化的数据库使用静态散列，有3种选择： 根据当前文件大小选择散列函数。这种选择会使性能随数据库增大而下降。 根据预计的将来某个时刻文件的大小选择散列函数。尽管这样可以一定程度上避免性能下降，但初始时会造成相当大的

30、空间浪费。 随着文件增大，周期性地对散列结构进行重组。重组是一个复杂、耗时的操作，而且重组期间必须禁止对文件的访问。 动态散列技术允许散列函数动态改变，以适应数据库增大或缩小的需要。 限于篇幅，这里不对动态散列技术进行讨论，有兴趣的读者请参考相关资料。散列与顺序索引的比较 散列其实就是一种不通过值的比较，而通过值的含义来确定存储位置的方法，它是为有效地实现等值查询而设计的。 不幸的是，基于散列技术不支持范围检索。 而基于B+树的索引技术能有效地支持范围检索，并且它的等值检索效果也很好。 但是，散列技术在等值连接等操作中是很有用的，尤其是在索引嵌套循环连接方法中，基于散列的索引和基于B+树的索引

31、在代价上的差别会很大。散列与顺序索引的选择 在实际的数据库设计中，到底是用索引还是散列要充分考虑以下几个问题： 索引或散列的周期性重组的代价如何？ 在文件中插入和删除记录的频率如何？ 是否愿意以增加最坏情况下的访问时间为代价优化平均访问时间？ 用户可能提出哪些类型的查询？目 录B+树索引树索引7.4文件组织文件组织7.1记录组织记录组织7.2顺序索引顺序索引7.37.57.6物理数据库设计物理数据库设计散列散列物理数据库设计 数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于给定的计算机系统。 为一个给定的逻辑数据模型选取一个最适合应用环境的物理结构的过程，就是数据库的物理设

32、计。 目标： 提高数据库性能，以满足应用的性能需求； 有效利用存储空间； 在性能和代价之间做出最优平衡。 内容： 确定数据库的存储结构； 为数据选择合适的存取路径，即索引的设计； 对物理结构进行评价，重点是评价时间和空间效率。 数据库的物理组织 数据库的基础是基于操作系统的文件系统，对数据库的操作都要转化为对文件的操作，如何设计文件结构以及有效利用操作系统提供的文件存取方法是DBMS要考虑的事情。 因此，选定DBMS后，数据库物理组织的大概框架也就基本确定了，如一个数据库需要多少个文件，每个文件的作用是什么，等等。 关系数据库中要存储的数据主要包括：关系表、数据字典、索引、日志和备份等。DBMS对不同数据的物理组织方式通常是不一样的。确定数据库存储结构 确定数据存放位置 ：为了提高系统性能，数据应该根据应用情况将易变部分和稳定部分、经常存取部分和存取频率较低部分分开来存放。 确定数据库存储结构 ：确定数据库存储结构时要综合考虑存取时间、存储空间利用率和维护代价三个方面的因素。这三个方面常常是相互矛