第6章数据库存储结构

《第6章数据库存储结构》由会员分享，可在线阅读，更多相关《第6章数据库存储结构（78页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

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

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

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

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

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

10、有两个有两个有两个：数据重复存储数据重复存储数据重复存储数据重复存储 和和和和通过并行提高数据传输速度通过并行提高数据传输速度通过并行提高数据传输速度通过并行提高数据传输速度 n n RAID RAID 按照其基本特性按照其基本特性按照其基本特性按照其基本特性，可分为八级可分为八级可分为八级可分为八级 。 9/3/20249/3/20249 94 磁带磁带uu磁带是一种顺序存储设备磁带是一种顺序存储设备磁带是一种顺序存储设备磁带是一种顺序存储设备 , , , ,即磁带只能顺序访问即磁带只能顺序访问即磁带只能顺序访问即磁带只能顺序访问，不能随机访问。不能随机访问。不能随机访问。不能随机访问。uu

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

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

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

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

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

16、同同同的的的的长长长长度度度度，以一行为单元进行增加删除等修改操作。以一行为单元进行增加删除等修改操作。以一行为单元进行增加删除等修改操作。以一行为单元进行增加删除等修改操作。Sn1Sn1000001000001甲甲Sn2Sn2000002000002乙乙Sn3Sn3000003000003丙丙Sn4Sn4000004000004丁丁9/3/20249/3/20241414SnumCnumScoreS003160S001283S005480S004185S006375S003280S002285S004260S003340图6.2 定长记录的文件 9/3/20249/3/20241515图图图

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

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

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

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

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

22、着。别人无法使用而又被空闲着。9/3/20249/3/202419196.2.1.2. 6.2.1.2. 插入方法插入方法插入方法插入方法n n可以根据删除的方法而定，直接插入尾部，或插可以根据删除的方法而定，直接插入尾部，或插可以根据删除的方法而定，直接插入尾部，或插可以根据删除的方法而定，直接插入尾部，或插到空位置。到空位置。到空位置。到空位置。6.2.26.2.2变长记录变长记录变长记录变长记录n n实实实实际际际际应应应应用用用用中中中中定定定定长长长长记记记记录录录录格格格格式式式式文文文文件件件件较较较较多多多多, , , ,但但但但为为为为了了了了增增增增强强强强文文文文件件件件

23、的的的的灵灵灵灵活活活活性性性性, , , ,在在在在数数数数据据据据库库库库系系系系统统统统中中中中，有有有有时时时时需需需需要要要要文文文文件件件件中中中中的的的的记录是变长格式。记录是变长格式。记录是变长格式。记录是变长格式。n n变长记录的表示有变长记录的表示有变长记录的表示有变长记录的表示有字节串形式字节串形式字节串形式字节串形式和和和和定长形式定长形式定长形式定长形式两种。两种。两种。两种。 9/3/20249/3/20242020 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、法 记录的开始加一个记录长度的字段来实现记录的开始加一个记录长度的字段来实现记录的开始加一个记录长度的字段来实现记录的开始加一个记录长度的字段来实现，读取数据时以此作为记录结束与否的标志读取数据时以此作为记录结束与否的标志读取数据时以此作为记录结束与否的标志读取数据时以此作为记录结束与否的标志。 9/3/20249/3/20242121SnumCnumScoreCnumScoreCnumScoreS003160280340S001283S005480S004185260S006375S002285 图6.4 变长记录的字节串表示形式 9/3/20249/3/20242222n n字节串表示形式

26、字节串表示形式字节串表示形式字节串表示形式缺点：缺点：缺点：缺点：每条记录长度不一，被删除后的位置难于使用。每条记录长度不一，被删除后的位置难于使用。每条记录长度不一，被删除后的位置难于使用。每条记录长度不一，被删除后的位置难于使用。记录要增长很难记录要增长很难记录要增长很难记录要增长很难 。n n “ “分槽式页结构分槽式页结构分槽式页结构分槽式页结构” ”：每块的开始设置一个：每块的开始设置一个：每块的开始设置一个：每块的开始设置一个“ “块首部块首部块首部块首部” ”，包含以下信息：块中的记录数目，包含以下信息：块中的记录数目，包含以下信息：块中的记录数目，包含以下信息：块中的记录数目，

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

28、取所有记录中最长的一个记录的长度作为存储取所有记录中最长的一个记录的长度作为存储空间的记录长度，来存储变长记录。对于预留空空间的记录长度，来存储变长记录。对于预留空空间的记录长度，来存储变长记录。对于预留空空间的记录长度，来存储变长记录。对于预留空间，仍如同定长格式的表格状。间，仍如同定长格式的表格状。间，仍如同定长格式的表格状。间，仍如同定长格式的表格状。n n缺点：如果每个记录的差别很大，就会造成大量缺点：如果每个记录的差别很大，就会造成大量缺点：如果每个记录的差别很大，就会造成大量缺点：如果每个记录的差别很大，就会造成大量空间的浪费。空间的浪费。空间的浪费。空间的浪费。 9/3/2024

29、9/3/20242525 例如图 6.4 的字节串表示形式可以用图 6.6 的预留空间技术实现。该方法一般在大多数记录的长度接近最大长度时才使用，否则使用时空间浪费很大。SnumCnumScoreCnumScoreCnumScoreS003160280340S001283S005480S004185260S006375S002285 图6.6 变长记录的预留空间表示形式9/3/20249/3/202426262.2.指针技术指针技术 n n解决记录长度差很大的方法，省去过多的解决记录长度差很大的方法，省去过多的空间浪费。空间浪费。n n每个定长记录后面增加指针指向在上一方每个定长记录后面增加指

30、针指向在上一方法中可以合并为同一记录的其他记录。法中可以合并为同一记录的其他记录。n n被指向的整体成为溢出块。被指向的整体成为溢出块。 9/3/20249/3/20242727图图图图6.7 6.7 变长记录的指针表示方式变长记录的指针表示方式变长记录的指针表示方式变长记录的指针表示方式 9/3/20249/3/20242828图图图图6.8 6.8 固定块和溢出块结构固定块和溢出块结构固定块和溢出块结构固定块和溢出块结构 9/3/20249/3/202429296.3 文件结构文件结构n n文件中记录的组织方式有文件中记录的组织方式有无序件、有序文件、无序件、有序文件、聚集文件聚集文件和和

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

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

33、志位置时，将此记录的标志位置“ “1”, 1”, 以后查找记录时跳以后查找记录时跳以后查找记录时跳以后查找记录时跳过有该标志的记录。过有该标志的记录。过有该标志的记录。过有该标志的记录。（）常用于定长记录文件，删除一个记录时，总是（）常用于定长记录文件，删除一个记录时，总是（）常用于定长记录文件，删除一个记录时，总是（）常用于定长记录文件，删除一个记录时，总是把文件末尾记录移到被删记录位置。把文件末尾记录移到被删记录位置。把文件末尾记录移到被删记录位置。把文件末尾记录移到被删记录位置。 9/3/20249/3/202431316.3.2 6.3.2 有序文件有序文件有序文件有序文件n n有序文

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

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

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

37、就插入到溢出块中。n n在初始的时候，可以保持无力顺序和查找键的顺序在初始的时候，可以保持无力顺序和查找键的顺序在初始的时候，可以保持无力顺序和查找键的顺序在初始的时候，可以保持无力顺序和查找键的顺序一致，以提高速度，若多次操作后变化很大，有必一致，以提高速度，若多次操作后变化很大，有必一致，以提高速度，若多次操作后变化很大，有必一致，以提高速度，若多次操作后变化很大，有必要重新组织一次。要重新组织一次。要重新组织一次。要重新组织一次。9/3/20249/3/202434346.3.3 聚集文件聚集文件n n文件允许一个文件有多个关系的记录组成，文件允许一个文件有多个关系的记录组成，即记录类型

38、文件。即记录类型文件。例：可以把有关一个人的全部记录信息放在例：可以把有关一个人的全部记录信息放在相邻的位置，按人查找信息时就会很方便。相邻的位置，按人查找信息时就会很方便。9/3/20249/3/20243535图图图图6.106.10 插入一个记录后的顺序文件插入一个记录后的顺序文件插入一个记录后的顺序文件插入一个记录后的顺序文件 9/3/20249/3/20243636图图图图6.116.11 聚集文件例子聚集文件例子聚集文件例子聚集文件例子 9/3/20249/3/202437376.3.4 HASH 文件文件n n哈哈哈哈稀稀稀稀 (HASH) (HASH) 文文文文件件件件又又又又

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

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

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

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

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

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

45、SH 方法方法和和可扩展的可扩展的 HASH 方法方法n n评价评价：散列方法必须选取恰当的散列函数。：散列方法必须选取恰当的散列函数。9/3/20249/3/20244343 图图图图6.136.136.136.13 HASHHASH桶目录示例桶目录示例桶目录示例桶目录示例 9/3/20249/3/202444441.1.简单简单简单简单 HASH HASH 方法。方法。方法。方法。 n n该方法采用固定个数的该方法采用固定个数的该方法采用固定个数的该方法采用固定个数的 HASH HASH 桶，即把文件划分桶，即把文件划分桶，即把文件划分桶，即把文件划分为为为为 N N 个个个个HASHHA

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

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

48、或减少的。 9/3/20249/3/20244646 图图图图6.14 6.14 6.14 6.14 动态动态动态动态HASHHASH方法结构方法结构方法结构方法结构 9/3/20249/3/202447473.3.3.3.可扩展的可扩展的可扩展的可扩展的 HASH HASH HASH HASH 方法方法方法方法 n n特点：特点：特点：特点： 按照实际需要申请或释放空间。按照实际需要申请或释放空间。按照实际需要申请或释放空间。按照实际需要申请或释放空间。n n查找：查找：查找：查找： 求出求出求出求出h(Kih(Ki) )前前前前i i位值位值位值位值m,m,沿桶地指表位置沿桶地指表位置沿桶

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

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

51、多个指针。则桶地址表不用指向这个桶有多个指针。则桶地址表不用指向这个桶有多个指针。则桶地址表不用扩大只要分裂桶可以了。申请新的桶空间，原来扩大只要分裂桶可以了。申请新的桶空间，原来扩大只要分裂桶可以了。申请新的桶空间，原来扩大只要分裂桶可以了。申请新的桶空间，原来的桶分出后一半指针指向新的桶，从新分配分裂的桶分出后一半指针指向新的桶，从新分配分裂的桶分出后一半指针指向新的桶，从新分配分裂的桶分出后一半指针指向新的桶，从新分配分裂的桶中的记录。的桶中的记录。的桶中的记录。的桶中的记录。 9/3/20249/3/20245050n n删除：删除：删除：删除： 查找到查找到查找到查找到KiKi的记录

52、，从桶内删除。删除后如桶为的记录，从桶内删除。删除后如桶为的记录，从桶内删除。删除后如桶为的记录，从桶内删除。删除后如桶为空，桶也删除，还有可能引起桶地址的收缩。空，桶也删除，还有可能引起桶地址的收缩。空，桶也删除，还有可能引起桶地址的收缩。空，桶也删除，还有可能引起桶地址的收缩。n n显著优点：显著优点：显著优点：显著优点： 数据量增长后仍然保持由原有的操作和查询数据量增长后仍然保持由原有的操作和查询数据量增长后仍然保持由原有的操作和查询数据量增长后仍然保持由原有的操作和查询性能性能性能性能 空间开销达到最小空间开销达到最小空间开销达到最小空间开销达到最小 9/3/20249/3/20245

53、1516.4 索引技术索引技术 n n索引的组织方式主要有索引的组织方式主要有索引的组织方式主要有索引的组织方式主要有线性索引线性索引线性索引线性索引和和和和树形索引树形索引树形索引树形索引两类两类两类两类 。6.4.16.4.1线性索引线性索引线性索引线性索引n n线性索引可分为线性索引可分为线性索引可分为线性索引可分为稠密索引稠密索引稠密索引稠密索引和和和和稀疏索引稀疏索引稀疏索引稀疏索引两种。两种。两种。两种。1.1.稠密索引稠密索引稠密索引稠密索引 n n对主文件中每一个查找键值都建立一个索引记号对主文件中每一个查找键值都建立一个索引记号对主文件中每一个查找键值都建立一个索引记号对主文

54、件中每一个查找键值都建立一个索引记号 n n优点优点优点优点 : :查找、更新数据记录方便查找、更新数据记录方便查找、更新数据记录方便查找、更新数据记录方便, , 存取速度快存取速度快存取速度快存取速度快n n缺点缺点缺点缺点 : :索引项多索引项多索引项多索引项多, , 索引表大索引表大索引表大索引表大, , 空间代价空间代价空间代价空间代价大大大大 . . 9/3/20249/3/202452522.稀疏索引稀疏索引 n n只对主文件中若干查找键值建立一个索引记号。只对主文件中若干查找键值建立一个索引记号。只对主文件中若干查找键值建立一个索引记号。只对主文件中若干查找键值建立一个索引记号。

55、n n在插入操作较多的应用中采用稀疏索引方在插入操作较多的应用中采用稀疏索引方式是不太适宜的。式是不太适宜的。 9/3/20249/3/20245353K1K2K3KnA(RK1)A(RK2)A(RK3)A(RKn) 图6.16.索引结构 9/3/20249/3/20245454图图图图6.17 6.17 6.17 6.17 学生关系索引方式学生关系索引方式学生关系索引方式学生关系索引方式 9/3/20249/3/202455556.4.2 B6.4.2 B树树树树1.1.平衡树的概念平衡树的概念平衡树的概念平衡树的概念 mm阶平衡树或者为空，或者满足下面条件：阶平衡树或者为空，或者满足下面条

56、件：阶平衡树或者为空，或者满足下面条件：阶平衡树或者为空，或者满足下面条件：n n每个节点之多有每个节点之多有每个节点之多有每个节点之多有mm棵子树棵子树棵子树棵子树n n根节点或为叶结点，或至少有两棵子树根节点或为叶结点，或至少有两棵子树根节点或为叶结点，或至少有两棵子树根节点或为叶结点，或至少有两棵子树n n每个非叶结点至少有每个非叶结点至少有每个非叶结点至少有每个非叶结点至少有m/2m/2棵子树棵子树棵子树棵子树n n根结点到叶结点的每一条路径都有同样的长度，根结点到叶结点的每一条路径都有同样的长度，根结点到叶结点的每一条路径都有同样的长度，根结点到叶结点的每一条路径都有同样的长度，即叶

57、结点在同一层次上即叶结点在同一层次上即叶结点在同一层次上即叶结点在同一层次上 平衡树分为平衡树分为平衡树分为平衡树分为B+B+树树树树和和和和BB树树树树 9/3/20249/3/20245656图图图图6.18 6.18 6.18 6.18 多级索引多级索引多级索引多级索引 9/3/20249/3/20245757B B B B树树树树在上述定义基础上同时约定在上述定义基础上同时约定在上述定义基础上同时约定在上述定义基础上同时约定：n n除叶结点之外的所有其它结点的索引块最多可存除叶结点之外的所有其它结点的索引块最多可存除叶结点之外的所有其它结点的索引块最多可存除叶结点之外的所有其它结点的索

58、引块最多可存放放放放 m -1 m -1 m -1 m -1 个主码值和个主码值和个主码值和个主码值和 m m m m 个地址指针个地址指针个地址指针个地址指针。其格式为其格式为其格式为其格式为 : : : : n n叶结点上不包含数据记录本身叶结点上不包含数据记录本身叶结点上不包含数据记录本身叶结点上不包含数据记录本身，而是由记录索引项而是由记录索引项而是由记录索引项而是由记录索引项组成的记录索引块组成的记录索引块组成的记录索引块组成的记录索引块，每个记录索引每个记录索引每个记录索引每个记录索引 项包含有主码项包含有主码项包含有主码项包含有主码值和地址指针值和地址指针值和地址指针值和地址指针

59、。 P P0 0K K1 1P P1 1K K2 2P P2 2K Km-1m-1P Pm-1m-19/3/20249/3/20245858n n一般假设一般假设，每一个索引块能容纳的每一个索引块能容纳的索索引项数引项数是个奇数是个奇数，且且 m=2d-1 3; m=2d-1 3; 每一个记录每一个记录索索引块引块能容纳的记录索引项也是个奇数能容纳的记录索引项也是个奇数，且且n=2e-13。 9/3/20249/3/20245959图图图图6.19 6.19 6.19 6.19 多级索引的多级索引的多级索引的多级索引的B B B B 树树树树 9/3/20249/3/202460606.4.3

60、 B+ 6.4.3 B+ 树树树树1 1结构结构结构结构n n每个结点之多有每个结点之多有每个结点之多有每个结点之多有m-1m-1各查找键各查找键各查找键各查找键KiKi，mm个指针个指针个指针个指针Pi;Pi;如上图。如上图。如上图。如上图。P1P1K1K1P2P2.Pn-1Pn-1Kn-Kn-1 1PnPn9/3/20249/3/20246161n n叶结点：叶结点：叶结点：叶结点：叶结点的指针指向主文件的记录；查找键在叶结点的指针指向主文件的记录；查找键在叶结点的指针指向主文件的记录；查找键在叶结点的指针指向主文件的记录；查找键在 m-1/2m-1m-1/2m-1之间；叶结点最后的指针指

61、向之间；叶结点最后的指针指向之间；叶结点最后的指针指向之间；叶结点最后的指针指向下一叶结点。下一叶结点。下一叶结点。下一叶结点。n n非叶结点：非叶结点：非叶结点：非叶结点：组成多级稀疏索引，指针在组成多级稀疏索引，指针在组成多级稀疏索引，指针在组成多级稀疏索引，指针在 m/2mm/2m之间之间之间之间，指针，指针，指针，指针PiPi指向所有查找键大于等于指向所有查找键大于等于指向所有查找键大于等于指向所有查找键大于等于KiKi-1,-1,小于小于小于小于KiKi。 9/3/20249/3/20246262图图图图20 20 B+B+树的模型树的模型树的模型树的模型 9/3/20249/3/2

62、0246363 图图图图6.21 6.21 图图图图6.196.19中的树的树中的树的树中的树的树中的树的树9/3/20249/3/20246464n n查询：查询：查询：查询： 方法：方法：方法：方法：先找第一个大于先找第一个大于先找第一个大于先找第一个大于k k的查找键值，沿其左面的查找键值，沿其左面的查找键值，沿其左面的查找键值，沿其左面的指针到达下一层，以此查找下去。的指针到达下一层，以此查找下去。的指针到达下一层，以此查找下去。的指针到达下一层，以此查找下去。 特点：特点：特点：特点：查询的层数相同为树的高度，因为都是在查询的层数相同为树的高度，因为都是在查询的层数相同为树的高度，因

63、为都是在查询的层数相同为树的高度，因为都是在叶结点链接主文件。叶结点链接主文件。叶结点链接主文件。叶结点链接主文件。9/3/20249/3/202465652 2修改操作：修改操作：修改操作：修改操作：n n不引起索引结点分裂的插入不引起索引结点分裂的插入不引起索引结点分裂的插入不引起索引结点分裂的插入 若以在叶结点出现，直接插入记录；若以在叶结点出现，直接插入记录；若以在叶结点出现，直接插入记录；若以在叶结点出现，直接插入记录； 否则，找到第一个大于的查找键值，在其否则，找到第一个大于的查找键值，在其否则，找到第一个大于的查找键值，在其否则，找到第一个大于的查找键值，在其前面插入，其后的都向

64、后移。前面插入，其后的都向后移。前面插入，其后的都向后移。前面插入，其后的都向后移。9/3/20249/3/20246666n n不引起索引结点合并的删除不引起索引结点合并的删除不引起索引结点合并的删除不引起索引结点合并的删除; ; 查找到主文件，删除记录；查找到主文件，删除记录；查找到主文件，删除记录；查找到主文件，删除记录； 若主文件中还有同查找键的记录不修改索引；若主文件中还有同查找键的记录不修改索引；若主文件中还有同查找键的记录不修改索引；若主文件中还有同查找键的记录不修改索引； 若无，从叶结点中删除相应的键值和指针。若无，从叶结点中删除相应的键值和指针。若无，从叶结点中删除相应的键值

65、和指针。若无，从叶结点中删除相应的键值和指针。n n引起分裂的插入引起分裂的插入引起分裂的插入引起分裂的插入; ; 插入叶结点后，把多出来的分裂出去；修改父结插入叶结点后，把多出来的分裂出去；修改父结插入叶结点后，把多出来的分裂出去；修改父结插入叶结点后，把多出来的分裂出去；修改父结点，插入心结点中的最小值，同理其父结点进行点，插入心结点中的最小值，同理其父结点进行点，插入心结点中的最小值，同理其父结点进行点，插入心结点中的最小值，同理其父结点进行修改。修改。修改。修改。 9/3/20249/3/20246767图图图图6.22 6.22 在图在图在图在图6.216.21中插入值为中插入值为中

66、插入值为中插入值为4141数据记录后的树数据记录后的树数据记录后的树数据记录后的树 9/3/20249/3/20246868n n引起合并的删除引起合并的删除引起合并的删除引起合并的删除 在删除叶结点后，引起结点不符合定义，将被在删除叶结点后，引起结点不符合定义，将被在删除叶结点后，引起结点不符合定义，将被在删除叶结点后，引起结点不符合定义，将被删除，若父结点中有也将删除，导致合并的发删除，若父结点中有也将删除，导致合并的发删除，若父结点中有也将删除，导致合并的发删除，若父结点中有也将删除，导致合并的发生。生。生。生。uuB+ B+ 树的性能分析树的性能分析树的性能分析树的性能分析n n显著优

67、点显著优点显著优点显著优点 ： 搜索代价较小搜索代价较小搜索代价较小搜索代价较小 ； 解决了数据记录在插入，删除和未解决了数据记录在插入，删除和未解决了数据记录在插入，删除和未解决了数据记录在插入，删除和未用回收等存储组织问题用回收等存储组织问题用回收等存储组织问题用回收等存储组织问题 。9/3/20249/3/20246969图图图图6.236.23 在图在图在图在图6.21 6.21 中删除主码值为中删除主码值为中删除主码值为中删除主码值为2626的数据记录后的树的数据记录后的树的数据记录后的树的数据记录后的树 9/3/20249/3/20247070小结小结n n 数数数数据据据据库库库

68、库是是是是数数数数据据据据的的的的有有有有序序序序集集集集合合合合，需需需需保保保保留留留留在在在在计计计计算算算算机机机机外外外外存存存存介介介介质质质质上上上上反反反反复复复复应应应应用用用用。由由由由于于于于实实实实际际际际应应应应用用用用系系系系统统统统数数数数据据据据规规规规模模模模都都都都很很很很庞庞庞庞大大大大, ,加加加加之之之之经经经经常常常常要要要要从从从从数数数数据据据据集集集集合合合合中中中中检检检检索索索索需需需需要要要要的的的的数数数数据据据据，所所所所以以以以数数数数据据据据组组组组织织织织的的的的方方方方式式式式，数数数数据据据据的的的的定定定定位位位位方方方方

69、式式式式，以以以以及及及及数数数数据据据据的维护策略的选取十分重要。的维护策略的选取十分重要。的维护策略的选取十分重要。的维护策略的选取十分重要。9/3/20249/3/20247171n n 在磁盘中在磁盘中在磁盘中在磁盘中, ,数据库以文件形式组织。文件组数据库以文件形式组织。文件组数据库以文件形式组织。文件组数据库以文件形式组织。文件组织有两种方法织有两种方法织有两种方法织有两种方法：一种是把记录设计成定长格式一种是把记录设计成定长格式一种是把记录设计成定长格式一种是把记录设计成定长格式, ,也也也也就是每个文件只存储某一确定长度的记录就是每个文件只存储某一确定长度的记录就是每个文件只存

70、储某一确定长度的记录就是每个文件只存储某一确定长度的记录；另一另一另一另一种是变长格式种是变长格式种是变长格式种是变长格式, ,使之能存放不同长度的记录。实现使之能存放不同长度的记录。实现使之能存放不同长度的记录。实现使之能存放不同长度的记录。实现变长记录的技变长记录的技变长记录的技变长记录的技术术术术有多种有多种有多种有多种, ,包括分槽式页结构、指针包括分槽式页结构、指针包括分槽式页结构、指针包括分槽式页结构、指针方法和保留空间等方法方法和保留空间等方法方法和保留空间等方法方法和保留空间等方法。9/3/20249/3/20247272小结小结n n 文文文文件件件件结结结结构构构构有有有有

71、堆堆堆堆文文文文件件件件、顺顺顺顺序序序序文文文文件件件件、散散散散列列列列文文文文件件件件和和和和聚聚聚聚集集集集文文文文件件件件等等等等四四四四种种种种。为为为为了了了了提提提提高高高高查查查查找找找找速速速速度度度度, , , ,可可可可以以以以为为为为文文文文件件件件建建建建立索引或散列机制立索引或散列机制立索引或散列机制立索引或散列机制。n n 索引有稠密索引、稀疏索引和多级索引等形式。索引有稠密索引、稀疏索引和多级索引等形式。索引有稠密索引、稀疏索引和多级索引等形式。索引有稠密索引、稀疏索引和多级索引等形式。索引顺序文件组织的主要缺陷是随着文件的增大索引顺序文件组织的主要缺陷是随着

72、文件的增大索引顺序文件组织的主要缺陷是随着文件的增大索引顺序文件组织的主要缺陷是随着文件的增大, , , ,性能会下降。为了克服这个缺陷性能会下降。为了克服这个缺陷性能会下降。为了克服这个缺陷性能会下降。为了克服这个缺陷, , , ,可以使用可以使用可以使用可以使用B B B B、B+B+B+B+树树树树索引索引索引索引。B+B+B+B+树索引是平衡树树索引是平衡树树索引是平衡树树索引是平衡树, , , ,即从树根到树叶所有路即从树根到树叶所有路即从树根到树叶所有路即从树根到树叶所有路径长度相等。这种查找是简单有效的径长度相等。这种查找是简单有效的径长度相等。这种查找是简单有效的径长度相等。这

73、种查找是简单有效的, , , ,但插入和删但插入和删但插入和删但插入和删除比较复杂。除比较复杂。除比较复杂。除比较复杂。B B B B树索引和树索引和树索引和树索引和B+B+B+B+树索引类似。树索引类似。树索引类似。树索引类似。9/3/20249/3/20247373小结小结n n B B树的主要优点在于它去除了查找键值树的主要优点在于它去除了查找键值存储中的冗余存储中的冗余; ;主要缺陷在于整体的复杂性主要缺陷在于整体的复杂性以及结点大小给定时减少了扇出以及结点大小给定时减少了扇出。实际应实际应用中用中, ,人们总是更愿意使用人们总是更愿意使用B+B+树索引树索引。9/3/20249/3/

74、20247474小结小结n n 顺顺顺顺序序序序文文文文件件件件需需需需要要要要一一一一个个个个索索索索引引引引结结结结构构构构来来来来定定定定位位位位数数数数据据据据。相相相相比比比比之之之之下下下下, , , ,基基基基于于于于散散散散列列列列的的的的文文文文件件件件允允允允许许许许通通通通过过过过散散散散列列列列函函函函数数数数直直直直接接接接得得得得到到到到记记记记录录录录所所所所在在在在的的的的桶桶桶桶地地地地址址址址。静静静静态态态态散散散散列列列列所所所所用用用用的的的的桶桶桶桶地地地地址址址址集集集集合合合合是是是是固固固固定定定定的的的的, , , ,不不不不容容容容易易易易

75、适适适适应应应应数数数数据据据据库库库库数数数数据据据据量量量量的的的的快快快快速速速速增增增增长长长长。可可可可扩扩扩扩充充充充散散散散列列列列结结结结构构构构是是是是一一一一种种种种允允允允许许许许修修修修改改改改散散散散列列列列函函函函数数数数的的的的动动动动态态态态散散散散列列列列技技技技术术术术, , , ,在在在在数数数数据据据据库库库库增增增增加加加加或或或或缩缩缩缩减减减减时时时时它它它它可可可可以以以以通通通通过过过过分分分分裂裂裂裂或合并桶来适应数据库大小的变化或合并桶来适应数据库大小的变化或合并桶来适应数据库大小的变化或合并桶来适应数据库大小的变化。9/3/20249/3

76、/20247575习题习题1. 1. 1. 1. 解释下列术语解释下列术语解释下列术语解释下列术语 : :n n(1) (1) 文件，记录，定长记录文件，变长记录文件，文件，记录，定长记录文件，变长记录文件，文件，记录，定长记录文件，变长记录文件，文件，记录，定长记录文件，变长记录文件，跨跨跨跨块记录，非跨块记录。块记录，非跨块记录。块记录，非跨块记录。块记录，非跨块记录。n n (2) (2) 有序索引，主索引，稠密索引，稀疏索引，有序索引，主索引，稠密索引，稀疏索引，有序索引，主索引，稠密索引，稀疏索引，有序索引，主索引，稠密索引，稀疏索引，多级索引，多级索引，多级索引，多级索引， B B

77、 树，树，树，树，B B+ + 树树树树n n2. 2.试叙述计算机系统的物理存储介质层次，并说试叙述计算机系统的物理存储介质层次，并说试叙述计算机系统的物理存储介质层次，并说试叙述计算机系统的物理存储介质层次，并说明每一种介质的数据访问速度。明每一种介质的数据访问速度。明每一种介质的数据访问速度。明每一种介质的数据访问速度。9/3/20249/3/20247676习题习题n n3. 3. 比较有序文件和无序文件的优缺点，什么情况比较有序文件和无序文件的优缺点，什么情况比较有序文件和无序文件的优缺点，什么情况比较有序文件和无序文件的优缺点，什么情况下应该使用有序文件，什么情况下应该使用无序下应

78、该使用有序文件，什么情况下应该使用无序下应该使用有序文件，什么情况下应该使用无序下应该使用有序文件，什么情况下应该使用无序文件。文件。文件。文件。n n4. 4. 回答下列问题回答下列问题回答下列问题回答下列问题 : :n n(1)HASH (1)HASH 文件的桶溢出问题是什么文件的桶溢出问题是什么文件的桶溢出问题是什么文件的桶溢出问题是什么 ? ? 如何解决如何解决如何解决如何解决 ? ?n n(2) (2) 简单简单简单简单 HASH HASH 文件、动态文件、动态文件、动态文件、动态 HASH HASH 文件和可扩文件和可扩文件和可扩文件和可扩展展展展 HASH HASH 文件之间有什

79、么文件之间有什么文件之间有什么文件之间有什么不同。不同。不同。不同。 9/3/20249/3/20247777习题习题n n5. 5. 在散列文件组织中在散列文件组织中在散列文件组织中在散列文件组织中，是什么原因引起桶溢出的是什么原因引起桶溢出的是什么原因引起桶溢出的是什么原因引起桶溢出的 ? ? 有什么办法能减少桶溢出的次数有什么办法能减少桶溢出的次数有什么办法能减少桶溢出的次数有什么办法能减少桶溢出的次数 ? ?n n6. 6. 试试试试举举举举一一一一个个个个数数数数据据据据库库库库应应应应用用用用例例例例子子子子，说说说说明明明明在在在在表表表表达达达达变变变变长长长长记记记记录录录录

80、时，有时指针形式比预留空间方法好。并作解释时，有时指针形式比预留空间方法好。并作解释时，有时指针形式比预留空间方法好。并作解释时，有时指针形式比预留空间方法好。并作解释。n n7.7.7.7. 设设设设查查查查找找找找键键键键值值值值集集集集为为为为 2,3,5,7,11,17,19,23,29,312,3,5,7,11,17,19,23,29,31。假假假假设设设设初初初初始始始始时时时时 B+ B+ 树树树树为为为为空空空空，按按按按升升升升序序序序次次次次序序序序插插插插入入入入键键键键值值值值。就就就就下面三种情况建立三棵下面三种情况建立三棵下面三种情况建立三棵下面三种情况建立三棵 B+ B+ 树树树树 : :n n 4 4 阶阶阶阶; ; 6 6 阶阶阶阶; ; 8 8 阶。阶。阶。阶。9/3/20249/3/20247878