1、第第7 7章章 数据库的物理组织数据库的物理组织 版权所有(C)-南京大学计算机科学与技术系7.1 概论概论7.2 数据库的物理存储介质数据库的物理存储介质7.3 磁盘存储器及其结构磁盘存储器及其结构7.4 文件组织文件组织7.5 文件记录组织文件记录组织7.6 索引技术与散列技术索引技术与散列技术7.7 数据库与文件数据库与文件版权所有(C)-南京大学计算机科学与技术系7.1 概论概论 研究目的研究目的 提高存储效率，加快存取速度提高存储效率，加快存取速度 研究内容研究内容 磁盘的物理结构磁盘的物理结构 文件的组织与设计文件的组织与设计 主要技术主要技术 索引技术索引技术 散列技术散列技术版
2、权所有(C)-南京大学计算机科学与技术系7.1 概论概论7.2 数据库的物理存储介质数据库的物理存储介质7.3 磁盘存储器及其结构磁盘存储器及其结构7.4 文件组织文件组织7.5 文件记录组织文件记录组织7.6 索引技术与散列技术索引技术与散列技术7.7 数据库与文件数据库与文件版权所有(C)-南京大学计算机科学与技术系 三级存储器结构三级存储器结构 第一级：第一级：主存储器主存储器(main memory)包括：包括：磁带存储器磁带存储器 自动光盘机自动光盘机 是一种辅助存储设备，也称三级存储器是一种辅助存储设备，也称三级存储器 包括包括：高速缓冲存储器高速缓冲存储器(cache)主存储器主
3、存储器(memory)7.2 数据库的物理存储介质数据库的物理存储介质 第二级：第二级：磁盘存储器磁盘存储器(secondary storage)第三级：第三级：辅助存储器辅助存储器(tertiary storage)也称为：二级存储器也称为：二级存储器 或或 次级存储器次级存储器版权所有(C)-南京大学计算机科学与技术系7.2 数据库的物理存储介质数据库的物理存储介质存储容量存储容量访问速度访问速度访问访问类型类型存取存取单位单位第一级第一级存储器存储器100MB10GB10-8秒秒10-7 秒秒随机随机字节字节第二级第二级存储器存储器10GB103GB10毫秒毫秒30 毫秒毫秒随机随机磁盘
4、块磁盘块第三级第三级存储器存储器106GB几秒钟几秒钟几分钟几分钟顺序顺序数据块数据块版权所有(C)-南京大学计算机科学与技术系7.2 数据库的物理存储介质数据库的物理存储介质主存储器主存储器磁盘存储器磁盘存储器辅助存储器辅助存储器cachememorytapeCDdisk存储存储容量容量小小大大访问访问速度速度快快慢慢制造制造成本成本高高低低版权所有(C)-南京大学计算机科学与技术系7.1 概论概论7.2 数据库的物理存储介质数据库的物理存储介质7.3 磁盘存储器及其结构磁盘存储器及其结构7.4 文件组织文件组织7.5 文件记录组织文件记录组织7.6 索引技术与散列技术索引技术与散列技术7.
5、7 数据库与文件数据库与文件版权所有(C)-南京大学计算机科学与技术系7.3 磁盘存储器及其结构磁盘存储器及其结构磁盘存储器磁盘存储器 一种大容量、可以直接存取的外部存储设备。一种大容量、可以直接存取的外部存储设备。v大容量：大容量：10GB 1000GBv直接存取：可以随机到达磁盘上的任何直接存取：可以随机到达磁盘上的任何一个部位存取数据。一个部位存取数据。磁盘存储器的组成磁盘存储器的组成 磁盘盘片磁盘盘片 磁盘驱动器磁盘驱动器版权所有(C)-南京大学计算机科学与技术系7.3 磁盘存储器及其结构磁盘存储器及其结构1.磁盘盘片磁盘盘片 盘片分上下两面盘片分上下两面 每一面又被划分成若干每一面又
6、被划分成若干个磁道个磁道(Track)每个磁道是一个由两个每个磁道是一个由两个半径不等的同心圆所构半径不等的同心圆所构成的区域成的区域 每个磁道又分为若干个每个磁道又分为若干个等长的扇区等长的扇区(Sector)，它又称磁盘块它又称磁盘块(Block)磁盘块是磁盘与内存进磁盘块是磁盘与内存进行数据交换的基本单位行数据交换的基本单位磁磁道道轴轴磁盘块磁盘块版权所有(C)-南京大学计算机科学与技术系7.3 磁盘存储器及其结构磁盘存储器及其结构 一个磁盘存储器往往由若干个盘片一个磁盘存储器往往由若干个盘片组成一个盘片组，固定在同一个主组成一个盘片组，固定在同一个主轴上。轴上。由具有相同半径的若干个磁
7、道可以由具有相同半径的若干个磁道可以构成个无形的同心圆柱体，我们构成个无形的同心圆柱体，我们称其为柱面称其为柱面(Cylinder)。磁盘盘片的每一面有多少条磁道，磁盘盘片的每一面有多少条磁道，该磁盘存储器就有多少个柱面。该磁盘存储器就有多少个柱面。柱面柱面磁道磁道磁盘轴磁盘轴版权所有(C)-南京大学计算机科学与技术系7.3 磁盘存储器及其结构磁盘存储器及其结构2.磁盘驱动器磁盘驱动器 磁盘驱动器由活动臂和读写磁盘驱动器由活动臂和读写头组成。头组成。每个盘片有两个活动臂，分每个盘片有两个活动臂，分别对应上、下两面，每个活别对应上、下两面，每个活动臂的尽头有一个读动臂的尽头有一个读/写头写头（或
8、称磁头），用它可以读（或称磁头），用它可以读取取/写盘片中的数据。写盘片中的数据。所有的活动臂都被固定在同所有的活动臂都被固定在同一个活动臂组合件上，并可一个活动臂组合件上，并可以通过移动活动臂组合件来以通过移动活动臂组合件来使固定在活动臂上的磁头在使固定在活动臂上的磁头在不同的磁道之间移动，从而不同的磁道之间移动，从而完成对于柱面的定位操作。完成对于柱面的定位操作。旋转活动臂活动臂磁道磁道柱面柱面轴轴磁头磁头活活动动臂臂组组合合件件版权所有(C)-南京大学计算机科学与技术系7.3 磁盘存储器及其结构磁盘存储器及其结构3.磁盘存储器磁盘存储器 一个磁盘存储器是由盘片组以及磁盘驱动器所组成一个磁
9、盘存储器是由盘片组以及磁盘驱动器所组成的的，其中盘片组以轴为核心作不间断的旋转，而活其中盘片组以轴为核心作不间断的旋转，而活动臂组合件则以柱面为单位做前进或后退操作。动臂组合件则以柱面为单位做前进或后退操作。磁盘块（扇区）的定位操作磁盘块（扇区）的定位操作v选择柱面选择柱面：通过移动活动臂组合件来进行定位：通过移动活动臂组合件来进行定位v选择磁道选择磁道：选择活动臂（读：选择活动臂（读/写头）写头）v选择磁盘块选择磁盘块：根据盘片组的旋转定位。：根据盘片组的旋转定位。因此，每个磁盘块的物理地址由三个部分组成：因此，每个磁盘块的物理地址由三个部分组成：柱面号柱面号+磁道号磁道号+磁盘块号磁盘块号
10、版权所有(C)-南京大学计算机科学与技术系7.3 磁盘存储器及其结构磁盘存储器及其结构4.磁盘存储器的磁盘存储器的I/O操作操作 编码方式编码方式：设一个磁盘存储器有：设一个磁盘存储器有n个柱面，每个柱面个柱面，每个柱面有有m个磁道，每个磁道有个磁道，每个磁道有r个磁盘块。则编码规则如下：个磁盘块。则编码规则如下：v柱面号柱面号：由外层到内层分别为（：由外层到内层分别为（0号柱面，号柱面，1号柱号柱面，面，n-1号柱面）号柱面）v磁道号磁道号：每个柱面中的磁道从上到下分别为（：每个柱面中的磁道从上到下分别为（0号号磁道，磁道，1号磁道，号磁道，m-1号磁道）号磁道）v磁盘块号磁盘块号：每个磁道
11、中的磁盘块按照旋转的方向：每个磁道中的磁盘块按照旋转的方向分别为（分别为（0号磁盘块，号磁盘块，1号磁盘块，号磁盘块，r-1号磁号磁盘块）盘块）因此，该磁盘存储器中共有因此，该磁盘存储器中共有m*n*r个磁盘块，其中个磁盘块，其中x号号柱面的柱面的y号磁道的号磁道的z号磁盘块的编号是：号磁盘块的编号是：x m r +y r +z版权所有(C)-南京大学计算机科学与技术系7.3 磁盘存储器及其结构磁盘存储器及其结构4.磁盘存储器的磁盘存储器的I/O操作操作（续）（续）磁盘的格式化磁盘的格式化在每个磁盘块的头部写入：在每个磁盘块的头部写入：该磁盘块的地址，包括：柱面号，磁道号该磁盘块的地址，包括：
12、柱面号，磁道号（读（读/写头号），磁盘块号写头号），磁盘块号 有关该磁盘块的状态信息有关该磁盘块的状态信息在同一个磁道的相邻磁盘块之间会留有一定的空在同一个磁道的相邻磁盘块之间会留有一定的空隙，以利于对相邻磁盘块的顺序访问。隙，以利于对相邻磁盘块的顺序访问。磁盘的磁盘的I/O操作：首先根据给出的磁盘块地址定位，操作：首先根据给出的磁盘块地址定位，然后读然后读/写指定磁盘块上的数据，其时间开销是：写指定磁盘块上的数据，其时间开销是：活动臂组合件的移动时间活动臂组合件的移动时间 磁盘片的旋转定位时间磁盘片的旋转定位时间 读读/写数据时间写数据时间版权所有(C)-南京大学计算机科学与技术系7.1 概
13、论概论7.2 数据库的物理存储介质数据库的物理存储介质7.3 磁盘存储器及其结构磁盘存储器及其结构7.4 文件组织文件组织7.5 文件记录组织文件记录组织7.6 索引技术与散列技术索引技术与散列技术7.7 数据库与文件数据库与文件版权所有(C)-南京大学计算机科学与技术系7.4 文件组织文件组织 数据库中的数据被组织成若干个数据文件数据库中的数据被组织成若干个数据文件 文件是记录的集合，记录是项的集合。文件是记录的集合，记录是项的集合。v记录的记录的 型型 与与 值值 一个记录中所含有的项的描述信息被称为记录的型一个记录中所含有的项的描述信息被称为记录的型 记录值则是符合记录型要求的项值的集合
14、，通常也记录值则是符合记录型要求的项值的集合，通常也简称为记录简称为记录v记录记录是文件中的一个逻辑单位，在实现时是文件中的一个逻辑单位，在实现时记录记录必须被分配存储到具体磁盘块中去，从而构成一条物必须被分配存储到具体磁盘块中去，从而构成一条物理记录（通常也简称为记录）理记录（通常也简称为记录）v记录的大小往往与磁盘块的大小不一致，因此记录在记录的大小往往与磁盘块的大小不一致，因此记录在磁盘块上的存储可以有多种方式。磁盘块上的存储可以有多种方式。版权所有(C)-南京大学计算机科学与技术系7.4 文件组织文件组织 记录在磁盘块中的分配方式记录在磁盘块中的分配方式 单块单记录单块单记录记记 录录
15、无用部分无用部分 单块多记录单块多记录记录记录1记录记录2记录记录n特点：在上述两种存储方式中，记录不能跨块存储，都存特点：在上述两种存储方式中，记录不能跨块存储，都存在存储空间浪费现象。在存储空间浪费现象。版权所有(C)-南京大学计算机科学与技术系7.4 文件组织文件组织 记录在磁盘块中的分配方式记录在磁盘块中的分配方式（续）（续）特点：在上述两种存储方式中，允许记录跨块存储。在多特点：在上述两种存储方式中，允许记录跨块存储。在多块单记录方式下仍然有空间浪费现象，在多块多记块单记录方式下仍然有空间浪费现象，在多块多记录方式中则不存在空间浪费现象。录方式中则不存在空间浪费现象。多块单记录多块单
16、记录记记 录录 1无用部分无用部分记记 录录 1 多块多记录多块多记录R1R2RkRkRn空闲部分空闲部分版权所有(C)-南京大学计算机科学与技术系7.4 文件组织文件组织不同类型的应用可以采用不同的记录分配方式。不同类型的应用可以采用不同的记录分配方式。较常用的有两种方式：较常用的有两种方式：单块多记录单块多记录v当记录的长度远远小于磁盘块的大小时当记录的长度远远小于磁盘块的大小时 多块单记录多块单记录v当记录的长度接近或大于磁盘块的大小时当记录的长度接近或大于磁盘块的大小时版权所有(C)-南京大学计算机科学与技术系7.4 文件组织文件组织 磁盘块在磁盘上的分配磁盘块在磁盘上的分配数据库系统
17、使用的磁盘块有两种申请与使用方式：数据库系统使用的磁盘块有两种申请与使用方式：1.由文件系统负责磁盘块的申请与与分配由文件系统负责磁盘块的申请与与分配采用文件系统中的数据文件来负责数据库中数据采用文件系统中的数据文件来负责数据库中数据的存储，文件所需要的磁盘空间由文件系统来申的存储，文件所需要的磁盘空间由文件系统来申请和分配使用。请和分配使用。在此种方式下不存在真正意义上的磁盘管理。在此种方式下不存在真正意义上的磁盘管理。2.由由DBMS负责磁盘块的申请申请与分配负责磁盘块的申请申请与分配DBMS在一开始就申请所有供数据库系统使用的在一开始就申请所有供数据库系统使用的磁盘块，并负责这些磁盘块的
18、分配与使用管理。磁盘块，并负责这些磁盘块的分配与使用管理。版权所有(C)-南京大学计算机科学与技术系7.4 文件组织文件组织 常用的磁盘块的分配方式常用的磁盘块的分配方式分配方式分配方式优点优点缺点缺点连续分配法连续分配法按连续物理地址分配按连续物理地址分配有利于文件的有利于文件的顺序访问顺序访问无法扩充文件无法扩充文件所使用的存储所使用的存储空间空间链接分配法链接分配法随机分配，磁盘块之随机分配，磁盘块之间通过指针链接在一间通过指针链接在一起起存取效率较差存取效率较差有利于文件存有利于文件存储空间的扩充储空间的扩充索引分配法索引分配法通过一个逻辑块号与通过一个逻辑块号与磁盘块地址之间的索磁盘
19、块地址之间的索引来维护所使用的磁引来维护所使用的磁盘块盘块空间的使用较空间的使用较灵活灵活索引文件需要索引文件需要额外的存储空额外的存储空间间集簇分配法集簇分配法局部是物理上连续的，局部是物理上连续的，又可以通过指针链接又可以通过指针链接新的磁盘块新的磁盘块综合了连续分综合了连续分配法和链接分配法和链接分配法的优点配法的优点版权所有(C)-南京大学计算机科学与技术系7.4 文件组织文件组织 文件中的定长记录与变长记录文件中的定长记录与变长记录 在数据库系统中，文件中的记录有定长与变长两种在数据库系统中，文件中的记录有定长与变长两种组织方式。组织方式。v定长记录定长记录：所有属性值都是定长的，即
20、占用固：所有属性值都是定长的，即占用固定大小的存储空间。定大小的存储空间。v变长记录变长记录：记录占用的存储空间是不断变化的。：记录占用的存储空间是不断变化的。变长记录的组织方式主要适合于下述几种情况：变长记录的组织方式主要适合于下述几种情况：数据项所占用的存储空间大小变化较大数据项所占用的存储空间大小变化较大 含有需要重复存储的字段值含有需要重复存储的字段值 含有数据量极大的字段值含有数据量极大的字段值 含有可变格式的记录含有可变格式的记录版权所有(C)-南京大学计算机科学与技术系7.1 概论概论7.2 数据库的物理存储介质数据库的物理存储介质7.3 磁盘存储器及其结构磁盘存储器及其结构7.
21、4 文件组织文件组织7.5 文件记录组织文件记录组织7.6 索引技术与散列技术索引技术与散列技术7.7 数据库与文件数据库与文件版权所有(C)-南京大学计算机科学与技术系7.5 文件记录组织文件记录组织 堆文件组织堆文件组织(Heap file)记录可以放在文件的任何位置上，一般以记录录入记录可以放在文件的任何位置上，一般以记录录入时间先后为序组织存储。时间先后为序组织存储。顺序文件组织顺序文件组织(Sequential file)记录是按其项值的升序或降序存储的。记录是按其项值的升序或降序存储的。散列文件组织散列文件组织(Hashing file)根据记录中的某个项值通过散列函数求得的值作为
22、根据记录中的某个项值通过散列函数求得的值作为记录的存储地址记录的存储地址 聚集文件组织聚集文件组织(Clustering file)一个文件可以存储多个关系的记录，不同关系中有一个文件可以存储多个关系的记录，不同关系中有联系的记录存储在一起可以提高查找速度。联系的记录存储在一起可以提高查找速度。版权所有(C)-南京大学计算机科学与技术系7.1 概论概论7.2 数据库的物理存储介质数据库的物理存储介质7.3 磁盘存储器及其结构磁盘存储器及其结构7.4 文件组织文件组织7.5 文件记录组织文件记录组织7.6 索引技术与散列技术索引技术与散列技术7.7 数据库与文件数据库与文件版权所有(C)-南京大
23、学计算机科学与技术系7.6 索引技术与散列技术索引技术与散列技术 在数据库中数据查找的速度是至关重要的，但是当数据在数据库中数据查找的速度是至关重要的，但是当数据库中数据量增大时，数据查找速度就会受到影响，当数库中数据量增大时，数据查找速度就会受到影响，当数据量极大时，查找速度将会受到严重影响，为解决此问据量极大时，查找速度将会受到严重影响，为解决此问题需引入题需引入“索引技术索引技术”与与“散列技术散列技术”。内容内容 顺序文件顺序文件 索引文件索引文件v在顺序文件上的索引技术在顺序文件上的索引技术 稠密索引、稀疏索引、多级索引稠密索引、稀疏索引、多级索引v非顺序文件中的索引技术非顺序文件中
24、的索引技术v多维索引多维索引 B/B+树文件树文件 HASH文件文件版权所有(C)-南京大学计算机科学与技术系7.6 索引技术与散列技术索引技术与散列技术一、顺序文件一、顺序文件 按照某个属性按照某个属性(项项)的取值进行排序而构成的数据文的取值进行排序而构成的数据文件被称为件被称为顺序文件顺序文件。例（例（假设每个磁盘块可以存放假设每个磁盘块可以存放2条记录条记录）1 记记录录 1 2 记记录录 2 3 记记录录 3 4 记记录录 4 5 记记录录 5 6 记记录录 6 第第 1 个个磁磁盘盘块块 第第 2 个个磁磁盘盘块块 第第 3 个个磁磁盘盘块块 主主关关键键字字值值 版权所有(C)-
25、南京大学计算机科学与技术系7.6 索引技术与散列技术索引技术与散列技术-顺序文件（续）顺序文件（续）例例11 设一个关系有设一个关系有10106 6个元组，在每个磁盘块（大小为个元组，在每个磁盘块（大小为4 4KBKB）中可存放中可存放1010个这样的元组，则该关系大约占个这样的元组，则该关系大约占用：用：10105 5个磁盘块（约个磁盘块（约400400MBMB）设该关系中的元组已经按照主关键字值从小到大的设该关系中的元组已经按照主关键字值从小到大的顺序构成了一个顺序文件，因此可以采用二分查找顺序构成了一个顺序文件，因此可以采用二分查找法来根据主关键字值进行记录定位。法来根据主关键字值进行记
26、录定位。按照一个主关键字值进行记录定位所需要的磁盘按照一个主关键字值进行记录定位所需要的磁盘I/OI/O次数为：次数为：loglog2 210105 5 16.6 16.6 1717版权所有(C)-南京大学计算机科学与技术系7.6 索引技术与散列技术索引技术与散列技术二、索引文件二、索引文件 建立索引文件的目的：以记录的特征值（通常是一建立索引文件的目的：以记录的特征值（通常是一个或多个字段的值）为输入，能够快速地找出具有个或多个字段的值）为输入，能够快速地找出具有该特征的记录。该特征的记录。利用索引文件进行记录查找的过程：首先在索引文利用索引文件进行记录查找的过程：首先在索引文件中按照特征字
27、段的值进行查找，找出具有该特征件中按照特征字段的值进行查找，找出具有该特征的记录的记录指针（即记录在数据文件中的存储地的记录的记录指针（即记录在数据文件中的存储地址），从而可以在数据文件中进行直接定位，读出址），从而可以在数据文件中进行直接定位，读出所需要的记录。所需要的记录。索引关键字值索引文件符合条件的记录所在的数据文件磁盘块符合条件的记录利利用用索索引引文文件件访访问问数数据据文文件件中中的的记记录录的的示示意意图图 版权所有(C)-南京大学计算机科学与技术系7.6 索引技术与散列技术索引技术与散列技术-索引文件（续）索引文件（续）通过建立索引文件可以大大提高在数据文件上的记录查找通过建
28、立索引文件可以大大提高在数据文件上的记录查找定位速度。定位速度。v索引文件的大小一般都大大小于数据文件的大小。索引文件的大小一般都大大小于数据文件的大小。索引文件主要用于记录的快速定位操作，在索引文索引文件主要用于记录的快速定位操作，在索引文件中一般只含有特征字段（即索引属性）上的值和件中一般只含有特征字段（即索引属性）上的值和记录指针。如：记录指针。如：v索引文件采用便于查找的特殊组织结构索引文件采用便于查找的特殊组织结构(如如B或或B+树树)。在不同类型的数据文件上我们可以建立不同的索引文件。在不同类型的数据文件上我们可以建立不同的索引文件。对应记录对应记录3的指针的指针属性值属性值3对应
29、记录对应记录2的指针的指针属性值属性值2对应记录对应记录1的指针的指针属性值属性值1版权所有(C)-南京大学计算机科学与技术系7.6 索引技术与散列技术索引技术与散列技术1.在顺序文件上的索引在顺序文件上的索引 稠密索引稠密索引 稀疏索引稀疏索引 多级索引多级索引v在讨论上述的三种索引文件时，我们假设其索在讨论上述的三种索引文件时，我们假设其索引属性的值具有唯一性。否则我们可以使用：引属性的值具有唯一性。否则我们可以使用：具有重复键值的索引具有重复键值的索引版权所有(C)-南京大学计算机科学与技术系7.6 索引技术与散列技术索引技术与散列技术 稠密索引稠密索引 索引文件索引文件v存放记录的关键
30、字值以及指向记录本身的指针存放记录的关键字值以及指向记录本身的指针(记录的存储地址记录的存储地址)，并且按照关键字值的顺序进，并且按照关键字值的顺序进行排序。行排序。v一个关键字值和一个记录指针构成的一个关键字值和一个记录指针构成的键键-指针指针对对我们称为一个我们称为一个索引项索引项:稠密索引稠密索引v如果数据文件中的每条记录在索引文件中都存在如果数据文件中的每条记录在索引文件中都存在一个相对应的索引项，则该索引被成为一个相对应的索引项，则该索引被成为稠密索引稠密索引。v例如：例如：关键字关键字K记录指针记录指针P版权所有(C)-南京大学计算机科学与技术系稠密索引稠密索引(续续)S#SNSD
31、SAS1LUCS18S2LICS17S3XUMA18S4LOCS18S5LINPH19S6WANGCS17S7SENMA17S8EHENPH18S#指针指针S1S2S3S4S5S6S7S8数据文件（主文件）数据文件（主文件）稠密索引稠密索引版权所有(C)-南京大学计算机科学与技术系稠密索引稠密索引(续续)利用稠密索引进行数据查找要比直接在数据文件上进利用稠密索引进行数据查找要比直接在数据文件上进行数据查找的速度快。其原因是：行数据查找的速度快。其原因是：索引文件使用的磁盘块比数据文件的少，因此磁盘索引文件使用的磁盘块比数据文件的少，因此磁盘I/O的时间开销小。的时间开销小。v一般情况下，一个磁
32、盘块中可以存放的索引项一般情况下，一个磁盘块中可以存放的索引项的个数要远远大于可以存放的记录数。的个数要远远大于可以存放的记录数。索引文件中的索引项被按照索引关键字的值进行了索引文件中的索引项被按照索引关键字的值进行了排序，因此在索引文件中可采用二分查找法来提高排序，因此在索引文件中可采用二分查找法来提高查找速度。查找速度。v这在无序的数据文件这在无序的数据文件(堆文件堆文件)中是无法做到的。中是无法做到的。索引文件可能足够小，可以放在内存中操作，从而索引文件可能足够小，可以放在内存中操作，从而不必访问磁盘不必访问磁盘。版权所有(C)-南京大学计算机科学与技术系稠密索引稠密索引(续续)利用稠密
33、索引查找关键字值为利用稠密索引查找关键字值为K的记录的算法如下：的记录的算法如下：1)1)采用二分查找法在索引文件中查找是否存在关键采用二分查找法在索引文件中查找是否存在关键字值为字值为K的索引项；的索引项；2)2)如果不存在相关的索引项，则表示关键字值为如果不存在相关的索引项，则表示关键字值为K的的记录不存在，查找失败。记录不存在，查找失败。否则：否则：3)3)根据找到的索引项中的记录指针到数据文件中进根据找到的索引项中的记录指针到数据文件中进行直接定位，读取相应的记录。行直接定位，读取相应的记录。版权所有(C)-南京大学计算机科学与技术系稠密索引稠密索引(续续)例例2 为为 例例1中的顺序
34、数据文件建立一个稠密索引。假中的顺序数据文件建立一个稠密索引。假设每个磁盘块可以存放设每个磁盘块可以存放100个索引项，则该稠密索个索引项，则该稠密索引共有引共有106个索引项，需要占用：个索引项，需要占用：104个磁盘块（约个磁盘块（约40MB）利用该稠密索引进行记录定位需要的磁盘利用该稠密索引进行记录定位需要的磁盘I/O次数为：次数为：log2104+1 13.3+1 13.3+1 15v其中的其中的1是访问数据文件的磁盘是访问数据文件的磁盘I/O。版权所有(C)-南京大学计算机科学与技术系7.6 索引技术与散列技术索引技术与散列技术 稀疏索引稀疏索引 如果数据文件是顺序文件，我们可以在索
35、引文件中如果数据文件是顺序文件，我们可以在索引文件中只为数据文件的每个磁盘块设一个索引项，记录该只为数据文件的每个磁盘块设一个索引项，记录该磁盘块中第一条数据记录的关键字值及该磁盘块的磁盘块中第一条数据记录的关键字值及该磁盘块的首地址。首地址。这样建立起来的索引文件被称为这样建立起来的索引文件被称为稀疏索引稀疏索引版权所有(C)-南京大学计算机科学与技术系1 记记录录1 2 记记录录2 3 记记录录3 4 记记录录4 5 记记录录5 6 记记录录6 7 记记录录7 8 记记录录8 9 记记录录9 第第1个个磁磁盘盘块块 第第2个个磁磁盘盘块块 第第3个个磁磁盘盘块块 第第4个个磁磁盘盘块块 1
36、 记记录录1的的指指针针 3 记记录录3的的指指针针 5 记记录录5的的指指针针 7 记记录录7的的指指针针 9 记记录录9的的指指针针 11 记记录录11的的指指针针 13 记记录录13的的指指针针 15 记记录录15的的指指针针 第第1个个磁磁盘盘块块 第第2个个磁磁盘盘块块 稀疏索引稀疏索引(续续)数据文件（主文件）数据文件（主文件）稀疏索引稀疏索引假设每个磁盘块可以存放假设每个磁盘块可以存放2条数据记录或条数据记录或4条索引项条索引项版权所有(C)-南京大学计算机科学与技术系稀疏索引稀疏索引(续续)利用利用稀疏稀疏索引查找关键字值为索引查找关键字值为K的记录的算法如下：的记录的算法如下
37、：1)1)采用二分查找法在索引文件中查找关键字值采用二分查找法在索引文件中查找关键字值小于小于或等于或等于K，且最接近且最接近K的索引项；的索引项；2)2)如果不存在相关的索引项，则表示关键字值为如果不存在相关的索引项，则表示关键字值为K的的记录不存在记录不存在(所有记录的索引关键字的值均大于所有记录的索引关键字的值均大于K)K)，查找失败。查找失败。否则：否则：3)3)根据找到的索引项中的记录指针到数据文件中读根据找到的索引项中的记录指针到数据文件中读取相应的磁盘块取相应的磁盘块 D D；4)4)在磁盘块在磁盘块 D D 中利用二分查找法查找关键字值为中利用二分查找法查找关键字值为K K的记
38、录。的记录。版权所有(C)-南京大学计算机科学与技术系稀疏索引稀疏索引(续续)例例3 为例为例1中的顺序数据文件再建立一个稀疏索引。由中的顺序数据文件再建立一个稀疏索引。由于该数据文件共占用于该数据文件共占用105个磁盘块，因此稀疏索引个磁盘块，因此稀疏索引文件中有文件中有105个索引项，需要占用：个索引项，需要占用：v103个磁盘块（约个磁盘块（约4MB）利用该稀疏索引进行记录定位需要的磁盘利用该稀疏索引进行记录定位需要的磁盘I/O次数为：次数为：v log2103+1 9.97+1 9.97+1 11版权所有(C)-南京大学计算机科学与技术系稀疏索引稀疏索引(续续)稠密索引稠密索引 与与
39、稀疏索引稀疏索引 的区别的区别 索引文件的定义不同索引文件的定义不同v稀疏索引只能用于顺序文件上的索引组织。稀疏索引只能用于顺序文件上的索引组织。v稠密索引中的每个索引项对应数据文件中的一条稠密索引中的每个索引项对应数据文件中的一条记录，而稀疏索引中的每个索引项则对应数据文件记录，而稀疏索引中的每个索引项则对应数据文件中的一个磁盘块。中的一个磁盘块。需要的磁盘空间大小不同需要的磁盘空间大小不同 在记录的查找定位功能上存在差别：在记录的查找定位功能上存在差别：v稠密索引：可以直接回答是否存在键值为稠密索引：可以直接回答是否存在键值为K K的记录。的记录。v稀疏索引：需要额外的磁盘稀疏索引：需要额
40、外的磁盘I/OI/O操作，即需要将相操作，即需要将相应的数据文件中的磁盘块读入内存后才能判别该记应的数据文件中的磁盘块读入内存后才能判别该记录是否存在。录是否存在。版权所有(C)-南京大学计算机科学与技术系7.6 索引技术与散列技术索引技术与散列技术多级索引多级索引 索引文件本身也可能占据多个存储块，为了能够快索引文件本身也可能占据多个存储块，为了能够快速找到这些索引块在磁盘中的存储位置，需要引入速找到这些索引块在磁盘中的存储位置，需要引入新的索引结构，即在索引文件上再建立索引，从而新的索引结构，即在索引文件上再建立索引，从而构成了多级索引。构成了多级索引。由于索引文件本身是顺序文件，因此索引
41、文件上由于索引文件本身是顺序文件，因此索引文件上的索引组织方法采用的是稀疏索引。的索引组织方法采用的是稀疏索引。我们将直接建立在数据文件上的索引（例我们将直接建立在数据文件上的索引（例2、例、例3中中建立的索引）称为第一级索引，根据第一级索引文建立的索引）称为第一级索引，根据第一级索引文件建立的索引称为第二级索引，依此类推，从而可件建立的索引称为第二级索引，依此类推，从而可以建立一个多级索引结构。以建立一个多级索引结构。在多级索引组织结构中，第一级索引可以是稠密在多级索引组织结构中，第一级索引可以是稠密索引，也可以是稀疏索引。索引，也可以是稀疏索引。从第二级索引开始建立的都是稀疏索引。从第二级
42、索引开始建立的都是稀疏索引。版权所有(C)-南京大学计算机科学与技术系1 2 3 4 5 6 7 8 多级索引多级索引(续续)数据文件数据文件（顺序文件）（顺序文件）第第1级级稠密索引稠密索引1 记记录录1 2 记记录录2 3 记记录录3 4 记记录录4 5 记记录录5 6 记记录录6 7 记记录录7 8 记记录录8 9 记记录录9 磁磁盘盘块块1 磁磁盘盘块块2 磁磁盘盘块块3 磁磁盘盘块块4 1 5 9 13 17 21 25 29 第第2级级稀疏索引稀疏索引版权所有(C)-南京大学计算机科学与技术系1 2 3 4 5 6 7 8 多级索引多级索引(续续)数据文件数据文件（堆文件）（堆文件
43、）第第1级级稠密索引稠密索引3 记记录录3 1 记记录录1 5 记记录录5 8 记记录录8 7 记记录录7 6 记记录录6 2 记记录录2 4 记记录录4 9 记记录录9 磁磁盘盘块块1 磁磁盘盘块块2 磁磁盘盘块块3 磁磁盘盘块块4 1 5 9 13 17 21 25 29 第第2级级稀疏索引稀疏索引版权所有(C)-南京大学计算机科学与技术系1 3 5 7 9 11 13 15 多级索引多级索引(续续)数据文件数据文件（顺序文件）（顺序文件）第第1级级稀疏索引稀疏索引1 记记录录1 2 记记录录2 3 记记录录3 4 记记录录4 5 记记录录5 6 记记录录6 7 记记录录7 8 记记录录8
44、 9 记记录录9 磁磁盘盘块块1 磁磁盘盘块块2 磁磁盘盘块块3 磁磁盘盘块块4 1 9 17 25 33 41 49 57 第第2级级稀疏索引稀疏索引版权所有(C)-南京大学计算机科学与技术系多级索引多级索引(续续)例例4 在例在例2中的稠密索引文件上再建立一个稀疏索引中的稠密索引文件上再建立一个稀疏索引 由于例由于例2中的稠密索引文件共占用中的稠密索引文件共占用104个磁盘块，因此新个磁盘块，因此新建立的稀疏索引文件中有建立的稀疏索引文件中有104个索引项，需要占用：个索引项，需要占用：100个磁盘块（约个磁盘块（约400KB）例例55 在例在例3 3中的稀疏索引文件上也可以再建立一个稀疏
45、索引中的稀疏索引文件上也可以再建立一个稀疏索引 由于例由于例3 3中的稀疏索引文件共占用中的稀疏索引文件共占用10103 3个磁盘块，因此新个磁盘块，因此新建立的稀疏索引文件中有建立的稀疏索引文件中有10103 3个索引项，只需要占用：个索引项，只需要占用：1010个磁盘块（约个磁盘块（约4040KBKB）版权所有(C)-南京大学计算机科学与技术系多级索引多级索引(续续)考虑在例考虑在例4 4和例和例5 5中所建立的第二级索引文件，由于它中所建立的第二级索引文件，由于它们只分别占用们只分别占用400400KBKB和和4040KBKB的存储空间，这样的索引的存储空间，这样的索引文件完全可以全部放
46、在内存中。文件完全可以全部放在内存中。在这样的二级索引文件上进行搜索定位不需要索引文在这样的二级索引文件上进行搜索定位不需要索引文件上的磁盘件上的磁盘I/OI/O操作，我们只要根据在二级索引中查操作，我们只要根据在二级索引中查找到的索引项到第一级索引文件中直接读取相应的索找到的索引项到第一级索引文件中直接读取相应的索引磁盘块，并根据在该磁盘块中所找到的索引项到数引磁盘块，并根据在该磁盘块中所找到的索引项到数据文件中直接读取相应的数据文件磁盘块或记录。据文件中直接读取相应的数据文件磁盘块或记录。因此，根据这样的两级索引结构进行记录的查找定位因此，根据这样的两级索引结构进行记录的查找定位只需要只需
47、要2 2次磁盘次磁盘I/OI/O操作，大大低于我们在例操作，大大低于我们在例2 2和例和例3 3中中所需的磁盘所需的磁盘I/OI/O次数（见下表）次数（见下表）版权所有(C)-南京大学计算机科学与技术系多级索引多级索引(续续)索引类型索引类型需要的磁盘空间需要的磁盘空间（包括数据文件和（包括数据文件和索引文件）索引文件）记录查找需要记录查找需要的磁盘的磁盘I/O次数次数例例1无索引，直接在顺序数据无索引，直接在顺序数据文件上进行记录的查找文件上进行记录的查找10517例例2一级稠密索引一级稠密索引105+10415例例3一级稀疏索引一级稀疏索引105+10311例例4基于一级稠密索引的基于一级
48、稠密索引的二级索引二级索引105+104+1022例例5基于一级稀疏索引的基于一级稀疏索引的二级索引二级索引105+103+1012多级索引与单级索引的性能比较多级索引与单级索引的性能比较版权所有(C)-南京大学计算机科学与技术系7.6 索引技术与散列技术索引技术与散列技术 在在顺序数据文件顺序数据文件中建立中建立具有重复键值具有重复键值的索引的索引 在数据文件中索引关键字的值是不唯一的，即一个在数据文件中索引关键字的值是不唯一的，即一个索引关键字值对应着若干条记录。索引关键字值对应着若干条记录。具有重复键值的索引文件可以采用以下的组织方法：具有重复键值的索引文件可以采用以下的组织方法：v 稠
49、密索引稠密索引v 稀疏索引稀疏索引 到此为止，我们介绍了基于顺序文件的稠密索引、到此为止，我们介绍了基于顺序文件的稠密索引、稀疏索引和多级索引，并且索引属性是关系的关键稀疏索引和多级索引，并且索引属性是关系的关键字，具有唯一性。以此为基础，我们可以构造出索字，具有唯一性。以此为基础，我们可以构造出索引属性不唯一以及非顺序文件上的索引。引属性不唯一以及非顺序文件上的索引。版权所有(C)-南京大学计算机科学与技术系7.6 索引技术与散列技术索引技术与散列技术 具有重复键值的索引文件组织具有重复键值的索引文件组织 具有重复键值的稠密索引具有重复键值的稠密索引v为数据文件中的为数据文件中的每一个索引关
50、键字值每一个索引关键字值 K K 定义一个索定义一个索引项引项，其中的记录指针指向索引关键字值等于，其中的记录指针指向索引关键字值等于 K K 的的第一条记录。第一条记录。在索引文件中索引关键字的值是唯一的在索引文件中索引关键字的值是唯一的v利用该索引文件查找键值为利用该索引文件查找键值为 K 的记录时，所找到的的记录时，所找到的记录指针（如果找到具有键值为记录指针（如果找到具有键值为K的索引项）指向数的索引项）指向数据文件中第一条键值为据文件中第一条键值为K的记录。的记录。v由于由于数据文件是顺序文件数据文件是顺序文件，因此，我们可以在数据文，因此，我们可以在数据文件中从找到的第一条记录开始
