数据库存储结构.ppt

《数据库存储结构.ppt》由会员分享，可在线阅读，更多相关《数据库存储结构.ppt（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章 数据库存储结构 11/29/202211/29/20221 1主要内容主要内容n n 6.1 数据库存储设备数据库存储设备n n 6.2 文件组织文件组织n n 6.3 文件结构文件结构n n 6.4 索引技术索引技术11/29/202211/29/20222 26.1数据库存储设备数据库存储设备 计算机中有两级存储计算机中有两级存储计算机中有两级存储计算机中有两级存储,分别是分别是分别是分别是主存主存主存主存和和和和辅存辅存辅存辅存根据访问数据的速度根据访问数据的速度根据访问数据的速度根据访问数据的速度、成本和可靠性成本和可靠性成本和可靠性成本和可靠性,存储介质存储介质存储介质存储介

2、质可分成以下六类可分成以下六类可分成以下六类可分成以下六类:11/29/202211/29/20223 3 1 1高速缓冲存储器（高速缓冲存储器（高速缓冲存储器（高速缓冲存储器（CacheCache）简称为简称为简称为简称为“高速缓存高速缓存高速缓存高速缓存”，也就是一般说的，也就是一般说的，也就是一般说的，也就是一般说的CacheCache。CacheCache访问速度快，但贵，容量小。访问速度快，但贵，容量小。访问速度快，但贵，容量小。访问速度快，但贵，容量小。2.2.主存储器（主存储器（主存储器（主存储器（Main MemoryMain Memory）主存储器简称为主存主存储器简称为主存

3、主存储器简称为主存主存储器简称为主存,或内存或内存或内存或内存 。主存中的数据主存中的数据主存中的数据主存中的数据在掉电或系统崩溃时在掉电或系统崩溃时在掉电或系统崩溃时在掉电或系统崩溃时,会全部丢失会全部丢失会全部丢失会全部丢失。11/29/202211/29/20224 43.磁盘存储器（磁盘存储器（Magnetic-Disk Storage）n n磁盘是目前最常用的外部存储器磁盘是目前最常用的外部存储器磁盘是目前最常用的外部存储器磁盘是目前最常用的外部存储器,由磁性材料制成由磁性材料制成由磁性材料制成由磁性材料制成,数据存储在磁盘表面数据存储在磁盘表面数据存储在磁盘表面数据存储在磁盘表面。

4、n n磁盘是一种大容量的可直接存取的外部存储设备磁盘是一种大容量的可直接存取的外部存储设备磁盘是一种大容量的可直接存取的外部存储设备磁盘是一种大容量的可直接存取的外部存储设备。在掉电或系统崩溃后在掉电或系统崩溃后在掉电或系统崩溃后在掉电或系统崩溃后,仍能保持数据不丢失仍能保持数据不丢失仍能保持数据不丢失仍能保持数据不丢失。n n硬磁盘的特性硬磁盘的特性硬磁盘的特性硬磁盘的特性：11/29/202211/29/20225 5硬磁盘的物理特性硬磁盘的物理特性n n硬磁盘的总容量为硬磁盘的总容量为硬磁盘的总容量为硬磁盘的总容量为：盘面数目盘面数目盘面数目盘面数目每盘面的磁道数每盘面的磁道数每盘面的磁

5、道数每盘面的磁道数每磁道的盘块数每磁道的盘块数每磁道的盘块数每磁道的盘块数每盘块的字节数每盘块的字节数每盘块的字节数每盘块的字节数 磁盘是一种直接存储设备磁盘是一种直接存储设备磁盘是一种直接存储设备磁盘是一种直接存储设备，可随机读写任一盘可随机读写任一盘可随机读写任一盘可随机读写任一盘块。盘块地址的形式是块。盘块地址的形式是块。盘块地址的形式是块。盘块地址的形式是：柱面号柱面号磁磁头头号号盘块盘块号号图6.1 磁盘块地址形式示意图 11/29/202211/29/20226 6磁盘的性能指标磁盘的性能指标 磁盘的磁盘的磁盘的磁盘的性能用磁盘的性能用磁盘的性能用磁盘的性能用磁盘的容量容量容量容量

6、、存取时间存取时间存取时间存取时间、数据传数据传数据传数据传输速度输速度输速度输速度和和和和可靠性可靠性可靠性可靠性四个参数衡量四个参数衡量四个参数衡量四个参数衡量。内内外存间的数据交换外存间的数据交换 访问的数据不在主存时访问的数据不在主存时访问的数据不在主存时访问的数据不在主存时,需通过外存加载需通过外存加载需通过外存加载需通过外存加载，所所所所以内外存间要频繁地进行数据交换以内外存间要频繁地进行数据交换以内外存间要频繁地进行数据交换以内外存间要频繁地进行数据交换，每交换一次每交换一次每交换一次每交换一次数据数据数据数据，就称为一次就称为一次就称为一次就称为一次 I/O I/O 操作操作操

7、作操作。11/29/202211/29/20227 7 数据块的长度不一定恰好等于记录的整数倍数据块的长度不一定恰好等于记录的整数倍数据块的长度不一定恰好等于记录的整数倍数据块的长度不一定恰好等于记录的整数倍，通常有两种通常有两种通常有两种通常有两种 组块方式组块方式组块方式组块方式 ：n n不跨块方式不跨块方式不跨块方式不跨块方式：一个数据块只包含若干完整记录一个数据块只包含若干完整记录一个数据块只包含若干完整记录一个数据块只包含若干完整记录，不足以容纳一个记录的零头空间放弃不用不足以容纳一个记录的零头空间放弃不用不足以容纳一个记录的零头空间放弃不用不足以容纳一个记录的零头空间放弃不用。n

8、n跨块方式跨块方式跨块方式跨块方式：允许一个记录跨在不同数据块允许一个记录跨在不同数据块允许一个记录跨在不同数据块允许一个记录跨在不同数据块。这种这种这种这种组块方式虽然可节省空间组块方式虽然可节省空间组块方式虽然可节省空间组块方式虽然可节省空间，但实现比较困难但实现比较困难但实现比较困难但实现比较困难，用得用得用得用得较少较少较少较少。11/29/202211/29/20228 8n n廉价磁盘冗余阵列廉价磁盘冗余阵列 n n(Redundant Array of Inexpensive(Redundant Array of Inexpensive（或（或（或（或IndscendentInd

9、scendent）Disks Disks，简称，简称，简称，简称RAID)RAID)它是利用一台磁盘阵列控制器来统一管理和控它是利用一台磁盘阵列控制器来统一管理和控它是利用一台磁盘阵列控制器来统一管理和控它是利用一台磁盘阵列控制器来统一管理和控制一组制一组制一组制一组(几台到几十台几台到几十台几台到几十台几台到几十台)磁盘驱动器，组成一磁盘驱动器，组成一磁盘驱动器，组成一磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统。个高度可靠的、快速的大容量磁盘系统。个高度可靠的、快速的大容量磁盘系统。个高度可靠的、快速的大容量磁盘系统。uu 实现途实现途实现途实现途径径径径有两个有两个有两个有两个：

10、数据重复存储数据重复存储数据重复存储数据重复存储 和和和和通过并行提高数据传输速度通过并行提高数据传输速度通过并行提高数据传输速度通过并行提高数据传输速度 n n RAID RAID 按照其基本特性按照其基本特性按照其基本特性按照其基本特性，可分为八级可分为八级可分为八级可分为八级 。11/29/202211/29/20229 94 磁带磁带uu磁带是一种顺序存储设备磁带是一种顺序存储设备磁带是一种顺序存储设备磁带是一种顺序存储设备,即磁带只能顺序访问，即磁带只能顺序访问，即磁带只能顺序访问，即磁带只能顺序访问，不能随机访问。不能随机访问。不能随机访问。不能随机访问。uu主要用于数据备份或数据

11、归档。主要用于数据备份或数据归档。主要用于数据备份或数据归档。主要用于数据备份或数据归档。uu磁带的可靠性较好，主要有两大用途：磁带的可靠性较好，主要有两大用途：磁带的可靠性较好，主要有两大用途：磁带的可靠性较好，主要有两大用途：作为磁盘的后援存储器，存储数据库文件的作为磁盘的后援存储器，存储数据库文件的作为磁盘的后援存储器，存储数据库文件的作为磁盘的后援存储器，存储数据库文件的副本副本副本副本 用来存储磁盘上存储不了的大型数据库文件用来存储磁盘上存储不了的大型数据库文件用来存储磁盘上存储不了的大型数据库文件用来存储磁盘上存储不了的大型数据库文件,数据库中不常用的数据库文件或历史数据可以存储数

12、据库中不常用的数据库文件或历史数据可以存储数据库中不常用的数据库文件或历史数据可以存储数据库中不常用的数据库文件或历史数据可以存储在磁带上。在磁带上。在磁带上。在磁带上。11/29/202211/29/202210105 5 光存储器光存储器n n光存储器是多媒体信息的主要存储设备，作为分光存储器是多媒体信息的主要存储设备，作为分光存储器是多媒体信息的主要存储设备，作为分光存储器是多媒体信息的主要存储设备，作为分布式软件的主要存储介质，可存储音频、图像一布式软件的主要存储介质，可存储音频、图像一布式软件的主要存储介质，可存储音频、图像一布式软件的主要存储介质，可存储音频、图像一类的数据类的数据

13、类的数据类的数据 。n n目前流行的光存储器是光盘只读存储器目前流行的光存储器是光盘只读存储器目前流行的光存储器是光盘只读存储器目前流行的光存储器是光盘只读存储器(CD-(CD-(CD-(CD-ROM)ROM)ROM)ROM)。11/29/202211/29/202211116 6 快擦写存储器（快擦写存储器（Flash MemoryFlash Memory）n n快擦写存储器又称为快擦写存储器又称为快擦写存储器又称为快擦写存储器又称为“电可擦可编程只读存储器电可擦可编程只读存储器电可擦可编程只读存储器电可擦可编程只读存储器”，快闪存在掉电后仍能保持数据不丢失。，快闪存在掉电后仍能保持数据不丢

14、失。，快闪存在掉电后仍能保持数据不丢失。，快闪存在掉电后仍能保持数据不丢失。n n快闪存的缺陷是只能支持有限次擦写。而且不能快闪存的缺陷是只能支持有限次擦写。而且不能快闪存的缺陷是只能支持有限次擦写。而且不能快闪存的缺陷是只能支持有限次擦写。而且不能直接重写，必须先擦去整组存储器的内存，然后再直接重写，必须先擦去整组存储器的内存，然后再直接重写，必须先擦去整组存储器的内存，然后再直接重写，必须先擦去整组存储器的内存，然后再写数据进去。写数据进去。写数据进去。写数据进去。11/29/202211/29/202212126.2 文件组织文件组织n n外存中，数据库以文件形式组织，而文件外存中，数据

15、库以文件形式组织，而文件又是由记录组成。记录在物理文件中的实又是由记录组成。记录在物理文件中的实现就是本节讨论的内容。现就是本节讨论的内容。n n文件组织的两种方式：定长格式和变长格文件组织的两种方式：定长格式和变长格式。式。11/29/202211/29/20221313 定长记录定长记录定长记录定长记录 就就就就是是是是每每每每条条条条记记记记录录录录都都都都是是是是占占占占用用用用一一一一定定定定长长长长度度度度的的的的字字字字节节节节数数数数。记记记记录录录录的的的的排排排排列列列列也也也也就就就就是是是是一一一一张张张张表表表表格格格格每每每每行行行行有有有有相相相相同同同同的的的的

16、长长长长度度度度，以一行为单元进行增加删除等修改操作。以一行为单元进行增加删除等修改操作。以一行为单元进行增加删除等修改操作。以一行为单元进行增加删除等修改操作。Sn1Sn1000001000001甲甲Sn2Sn2000002000002乙乙Sn3Sn3000003000003丙丙Sn4Sn4000004000004丁丁11/29/202211/29/20221414SnumCnumScoreS003160S001283S005480S004185S006375S003280S002285S004260S003340图6.2 定长记录的文件 11/29/202211/29/20221515图图

17、图图6.3 6.3 6.3 6.3 删除记录删除记录删除记录删除记录2 2，5 5，7 7后的文件结构后的文件结构后的文件结构后的文件结构 11/29/202211/29/20221616n n如上图每条记录包含姓名、学号、班级三条信息。如上图每条记录包含姓名、学号、班级三条信息。如上图每条记录包含姓名、学号、班级三条信息。如上图每条记录包含姓名、学号、班级三条信息。在每条记录中对应的信息占相同的字节数，所以在每条记录中对应的信息占相同的字节数，所以在每条记录中对应的信息占相同的字节数，所以在每条记录中对应的信息占相同的字节数，所以每条记录的长度一定，构成了一个含有四条记录每条记录的长度一定，

18、构成了一个含有四条记录每条记录的长度一定，构成了一个含有四条记录每条记录的长度一定，构成了一个含有四条记录的定长记录的文件。的定长记录的文件。的定长记录的文件。的定长记录的文件。n n存在的两个问题：存在的两个问题：存在的两个问题：存在的两个问题：1.1.删除：删除后是在其位置补充一个记录还是忽略删除：删除后是在其位置补充一个记录还是忽略删除：删除后是在其位置补充一个记录还是忽略删除：删除后是在其位置补充一个记录还是忽略这个位置；这个位置；这个位置；这个位置；2.2.长度：若物理上每个块的大小不等于每个记录的长度：若物理上每个块的大小不等于每个记录的长度：若物理上每个块的大小不等于每个记录的长

19、度：若物理上每个块的大小不等于每个记录的长度倍数，则必然在读这样的记录时要访问两个长度倍数，则必然在读这样的记录时要访问两个长度倍数，则必然在读这样的记录时要访问两个长度倍数，则必然在读这样的记录时要访问两个块。块。块。块。11/29/202211/29/202217176.2.1.1 删除方法 1.删除记录后，把记录依次上移。缺点移动次数过多。2.把最后的记录补到删除的位置。只需移动一次。以上两个方法都需要移动结点，操作以上两个方法都需要移动结点，操作不灵活，处于灵活的考虑必然会想到指针，不灵活，处于灵活的考虑必然会想到指针，就是第三种方法。就是第三种方法。11/29/202211/29/2

20、02218183.3.把删除的结点用指针链接起来把删除的结点用指针链接起来把删除的结点用指针链接起来把删除的结点用指针链接起来n n首先，文件增设首先，文件增设首先，文件增设首先，文件增设“文件首部文件首部文件首部文件首部”，其中有一个指针，其中有一个指针，其中有一个指针，其中有一个指针指向第一个被删除的记录位置，所有被删除记录指向第一个被删除的记录位置，所有被删除记录指向第一个被删除的记录位置，所有被删除记录指向第一个被删除的记录位置，所有被删除记录的位置都用指针链接起来，构成的位置都用指针链接起来，构成的位置都用指针链接起来，构成的位置都用指针链接起来，构成“空闲记录链表空闲记录链表空闲记

21、录链表空闲记录链表”。n n缺点：这些被指针链接的记录被称为缺点：这些被指针链接的记录被称为缺点：这些被指针链接的记录被称为缺点：这些被指针链接的记录被称为“被拴记录被拴记录被拴记录被拴记录”，若被删记录被删掉，则指向记录的指针称为，若被删记录被删掉，则指向记录的指针称为，若被删记录被删掉，则指向记录的指针称为，若被删记录被删掉，则指向记录的指针称为“悬挂指针悬挂指针悬挂指针悬挂指针”，所指空间称为，所指空间称为，所指空间称为，所指空间称为“垃圾垃圾垃圾垃圾”，也就是，也就是，也就是，也就是别人无法使用而又被空闲着。别人无法使用而又被空闲着。别人无法使用而又被空闲着。别人无法使用而又被空闲着。

22、11/29/202211/29/202219196.2.1.2.6.2.1.2.插入方法插入方法插入方法插入方法n n可以根据删除的方法而定，直接插入尾部，或插可以根据删除的方法而定，直接插入尾部，或插可以根据删除的方法而定，直接插入尾部，或插可以根据删除的方法而定，直接插入尾部，或插到空位置。到空位置。到空位置。到空位置。变长记录变长记录变长记录变长记录n n实实实实际际际际应应应应用用用用中中中中定定定定长长长长记记记记录录录录格格格格式式式式文文文文件件件件较较较较多多多多,但但但但为为为为了了了了增增增增强强强强文文文文件件件件的的的的灵灵灵灵活活活活性性性性,在在在在数数数数据据据据

23、库库库库系系系系统统统统中中中中，有有有有时时时时需需需需要要要要文文文文件件件件中中中中的的的的记录是变长格式。记录是变长格式。记录是变长格式。记录是变长格式。n n变长记录的表示有变长记录的表示有变长记录的表示有变长记录的表示有字节串形式字节串形式字节串形式字节串形式和和和和定长形式定长形式定长形式定长形式两种。两种。两种。两种。11/29/202211/29/20222020 6.2.2.1 6.2.2.1 变长记录的字节串表示形式变长记录的字节串表示形式变长记录的字节串表示形式变长记录的字节串表示形式 尾标志法尾标志法尾标志法尾标志法 把每个记录看成连续的字节串，然后在每把每个记录看成

24、连续的字节串，然后在每把每个记录看成连续的字节串，然后在每把每个记录看成连续的字节串，然后在每个记录的尾部附加个记录的尾部附加个记录的尾部附加个记录的尾部附加“记录尾标志符记录尾标志符记录尾标志符记录尾标志符”（）,表明记录结束表明记录结束表明记录结束表明记录结束。图图图图 6.2 6.2 6.2 6.2 的定长记录文件可以用的定长记录文件可以用的定长记录文件可以用的定长记录文件可以用图图图图 6.4 6.4 6.4 6.4 的格式表示。的格式表示。的格式表示。的格式表示。记录长度法记录长度法记录长度法记录长度法 记录的开始加一个记录长度的字段来实现记录的开始加一个记录长度的字段来实现记录的开

25、始加一个记录长度的字段来实现记录的开始加一个记录长度的字段来实现，读取数据时以此作为记录结束与否的标志读取数据时以此作为记录结束与否的标志读取数据时以此作为记录结束与否的标志读取数据时以此作为记录结束与否的标志。11/29/202211/29/20222121SnumCnumScoreCnumScoreCnumScoreS003160280340S001283S005480S004185260S006375S002285 图6.4 变长记录的字节串表示形式 11/29/202211/29/20222222n n字节串表示形式缺点：字节串表示形式缺点：字节串表示形式缺点：字节串表示形式缺点：每条

26、记录长度不一，被删除后的位置难于使用。每条记录长度不一，被删除后的位置难于使用。每条记录长度不一，被删除后的位置难于使用。每条记录长度不一，被删除后的位置难于使用。记录要增长很难记录要增长很难记录要增长很难记录要增长很难 。n n “分槽式页结构分槽式页结构分槽式页结构分槽式页结构”：每块的开始设置一个：每块的开始设置一个：每块的开始设置一个：每块的开始设置一个“块首部块首部块首部块首部”，包含以下信息：块中的记录数目，包含以下信息：块中的记录数目，包含以下信息：块中的记录数目，包含以下信息：块中的记录数目，只想块中自由空间尾部的指针，登记每个记录只想块中自由空间尾部的指针，登记每个记录只想块

27、中自由空间尾部的指针，登记每个记录只想块中自由空间尾部的指针，登记每个记录近的开始位置和大小的信息。近的开始位置和大小的信息。近的开始位置和大小的信息。近的开始位置和大小的信息。11/29/202211/29/20222323图图图图6.5 6.5 分槽式页结构分槽式页结构分槽式页结构分槽式页结构 11/29/202211/29/20222424变长记录的定长表示形式变长记录的定长表示形式 1.1.预留空间技术预留空间技术 n n 取所有记录中最长的一个记录的长度作为存储取所有记录中最长的一个记录的长度作为存储取所有记录中最长的一个记录的长度作为存储取所有记录中最长的一个记录的长度作为存储空间

28、的记录长度，来存储变长记录。对于预留空空间的记录长度，来存储变长记录。对于预留空空间的记录长度，来存储变长记录。对于预留空空间的记录长度，来存储变长记录。对于预留空间，仍如同定长格式的表格状。间，仍如同定长格式的表格状。间，仍如同定长格式的表格状。间，仍如同定长格式的表格状。n n缺点：如果每个记录的差别很大，就会造成大量缺点：如果每个记录的差别很大，就会造成大量缺点：如果每个记录的差别很大，就会造成大量缺点：如果每个记录的差别很大，就会造成大量空间的浪费。空间的浪费。空间的浪费。空间的浪费。11/29/202211/29/20222525 例如图 6.4 的字节串表示形式可以用图 6.6 的

29、预留空间技术实现。该方法一般在大多数记录的长度接近最大长度时才使用，否则使用时空间浪费很大。SnumCnumScoreCnumScoreCnumScoreS003160280340S001283S005480S004185260S006375S002285 图6.6 变长记录的预留空间表示形式11/29/202211/29/202226262.2.指针技术指针技术 n n解决记录长度差很大的方法，省去过多的解决记录长度差很大的方法，省去过多的空间浪费。空间浪费。n n每个定长记录后面增加指针指向在上一方每个定长记录后面增加指针指向在上一方法中可以合并为同一记录的其他记录。法中可以合并为同一记录

30、的其他记录。n n被指向的整体成为溢出块。被指向的整体成为溢出块。11/29/202211/29/20222727图图图图6.7 6.7 变长记录的指针表示方式变长记录的指针表示方式变长记录的指针表示方式变长记录的指针表示方式 11/29/202211/29/20222828图图图图6.8 6.8 固定块和溢出块结构固定块和溢出块结构固定块和溢出块结构固定块和溢出块结构 11/29/202211/29/202229296.3 文件结构文件结构n n文件中记录的组织方式有文件中记录的组织方式有无序件、有序文件、无序件、有序文件、聚集文件聚集文件和和HASHHASH 文件四种。文件四种。无序文件无

31、序文件无序文件无序文件n n无序文件也称为无序文件也称为堆文件堆文件无序文件的操作比较简无序文件的操作比较简单，但查找效率比较低单，但查找效率比较低n n无序文件的删除操作比较复杂，常用的方法主要无序文件的删除操作比较复杂，常用的方法主要有以下三种：有以下三种：11/29/202211/29/20223030（）首先找到被删记录所在的磁盘块，然后读到主（）首先找到被删记录所在的磁盘块，然后读到主（）首先找到被删记录所在的磁盘块，然后读到主（）首先找到被删记录所在的磁盘块，然后读到主存缓冲区，在缓冲区中删除记录，最后把缓冲区内存缓冲区，在缓冲区中删除记录，最后把缓冲区内存缓冲区，在缓冲区中删除记

32、录，最后把缓冲区内存缓冲区，在缓冲区中删除记录，最后把缓冲区内容写回到磁盘文件容写回到磁盘文件容写回到磁盘文件容写回到磁盘文件（）在每个记录的存储空间增加一个标志位，标识（）在每个记录的存储空间增加一个标志位，标识（）在每个记录的存储空间增加一个标志位，标识（）在每个记录的存储空间增加一个标志位，标识记录删除与否，一般该标志常为空。删除一个记录记录删除与否，一般该标志常为空。删除一个记录记录删除与否，一般该标志常为空。删除一个记录记录删除与否，一般该标志常为空。删除一个记录时，将此记录的标志位置时，将此记录的标志位置时，将此记录的标志位置时，将此记录的标志位置“1”,“1”,以后查找记录时跳以

33、后查找记录时跳以后查找记录时跳以后查找记录时跳过有该标志的记录。过有该标志的记录。过有该标志的记录。过有该标志的记录。（）常用于定长记录文件，删除一个记录时，总是（）常用于定长记录文件，删除一个记录时，总是（）常用于定长记录文件，删除一个记录时，总是（）常用于定长记录文件，删除一个记录时，总是把文件末尾记录移到被删记录位置。把文件末尾记录移到被删记录位置。把文件末尾记录移到被删记录位置。把文件末尾记录移到被删记录位置。11/29/202211/29/202231316.3.2 6.3.2 有序文件有序文件有序文件有序文件n n有序文件是指记录按某个（或某些）域的值的大有序文件是指记录按某个（或

34、某些）域的值的大有序文件是指记录按某个（或某些）域的值的大有序文件是指记录按某个（或某些）域的值的大小顺序组织，一般最为常用的是按关键字的升序小顺序组织，一般最为常用的是按关键字的升序小顺序组织，一般最为常用的是按关键字的升序小顺序组织，一般最为常用的是按关键字的升序或降序排列，即每个记录增加一个指针字段，根或降序排列，即每个记录增加一个指针字段，根或降序排列，即每个记录增加一个指针字段，根或降序排列，即每个记录增加一个指针字段，根据主键的大小用指针把记录链接起来。据主键的大小用指针把记录链接起来。据主键的大小用指针把记录链接起来。据主键的大小用指针把记录链接起来。n n文件中每个记录增加一个

35、指针字段，根据查找键文件中每个记录增加一个指针字段，根据查找键文件中每个记录增加一个指针字段，根据查找键文件中每个记录增加一个指针字段，根据查找键的大小用指针把记录连接起来。的大小用指针把记录连接起来。的大小用指针把记录连接起来。的大小用指针把记录连接起来。11/29/202211/29/20223232图图图图6.96.9 顺序文件顺序文件顺序文件顺序文件 11/29/202211/29/20223333uu有序文件操作有序文件操作有序文件操作有序文件操作 n n 删除删除删除删除：只需修改指针即可。同定长记录的方法三：只需修改指针即可。同定长记录的方法三：只需修改指针即可。同定长记录的方法

36、三：只需修改指针即可。同定长记录的方法三n n 插入插入插入插入：1 1）定位：找到要插的位置。按查找键的顺序）定位：找到要插的位置。按查找键的顺序）定位：找到要插的位置。按查找键的顺序）定位：找到要插的位置。按查找键的顺序 2 2）插入：在找到记录的块内，如果自由空间）插入：在找到记录的块内，如果自由空间）插入：在找到记录的块内，如果自由空间）插入：在找到记录的块内，如果自由空间有空闲纪录，那么插入；若没有就插入到溢出块中。有空闲纪录，那么插入；若没有就插入到溢出块中。有空闲纪录，那么插入；若没有就插入到溢出块中。有空闲纪录，那么插入；若没有就插入到溢出块中。n n在初始的时候，可以保持无力

37、顺序和查找键的顺序在初始的时候，可以保持无力顺序和查找键的顺序在初始的时候，可以保持无力顺序和查找键的顺序在初始的时候，可以保持无力顺序和查找键的顺序一致，以提高速度，若多次操作后变化很大，有必一致，以提高速度，若多次操作后变化很大，有必一致，以提高速度，若多次操作后变化很大，有必一致，以提高速度，若多次操作后变化很大，有必要重新组织一次。要重新组织一次。要重新组织一次。要重新组织一次。11/29/202211/29/202234346.3.3 聚集文件聚集文件n n文件允许一个文件有多个关系的记录组成，文件允许一个文件有多个关系的记录组成，即记录类型文件。即记录类型文件。例：可以把有关一个人

38、的全部记录信息放在例：可以把有关一个人的全部记录信息放在相邻的位置，按人查找信息时就会很方便。相邻的位置，按人查找信息时就会很方便。11/29/202211/29/20223535图图图图6.106.10 插入一个记录后的顺序文件插入一个记录后的顺序文件插入一个记录后的顺序文件插入一个记录后的顺序文件 11/29/202211/29/20223636图图图图6.116.11 聚集文件例子聚集文件例子聚集文件例子聚集文件例子 11/29/202211/29/202237376.3.4 HASH 文件文件n n哈哈哈哈稀稀稀稀 (HASH)(HASH)文文文文件件件件又又又又称称称称为为为为散散散

39、散列列列列文文文文件件件件，是是是是一一一一种种种种支支支支持持持持快快快快速存取的文件存储方法。速存取的文件存储方法。速存取的文件存储方法。速存取的文件存储方法。1 1散列的概念：散列的概念：散列的概念：散列的概念：设设设设KK是是是是所所所所有有有有查查查查找找找找键键键键值值值值的的的的集集集集合合合合，BB是是是是所所所所有有有有桶桶桶桶地地地地址址址址的的的的集集集集合合合合。散散散散列列列列函函函函数数数数h h是是是是从从从从KK到到到到BB的的的的函函函函数数数数，它它它它把把把把每每每每个个个个查查查查找找找找键键键键值值值值映映映映射射射射到到到到地地地地址址址址集集集集合

40、合合合中中中中的的的的地地地地址址址址。其其其其中中中中每每每每个个个个桶桶桶桶的的的的大大大大小小小小一一一一定。定。定。定。查查找找键键集集K桶桶地地址址集集B主主文文件件记记录录11/29/202211/29/20223838n n检索：检索：检索：检索：n n 1 1）检索）检索）检索）检索KiKi的记录，首先计算的记录，首先计算的记录，首先计算的记录，首先计算h(Ki)h(Ki)在在在在BB集合中集合中集合中集合中 2 2）根据桶地址找到桶）根据桶地址找到桶）根据桶地址找到桶）根据桶地址找到桶 3 3）桶内查找）桶内查找）桶内查找）桶内查找 特点：特点：特点：特点：不同的查找键值的记

41、录可能在同一个不同的查找键值的记录可能在同一个不同的查找键值的记录可能在同一个不同的查找键值的记录可能在同一个桶内，找到桶后仍然有进行检测。桶内，找到桶后仍然有进行检测。桶内，找到桶后仍然有进行检测。桶内，找到桶后仍然有进行检测。n n删除：找到记录直接删除即可。删除：找到记录直接删除即可。删除：找到记录直接删除即可。删除：找到记录直接删除即可。11/29/202211/29/202239392散列函数散列函数 n n要满足两个条件：要满足两个条件：1）使地址分布均匀；）使地址分布均匀；2）地质分布随机。）地质分布随机。n n 常用方法：常用方法：质数除余法质数除余法。n n 缺点：函数的设计

42、，若设计不好会造成很缺点：函数的设计，若设计不好会造成很大的不均匀性，查找时间的浪费。大的不均匀性，查找时间的浪费。11/29/202211/29/202240403.3.散列碰撞散列碰撞散列碰撞散列碰撞 n n 问题问题问题问题：由于同所存储的记录数是一定的，再插入由于同所存储的记录数是一定的，再插入由于同所存储的记录数是一定的，再插入由于同所存储的记录数是一定的，再插入操作时很容易发生溢出。操作时很容易发生溢出。操作时很容易发生溢出。操作时很容易发生溢出。n n 原因原因原因原因：一是桶的数目少；二是散列的均匀性不好。：一是桶的数目少；二是散列的均匀性不好。：一是桶的数目少；二是散列的均匀

43、性不好。：一是桶的数目少；二是散列的均匀性不好。n n 解决：解决：解决：解决：1 1）溢出链法：每个同都作为基本桶存在，）溢出链法：每个同都作为基本桶存在，）溢出链法：每个同都作为基本桶存在，）溢出链法：每个同都作为基本桶存在，若溢出系统提供一处同连接在基本桶后面。若溢出系统提供一处同连接在基本桶后面。若溢出系统提供一处同连接在基本桶后面。若溢出系统提供一处同连接在基本桶后面。2 2）开放式散列法：只存在基本桶，若溢）开放式散列法：只存在基本桶，若溢）开放式散列法：只存在基本桶，若溢）开放式散列法：只存在基本桶，若溢 出就插入其他空闲的桶。有两种选择方式：出就插入其他空闲的桶。有两种选择方式

44、：出就插入其他空闲的桶。有两种选择方式：出就插入其他空闲的桶。有两种选择方式：1 1。在溢出桶下面的一个空闲桶；。在溢出桶下面的一个空闲桶；。在溢出桶下面的一个空闲桶；。在溢出桶下面的一个空闲桶；2 2。采用二次散列的方法。采用二次散列的方法。采用二次散列的方法。采用二次散列的方法。11/29/202211/29/20224141图图图图6.12 6.12 6.12 6.12 散列结构的溢出链散列结构的溢出链散列结构的溢出链散列结构的溢出链 11/29/202211/29/20224242.散列方法散列方法 n n常用的常用的 HASH 方法有方法有简单简单 HASH 方法，动方法，动态态 H

45、ASH 方法方法和和可扩展的可扩展的 HASH 方法方法n n评价评价：散列方法必须选取恰当的散列函数。：散列方法必须选取恰当的散列函数。11/29/202211/29/20224343 图图图图6.136.136.136.13 HASH HASH桶目录示例桶目录示例桶目录示例桶目录示例 11/29/202211/29/202244441.1.简单简单简单简单 HASH HASH 方法。方法。方法。方法。n n该方法采用固定个数的该方法采用固定个数的该方法采用固定个数的该方法采用固定个数的 HASH HASH 桶，即把文件划分桶，即把文件划分桶，即把文件划分桶，即把文件划分为为为为 N N 个

46、个个个HASHHASH桶，每个桶，每个桶，每个桶，每个HASH HASH 桶对应一个磁盘块，桶对应一个磁盘块，桶对应一个磁盘块，桶对应一个磁盘块，每个每个每个每个 HASH HASH 桶有一编号。桶有一编号。桶有一编号。桶有一编号。n n缺点：缺点：缺点：缺点：只能有效地支持只能有效地支持只能有效地支持只能有效地支持 HASH HASH 域上具有相域上具有相域上具有相域上具有相 等比较的数据操作。等比较的数据操作。等比较的数据操作。等比较的数据操作。由于由于由于由于 HASH HASH 桶的数量一成不变，当桶的数量一成不变，当桶的数量一成不变，当桶的数量一成不变，当 文件记录较少时文件记录较少

47、时文件记录较少时文件记录较少时 ，影响记录的存取效率。，影响记录的存取效率。，影响记录的存取效率。，影响记录的存取效率。11/29/202211/29/202245452.动态动态 HASH 方法方法 n n动态动态动态动态 HASH HASH 方法中，方法中，方法中，方法中，HASH HASH 桶与磁盘块一一对桶与磁盘块一一对桶与磁盘块一一对桶与磁盘块一一对应。应。应。应。n n HASH HASH 桶的数量不是固定的，而是随文件记录桶的数量不是固定的，而是随文件记录桶的数量不是固定的，而是随文件记录桶的数量不是固定的，而是随文件记录的变化而增加或减少的。的变化而增加或减少的。的变化而增加或

48、减少的。的变化而增加或减少的。11/29/202211/29/20224646 图图图图6.14 6.14 6.14 6.14 动态动态动态动态HASHHASH方法结构方法结构方法结构方法结构 11/29/202211/29/202247473.3.3.3.可扩展的可扩展的可扩展的可扩展的 HASH HASH HASH HASH 方法方法方法方法 n n特点：特点：特点：特点：按照实际需要申请或释放空间。按照实际需要申请或释放空间。按照实际需要申请或释放空间。按照实际需要申请或释放空间。n n查找：查找：查找：查找：求出求出求出求出h(Ki)h(Ki)前前前前i i位值位值位值位值m,m,沿桶

49、地指表位置沿桶地指表位置沿桶地指表位置沿桶地指表位置mm处的指处的指处的指处的指针到达某个同中去找记录。针到达某个同中去找记录。针到达某个同中去找记录。针到达某个同中去找记录。n n插入：插入：插入：插入：先查找到相应的桶，若有空闲空间直接插入；先查找到相应的桶，若有空闲空间直接插入；先查找到相应的桶，若有空闲空间直接插入；先查找到相应的桶，若有空闲空间直接插入；11/29/202211/29/20224848图图图图6.15 6.15 可扩展的可扩展的可扩展的可扩展的HASHHASH方法的结构方法的结构方法的结构方法的结构 11/29/202211/29/20224949n n分裂桶：分裂桶

50、：分裂桶：分裂桶：情况一：情况一：情况一：情况一：指向这个桶只有一个指针。增加指向这个桶只有一个指针。增加指向这个桶只有一个指针。增加指向这个桶只有一个指针。增加i i的值，桶的值，桶的值，桶的值，桶地址表加倍，每一项之分列成相邻的两项，但是地址表加倍，每一项之分列成相邻的两项，但是地址表加倍，每一项之分列成相邻的两项，但是地址表加倍，每一项之分列成相邻的两项，但是指向同一个桶。新申请的桶，就得到其中第二个指向同一个桶。新申请的桶，就得到其中第二个指向同一个桶。新申请的桶，就得到其中第二个指向同一个桶。新申请的桶，就得到其中第二个指针。指针。指针。指针。情况二：情况二：情况二：情况二：指向这个