第6章数据物理组织与索引重点课件.ppt

《第6章数据物理组织与索引重点课件.ppt》由会员分享，可在线阅读，更多相关《第6章数据物理组织与索引重点课件.ppt（70页珍藏版）》请在三一办公上搜索。

1、数据库系统原理 SHUJUKU XITONG YUANLI,中国计量学院信息学院,SHUJUKU XITONG YUANLI,China Jiliang University2011,(第二版),第六章 数据物理组织与索引,2022/12/20,2,主要内容,6.1 数据库存储设备 6.2 文件 6.3 索引技术,2022/12/20,3,6.1数据库存储设备 计算机中存储介质主要包括两类,一级存储器和二级存储器（外存）。 根据访问数据的速度、成本和可靠性,存储介质可分成以下六类:,2022/12/20,4,2022/12/20,5,1高速缓冲存储器（Cache） 简称为“高速缓存”，也就是一

2、般说的Cache。Cache访问速度快，但贵，容量小。 2. 主存储器（Main Memory）主存储器简称为主存,或内存 。主存中的数据在掉电或系统崩溃时,会全部丢失。,3. 磁盘存储器（Magnetic-Disk Storage）磁盘是目前最常用的外部存储器,由磁性材料制成,数据存储在磁盘表面。磁盘是一种大容量的可直接存取的外部存储设备。在掉电或系统崩溃后,仍能保持数据不丢失。 硬磁盘的特性：,2022/12/20,6,2022/12/20,7,硬磁盘的物理特性硬磁盘的总容量为： 盘面数目每盘面的磁道数每磁道的盘块数每盘块的字节数 磁盘是一种直接存储设备，可随机读写任一盘块。盘块地址的形式

3、是：,图6.1 磁盘块地址形式示意图,磁盘的性能指标 磁盘的性能用磁盘的容量、存取时间、数据传输速度和可靠性四个参数衡量。 内外存间的数据交换 访问的数据不在主存时, 需通过外存加载，所以内外存间要频繁地进行数据交换，每交换一次数据，就称为一次 I/O 操作。,2022/12/20,8,2022/12/20,9,数据块的长度不一定恰好等于记录的整数倍，通常有两种 组块方式 ：不跨块方式： 一个数据块只包含若干完整记录，不足以容纳一个记录的零头空间放弃不用。跨块方式： 允许一个记录跨在不同数据块。这种组块方式虽然可节省空间，但实现比较困难，用得较少。,廉价磁盘冗余阵列 (Redundant Ar

4、ray of Inexpensive（或Indscendent） Disks，简称RAID)它是利用一台磁盘阵列控制器来统一管理和控制一组 ( 几台到几十台 ) 磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统。 实现途径有两个：数据重复存储 和通过并行提高数据传输速度 RAID 按照其基本特性，可分为八级 。,2022/12/20,10,4 磁带磁带是一种顺序存储设备 ,即磁带只能顺序访问，不能随机访问。主要用于数据备份或数据归档。磁带的可靠性较好，主要有两大用途： 作为磁盘的后援存储器，存储数据库文件的副本 用来存储磁盘上存储不了的大型数据库文件,数据库中不常用的数据库文件或历史数据可

5、以存储在磁带上。,2022/12/20,11,5 光存储器光存储器是多媒体信息的主要存储设备，作为分布式软件的主要存储介质，可存储音频、图像一类的数据 。目前流行的光存储器是光盘只读存储器 (CD-ROM) 和数字视频光盘只读存储器（DVD-ROM）。,2022/12/20,12,2022/12/20,13,6 快擦写存储器（Flash Memory）快擦写存储器又称为“电可擦可编程只读存储器”，快闪存在掉电后仍能保持数据不丢失。 快闪存的缺陷是只能支持有限次擦写。而且不能直接重写，必须先擦去整组存储器的内存，然后再写数据进去。,6.2文件,外存中，数据库以文件形式组织，而文件又是由记录组成。

6、文件结构由操作系统的文件系统提供和管理。从文件的组织形式看，分为逻辑结构和物理结构两种。逻辑文件组织有两种方式，一种是把文件看成无结构的流式文件，另一种是把文件看成有结构的纪录式文件。记录式文件分为定长记录和变长记录。,2022/12/20,14,一个文件有逻辑地组织成为记录的一个序列，这些记录映射在磁盘上，通常把文件是为记录的集合。 本节讨论逻辑文件中的记录在物理文件中如何实现。文件记录分为两种：定长记录格式和变长记录格式。,2022/12/20,15,6.2.1 文件组织方式,2022/12/20,16,1 定长记录 就是每条记录都是占用一定长度的字节数。记录的排列也就是一张表格每行有相同

7、的长度，以一行为单元进行增加删除等修改操作。,2022/12/20,17,图6.2 定长记录的文件,2022/12/20,18,图6.3 删除记录2，5，7后的文件结构,如上图每条记录包含姓名、学号、班级三条信息。在每条记录中对应的信息占相同的字节数，所以每条记录的长度一定，构成了一个含有四条记录的定长记录的文件。存在的两个问题：删除：删除后是在其位置补充一个记录还是忽略这个位置；长度：若物理上每个块的大小不等于每个记录的长度倍数，则必然在读这样的记录时要访问两个块。,2022/12/20,19,删除方法 1) 删除记录后，把记录依次上移。 缺点移动次数过多。2) 把最后的记录补到删除的位置。

8、 只需移动一次。以上两个方法都需要移动结点，操作不灵活，处于灵活的考虑必然会想到指针，就是第三种方法。,2022/12/20,20,3) 把删除的结点用指针链接起来首先，文件增设“文件首部”，其中有一个指针指向第一个被删除的记录位置，所有被删除记录的位置都用指针链接起来，构成“空闲记录链表”。缺点：这些被指针链接的记录被称为“被拴记录”，若被删记录被删掉，则指向记录的指针称为“悬挂指针”，所指空间称为“垃圾”，也就是别人无法使用而又被空闲着。,2022/12/20,21,插入方法可以根据删除的方法而定，直接插入尾部，或插到空位置。,2022/12/20,22,2变长记录实际应用中定长记录格式文

9、件较多,但为了增强文件的灵活性,在数据库系统中，有时需要文件中的记录是变长格式。变长记录的表示有字节串形式和定长形式两种。,2022/12/20,23,（1）变长记录的字节串表示形式 尾标志法 把每个记录看成连续的字节串，然后在每个记录的尾部附加 “ 记录尾标志符 ” （）, 表明记录结束。图 6.2 的定长记录文件可以用图 6.4 的格式表示。 记录长度法 记录的开始加一个记录长度的字段来实现，读取数据时以此作为记录结束与否的标志。,2022/12/20,24,2022/12/20,25,图6.4 变长记录的字节串表示形式,字节串表示形式缺点：每条记录长度不一，被删除后的位置难于使用。记录要

10、增长很难 。 “分槽式页结构”：每块的开始设置一个“块首部”，包含以下信息：块中的记录数目，指向块中自由空间尾部的指针，登记每个记录近的开始位置和大小的信息。,2022/12/20,27,图6.5 分槽式页结构,（2）变长记录的定长表示形式 1）预留空间技术 取所有记录中最长的一个记录的长度作为存储空间的记录长度，来存储变长记录。对于预留空间，仍如同定长格式的表格状。缺点：如果每个记录的差别很大，就会造成大量空间的浪费。,2022/12/20,28,2022/12/20,29,例如图 6.4 的字节串表示形式可以用图 6.6 的预留空间技术实现。该方法一般在大多数记录的长度接近最大长度时才使用

11、，否则使用时空间浪费很大。,图6.6 变长记录的预留空间表示形式,2）指针技术 解决记录长度差很大的方法，省去过多的空间浪费。每个定长记录后面增加指针指向在上一方法中可以合并为同一记录的其他记录。被指向的整体成为溢出块。,2022/12/20,30,2022/12/20,31,图6.7 变长记录的指针表示方式,2022/12/20,32,图6.8 固定块和溢出块结构,6.2.2 文件结构,文件中记录的组织方式有无序文件、有序文件、聚集文件和HASH 文件四种。1.无序文件无序文件也称为堆文件无序文件的操作比较简单，但查找效率比较低无序文件的删除操作比较复杂，常用的方法主要有以下三种：,2022

12、/12/20,33,（）首先找到被删记录所在的磁盘块，然后读到主存缓冲区，在缓冲区中删除记录，最后把缓冲区内容写回到磁盘文件（）在每个记录的存储空间增加一个标志位，标识记录删除与否，一般该标志常为空。删除一个记录时，将此记录的标志位置“1”, 以后查找记录时跳过有该标志的记录。（）常用于定长记录文件，删除一个记录时，总是把文件末尾记录移到被删记录位置。,2022/12/20,34,2. 有序文件有序文件是指记录按某个（或某些）域的值的大小顺序组织，一般最为常用的是按关键字的升序或降序排列，即每个记录增加一个指针字段，根据主键的大小用指针把记录链接起来。 文件中每个记录增加一个指针字段，根据查找

13、键的大小用指针把记录连接起来。,2022/12/20,35,2022/12/20,36,图6.9 顺序文件,有序文件操作 删除：只需修改指针即可。同定长记录的方法三 插入： 1）定位：找到要插的位置。按查找键的顺序 2）插入：在找到记录的块内，如果自由空间有空闲纪录，那么插入；若没有就插入到溢出块中。在初始的时候，可以保持无力顺序和查找键的顺序一致，以提高速度，若多次操作后变化很大，有必要重新组织一次。,2022/12/20,37,3. 聚集文件文件允许一个文件有多个关系的记录组成，即记录类型文件。例：可以把有关一个人的全部记录信息放在相邻的位置，按人查找信息时就会很方便。,2022/12/2

14、0,38,2022/12/20,39,图6.10 插入一个记录后的顺序文件,2022/12/20,40,图6.11 聚集文件例子,哈稀 (HASH) 文件又称为散列文件，是一种支持快速存取的文件存储方法。,2022/12/20,41,4. HASH 文件,2022/12/20,42,图6.16.索引结构,6.3 索引技术,2022/12/20,43,图6.13 学生关系索引方式,索引的组织方式主要有线性索引和树形索引两类 。6.3.1线性索引线性索引可分为稠密索引和稀疏索引两种。1.稠密索引 对主文件中每一个查找键值都建立一个索引记号 优点 :查找、更新数据记录方便, 存取速度快缺点 :索引项

15、多, 索引表大, 空间代价大 .,2022/12/20,44,2.稀疏索引 只对主文件中若干查找键值建立一个索引记号。在插入操作较多的应用中采用稀疏索引方式是不太适宜的。,2022/12/20,45,2022/12/20,46,图6.14 多级索引,6.3.2 B树,1.B树的有关概念 m阶平衡树或者为空，或者满足下面条件：每个节点之多有m棵子树根节点或为叶结点，或至少有两棵子树每个非叶结点至少有m/2棵子树根结点到叶结点的每一条路径都有同样的长度，即叶结点在同一层次上 平衡树分为B+树和B树,2022/12/20,47,2022/12/20,48,2.B树的有关约定除叶结点之外的所有其它结点

16、的索引块最多可存放 m -1 个主码值和 m 个地址指针。其格式为 : 叶结点上不包含数据记录本身，而是由记录索引项组成的记录索引块，每个记录索引 项包含有主码值和地址指针。,一般假设，每一个索引块能容纳的索引项数是个奇数，且 m=2d-1 3; 每一个记录索引块能容纳的记录索引项也是个奇数，且n=2e-13。,2022/12/20,49,2022/12/20,50,图6.15 多级索引的B 树,2022/12/20,51,1B+树的概念每个结点至多有m-1个查找键Ki，m个指针Pi;如上图。,6.3.3 B+ 树,2022/12/20,52,叶结点：叶结点的指针指向主文件的记录；查找键在m-

17、1/2m-1之间；叶结点最后的指针指向下一叶结点。非叶结点：组成多级稀疏索引，指针在m/2m之间，指针Pi指向所有查找键大于等于Ki-1,小于Ki。,2022/12/20,53,图6.16 B+树的模型,2022/12/20,54,图6.17 图6.15中的树的树,（1）查找： 方法：先找第一个大于k的查找键值，沿其左面的指针到达下一层，以此查找下去。 特点：查询的层数相同为树的高度，因为都是在叶结点链接主文件。,2022/12/20,55,2B+树的操作,2022/12/20,56,（3）插入不引起索引结点分裂的插入 若以在叶结点出现，直接插入记录； 否则，找到第一个大于的查找键值，在其前面

18、插入，其后的都向后移。,引起分裂的插入； 插入叶结点后，把多出来的分裂出去；修改父结点，插入心结点中的最小值，同理其父结点进行修改。,2022/12/20,57,2022/12/20,58,图6.18 在图6.17中插入值为41数据记录后的树,（4）删除不引起索引结点合并的删除; 查找到主文件，删除记录； 若主文件中还有同查找键的记录不修改索引； 若无，从叶结点中删除相应的键值和指针。,2022/12/20,59,引起合并的删除 在删除叶结点后，引起结点不符合定义，将被删除，若父结点中有也将删除，导致合并的发生。,2022/12/20,60,2022/12/20,61,图6.19 在图6.17

19、 中删除主码值为26的数据记录后的树,3. B+ 树的性能分析显著优点 ：搜索代价较小 ；解决了数据记录在插入，删除和未用回收等存储组织问题 。,2022/12/20,62,小结,数据库是数据的有序集合，需保留在计算机外存介质上反复应用。由于实际应用系统数据规模都很庞大,加之经常要从数据集合中检索需要的数据，所以数据组织的方式，数据的定位方式，以及数据的维护策略的选取十分重要。,2022/12/20,63,2022/12/20,64,在磁盘中,数据库以文件形式组织。文件组织有两种方法：一种是把记录设计成定长格式,也就是每个文件只存储某一确定长度的记录；另一种是变长格式,使之能存放不同长度的记录

20、。实现变长记录的技术有多种,包括分槽式页结构、指针方法和保留空间等方法。,小 结,文件结构有堆文件、顺序文件、散列文件和聚集文件等四种。为了提高查找速度,可以为文件建立索引或散列机制。索引有稠密索引、稀疏索引和多级索引等形式。索引顺序文件组织的主要缺陷是随着文件的增大,性能会下降。为了克服这个缺陷,可以使用B、B+树索引。B+树索引是平衡树,即从树根到树叶所有路径长度相等。这种查找是简单有效的,但插入和删除比较复杂。B树索引和B+树索引类似。,2022/12/20,65,小 结,B树的主要优点在于它去除了查找键值存储中的冗余;主要缺陷在于整体的复杂性以及结点大小给定时减少了扇出。实际应用中,人

21、们总是更愿意使用B+树索引。,2022/12/20,66,小 结,顺序文件需要一个索引结构来定位数据。相比之下,基于散列的文件允许通过散列函数直接得到记录所在的桶地址。静态散列所用的桶地址集合是固定的,不容易适应数据库数据量的快速增长。可扩充散列结构是一种允许修改散列函数的动态散列技术,在数据库增加或缩减时它可以通过分裂或合并桶来适应数据库大小的变化。,2022/12/20,67,习 题,1. 解释下列术语 :(1) 文件，记录，定长记录文件，变长记录文件，跨块记录，非跨块记录。 (2) 有序索引，主索引，稠密索引，稀疏索引，多级索引， B 树，B+ 树。2.试叙述计算机系统的物理存储介质层次

22、，并说明每一种介质的数据访问速度。,2022/12/20,68,习 题,3. 比较有序文件和无序文件的优缺点，什么情况下应该使用有序文件，什么情况下应该使用无序文件。4. 回答下列问题 :(1)HASH 文件的桶溢出问题是什么 ? 如何解决 ?(2) 简单 HASH 文件、动态 HASH 文件和可扩展 HASH 文件之间有什么不同。,2022/12/20,69,习 题,5. 在散列文件组织中，是什么原因引起桶溢出的 ? 有什么办法能减少桶溢出的次数 ?6. 试举一个数据库应用例子，说明在表达变长记录时，有时指针形式比预留空间方法好。并作解释。7. 设查找键值集为 2,3,5,7,11,17,19,23,29,31。假设初始时 B+ 树为空，按升序次序插入键值。就下面三种情况建立三棵 B+ 树 : 4 阶; 6 阶; 8 阶。,2022/12/20,70,