《【教学课件】第五章数据库的存储结构.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第五章数据库的存储结构.ppt(55页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第五章第五章 数据数据库的存的存储结构构5.15.1数据数据库存存储介介质的特点的特点n n采用多采用多采用多采用多级级存存存存储储器,用的最多的器,用的最多的器,用的最多的器,用的最多的辅辅存是磁存是磁存是磁存是磁盘盘。n n光光光光盘盘由于速度和价格上的原因,近期无法取由于速度和价格上的原因,近期无法取由于速度和价格上的原因,近期无法取由于速度和价格上的原因,近期无法取代硬代硬代硬代硬盘盘。n n磁磁磁磁带带是是是是顺顺序存取存序存取存序存取存序存取存储储器,通常用作后器,通常用作后器,通常用作后器,通常用作后备备存存存存储储器。器。器。器。数据数据库是大量、持久数据的集合,在是大量、持久
2、数据的集合,在现阶段段用内存作用内存作为数据数据库的存的存储介介质是不合适的是不合适的。n活活动头磁磁盘的存取的存取时间由三部分由三部分组成:成:寻道道时间、等待、等待时间以及以及传输时间。n磁磁盘上的数据划分上的数据划分为大小相等的物理大小相等的物理块。磁。磁盘与内存与内存间的数据交的数据交换以物理以物理块为单位。位。以物理以物理以物理以物理块为块为交交交交换单换单位的位的位的位的优优点:点:点:点:1).1).1).1).减少减少减少减少I/OI/O的次数的次数的次数的次数,从而减少,从而减少,从而减少,从而减少寻寻道和等待的道和等待的道和等待的道和等待的时间时间。2).2).2).2).
3、减少减少减少减少间间隙的数目隙的数目隙的数目隙的数目,提高磁,提高磁,提高磁,提高磁盘盘空空空空间间利用率。利用率。利用率。利用率。物理快的大小由物理快的大小由物理快的大小由物理快的大小由OSOS决定。决定。决定。决定。n一般,在磁一般,在磁盘和内存之和内存之间设立立缓冲区以解决冲区以解决二者的速度不匹配二者的速度不匹配问题。由于有多个由于有多个缓冲冲块可供申可供申请使用,磁使用,磁盘的的读写写操作和操作和读写数据的写数据的处理可以重叠理可以重叠进行。行。读出:出:i块缓冲冲块A处理:理:处理理A中中i块i+1块缓冲冲块B i+2块缓冲冲块A处理理B中中i+1块qq OS OS与与与与DBMS
4、DBMS都有各自的都有各自的都有各自的都有各自的缓缓冲区。冲区。冲区。冲区。qq 不少不少不少不少DBMSDBMS采用采用采用采用延延延延迟迟写写写写与与与与提前提前提前提前读读技技技技术术,减少,减少,减少,减少I/OI/O,改善性能。改善性能。改善性能。改善性能。5.25.2记录的存的存储结构构n记录是目前商用数据是目前商用数据库的基本数据的基本数据单元,有定元,有定长和和变长之分。之分。n记录的存的存储结构构1.1.1.1.定位法定位法定位法定位法每个字段按其最大可能每个字段按其最大可能每个字段按其最大可能每个字段按其最大可能长长度分配定度分配定度分配定度分配定长长的的的的位置位置位置位
5、置LIbbbMINGbbbMALEbb1967512182.2.2.2.相相相相对对法法法法每个字段没有固定的每个字段没有固定的每个字段没有固定的每个字段没有固定的长长度,而是用特度,而是用特度,而是用特度,而是用特殊的字符分隔开殊的字符分隔开殊的字符分隔开殊的字符分隔开LI?MING?MALE?1967#问题:字段中也需要用到字段中也需要用到这些分隔符些分隔符时,如何,如何进行行表示?表示?3.3.3.3.计计数法数法数法数法每个字段的开始加上表示每个字段的开始加上表示每个字段的开始加上表示每个字段的开始加上表示该该字段字段字段字段长长度度度度 的字段的字段的字段的字段02LI04MING0
6、4MALE041967问题:计数法数法对字段的字段的实际长度度有什么要求?有什么要求?记录在物理在物理块上的分配上的分配n n磁磁磁磁盘盘上,上,上,上,记录记录必必必必须须分配到物理分配到物理分配到物理分配到物理块块中。中。中。中。记录记录跨快存跨快存跨快存跨快存储储(spannedspanned)记录记录不不不不垮块垮块存存存存储储(unspannedunspanned)设为物理物理块的有效空的有效空间大小,大小,为固定固定长记录的大小,若的大小,若,则每个物理每个物理块可容可容纳的的记录数数为:p=B/Rp称称为块因子(因子(Blocking Factor)。)。记录一般不会一般不会刚好
7、填好填满物理物理块,会留下不用的零,会留下不用的零头空空间:BpRR 为了利用了利用这部分空部分空间,可以利用,可以利用记录的跨的跨块存存储组织(spanned organization)。记录1记录2 2记录3 3记录4 4n n定定定定长记录长记录(跨(跨(跨(跨块块)记录1记录2 2记录3 3记录4 4块i记录4(剩余部剩余部分分)记录5 5记录6 6记录7 7块i+1n n变长记录变长记录(跨(跨(跨(跨块块)记录1记录2 2记录3 3块i记录3(剩剩余部分余部分)记录4 4记录5 5块i+1 物理物理块在磁在磁盘上的分配上的分配早期的早期的早期的早期的DBMSDBMS中,通常由操作系
8、中,通常由操作系中,通常由操作系中,通常由操作系统统分配分配分配分配数据数据数据数据库库所需的物理所需的物理所需的物理所需的物理块块,逻辑逻辑上相上相上相上相邻邻的数据可的数据可的数据可的数据可能被分散到磁能被分散到磁能被分散到磁能被分散到磁盘盘的不同区域。使得的不同区域。使得的不同区域。使得的不同区域。使得访问访问数据数据数据数据时时,性能下降。,性能下降。,性能下降。,性能下降。现现代代代代DBMSDBMS中,都改由中,都改由中,都改由中,都改由DBMSDBMS初始化初始化初始化初始化时时向操作系向操作系向操作系向操作系统统一次性的申一次性的申一次性的申一次性的申请请所需的存所需的存所需的
9、存所需的存储储空空空空间间。1 1、连续分配法(分配法(contiguous allocation)2 2 2 2、链链接分配法(接分配法(接分配法(接分配法(linked allocationlinked allocation)物理物理物理物理块块未必分配在磁未必分配在磁未必分配在磁未必分配在磁盘盘的的的的连续连续存存存存储储空空空空间间上,上,上,上,各物理各物理各物理各物理块块用指用指用指用指针链针链接,接,接,接,有利于文件的有利于文件的有利于文件的有利于文件的扩扩展,但展,但展,但展,但效率效率效率效率较较差。差。差。差。将一个文件的将一个文件的块分配在磁分配在磁盘的的连续空空间上,
10、上,块的次序就是其存的次序就是其存储的次序,的次序,有利于有利于顺序存取序存取多多块文件,不利于文件的文件,不利于文件的扩充充。3 3 3 3、簇集分配法(、簇集分配法(、簇集分配法(、簇集分配法(clustered allocationclustered allocation)上述两种方法的上述两种方法的上述两种方法的上述两种方法的结结合。合。合。合。4 4 4 4、索引分配法(、索引分配法(、索引分配法(、索引分配法(indexed allocationindexed allocation)每个文件有一个每个文件有一个逻辑块号与其物理号与其物理块地址地址对照的索引。照的索引。n n数据数据
11、数据数据压缩压缩技技技技术术1.1.1.1.消零或空格符法(消零或空格符法(消零或空格符法(消零或空格符法(null suppressionnull suppression)例如,例如,例如,例如,bbbbbbbbbb可以用可以用可以用可以用#5#5#5#5表示;表示;表示;表示;000000000000000000000000可以用可以用可以用可以用66表示等。表示等。表示等。表示等。2.2.2.2.串型代替法(串型代替法(串型代替法(串型代替法(pattern substitutionpattern substitution)对对反复出反复出反复出反复出现现的字符串,可以用一个的字符串,可
12、以用一个的字符串,可以用一个的字符串,可以用一个省略符代替。省略符代替。省略符代替。省略符代替。例如,串型表如右:例如,串型表如右:例如,串型表如右:例如,串型表如右:IBM PC/XT0000#原始数据原始数据IBM PC/XT 00001IBM PC/XT 00002压缩数据数据#1#23.3.3.3.索引法(索引法(索引法(索引法(indexingindexing)串行代替法的串行代替法的串行代替法的串行代替法的变变种,种,种,种,对对重复出重复出重复出重复出现现的串行,的串行,的串行,的串行,单单独存独存独存独存储储,在用到,在用到,在用到,在用到这这些串行的地方,些串行的地方,些串行
13、的地方,些串行的地方,用指用指用指用指针针引用引用引用引用它。它。它。它。索引法示例:索引法示例:BeijingNanjingShanghaiCITY表表SHOP#CITY0001Nanjing0002Nanjing0003Nanjing0004Shanghai原始数据原始数据0005ShanghaiSHOP#CITY0001000200030004压缩数据数据0005问题问题:索引法索引法索引法索引法对对串型的串型的串型的串型的长长度有什么要求?度有什么要求?度有什么要求?度有什么要求?5.35.3文件文件结构和存取路径构和存取路径5.3.15.3.15.3.15.3.1访问访问文件的方式文
14、件的方式文件的方式文件的方式 传统传统的数据模型都以的数据模型都以的数据模型都以的数据模型都以记录为记录为基基基基础础,记录记录的集合构成的集合构成的集合构成的集合构成文件。文件文件。文件文件。文件文件。文件须须按一定的按一定的按一定的按一定的结结构构构构组织组织和存和存和存和存储记录储记录,按一定,按一定,按一定,按一定的存取路径的存取路径的存取路径的存取路径访问访问有关有关有关有关记录记录。对对数据数据数据数据库库的操作最的操作最的操作最的操作最终终要落要落要落要落实实到到到到对对文件的操作。文件的操作。文件的操作。文件的操作。文件文件文件文件结结构及其所提供的存构及其所提供的存构及其所提
15、供的存构及其所提供的存储储路径直接影响数据路径直接影响数据路径直接影响数据路径直接影响数据访问访问的速度,通常的速度,通常的速度,通常的速度,通常针对针对不同的数据不同的数据不同的数据不同的数据访问访问采用不同的文件采用不同的文件采用不同的文件采用不同的文件结结构。构。构。构。1.1.1.1.查询查询文件的全部或相当多的文件的全部或相当多的文件的全部或相当多的文件的全部或相当多的记录记录(15%15%15%15%)2.2.2.2.查询查询某一特定某一特定某一特定某一特定记录记录3.3.3.3.查询查询某些某些某些某些记录记录4.4.4.4.范范范范围查询围查询5.5.5.5.记录记录的更新的更
16、新的更新的更新文件文件文件文件访问访问方式按方式按方式按方式按设计设计文件文件文件文件结结构的构的构的构的观观点分点分点分点分5 5 5 5类类5.3.25.3.25.3.25.3.2数据数据数据数据库对库对文件的要求文件的要求文件的要求文件的要求一些一些一些一些DBMSDBMS就以就以就以就以OSOS的的文件管理系的的文件管理系的的文件管理系的的文件管理系统统作作作作为为其物理其物理其物理其物理层层的基的基的基的基础础,更多的,更多的,更多的,更多的DBMSDBMS不用不用不用不用OSOS的的的的文件管理系文件管理系文件管理系文件管理系统统,而是独立,而是独立,而是独立,而是独立设计设计其存
17、其存其存其存储结储结构。构。构。构。原因如下:原因如下:原因如下:原因如下:qq 传统传统文件系文件系文件系文件系统统不能提供不能提供不能提供不能提供实现实现DBMSDBMS功能所需的功能所需的功能所需的功能所需的附加信息。附加信息。附加信息。附加信息。DBMSDBMS为为了了了了实现实现其功能,其功能,其功能,其功能,须须在文件目在文件目在文件目在文件目录录、文件描述、文件描述、文件描述、文件描述块块、物理物理物理物理块块等部分附加一些信息。等部分附加一些信息。等部分附加一些信息。等部分附加一些信息。qq 传统传统文件系文件系文件系文件系统统主要面向批主要面向批主要面向批主要面向批处处理,数
18、据理,数据理,数据理,数据库库系系系系统统要要要要求即求即求即求即时访问时访问、动态动态修改。修改。修改。修改。这这就要求文件的就要求文件的就要求文件的就要求文件的结结构能构能构能构能适适适适应应数据的数据的数据的数据的动态变动态变化,提供快速化,提供快速化,提供快速化,提供快速访问访问路径。路径。路径。路径。qq 传统传统文件系文件系文件系文件系统统服服服服务对务对象特殊,用途象特殊,用途象特殊,用途象特殊,用途单单一,共享一,共享一,共享一,共享度低;数据度低;数据度低;数据度低;数据库库中的文件供所有用中的文件供所有用中的文件供所有用中的文件供所有用户户共享,有些用共享,有些用共享,有些
19、用共享,有些用途甚至是不可知的。途甚至是不可知的。途甚至是不可知的。途甚至是不可知的。qq 减少减少减少减少DBMSDBMS对对OSOS的依的依的依的依赖赖,提高,提高,提高,提高DBMSDBMS的可移植的可移植的可移植的可移植性。性。性。性。qq 传统传统文件系文件系文件系文件系统统一旦建立以后,数据量比一旦建立以后,数据量比一旦建立以后,数据量比一旦建立以后,数据量比较稳较稳定;定;定;定;数据数据数据数据库库中文件的数据量中文件的数据量中文件的数据量中文件的数据量变变化化化化较较大。大。大。大。5.3.35.3.35.3.35.3.3文件的基本文件的基本文件的基本文件的基本类类型型型型不
20、同不同类型的型的访问各有其使用的文件各有其使用的文件结构和构和存取路径。存取路径。DBMS通常提供多种文件通常提供多种文件结构,供构,供数据数据库设计者者选用。用。1.1.堆文件(堆文件(heap file)2.2.直接文件(直接文件(direct file)3.3.索引文件(索引文件(indexed file)n n最最最最简单简单、最早使用的文、最早使用的文、最早使用的文、最早使用的文件件件件结结构。构。构。构。记录记录按其插入按其插入按其插入按其插入的先后次序存放(的先后次序存放(的先后次序存放(的先后次序存放(所有所有所有所有记录记录在物理上不一定相在物理上不一定相在物理上不一定相在物
21、理上不一定相邻邻接接接接)n n堆文件插入容易、堆文件插入容易、堆文件插入容易、堆文件插入容易、查查找找找找不方便(不方便(不方便(不方便(所提供的唯一所提供的唯一所提供的唯一所提供的唯一存取路径就是存取路径就是存取路径就是存取路径就是顺顺序搜索序搜索序搜索序搜索)堆堆文文件件记录1 1记录6 6记录2 2记录1 1记录2 2记录3 3记录5 5记录6 61.1.1.1.堆文件堆文件堆文件堆文件记录4 4n n适于适于适于适于访问访问全部或相当多的全部或相当多的全部或相当多的全部或相当多的记录记录,对对于其它于其它于其它于其它类访问类访问效率效率效率效率较较低。低。低。低。(设设文件文件文件文
22、件记录记录数数数数为为N N,查查找某一找某一找某一找某一记录记录的平均的平均的平均的平均访问访问次数次数次数次数为为N+1/2N+1/2)n n若堆文件的若堆文件的若堆文件的若堆文件的记录记录按按按按检检索属性排序,可用二分索属性排序,可用二分索属性排序,可用二分索属性排序,可用二分查查找法。找法。找法。找法。(但要以排序(但要以排序(但要以排序(但要以排序为为代价)代价)代价)代价)堆堆文文件件记录1 1记录3 3记录5 5记录6 6记录4 4记录7 7记录8 8记录2 2 假假设,要,要删除右除右图堆文件中堆文件中的第的第2,4,6条数据条数据记录。直接直接删除除这三条三条记录的情况的情
23、况如右如右图所示。所示。带来什么来什么问题?n n 删删除除除除记录较记录较麻麻麻麻烦烦空空空空间间回收回收回收回收问题问题,后,后,后,后续记录续记录需搬移,影响需搬移,影响需搬移,影响需搬移,影响对对文件的操作效文件的操作效文件的操作效文件的操作效率。率。率。率。作作删除除标记堆堆文文件件记录1 1记录2 2记录3 3记录5 5记录6 6记录4 4记录7 7记录8 8堆堆文文件件记录1 1记录3 3记录5 5记录6 6记录4 4记录7 7记录8 8记录2 2堆堆文文件件记录1 1记录3 3记录5 5记录7 7记录8 8集中集中删除除记录,并,并进行行记录重排重排 解决方法解决方法2.2.2
24、.2.直接文件直接文件直接文件直接文件 直接文件中,将直接文件中,将直接文件中,将直接文件中,将记录记录的某一属性用散列函数直的某一属性用散列函数直的某一属性用散列函数直的某一属性用散列函数直接映射成接映射成接映射成接映射成记录记录的地址,被散列的属性称的地址,被散列的属性称的地址,被散列的属性称的地址,被散列的属性称为为散列散列散列散列键键。Student(SNO,SNAME,SEX,BIRTHDATE,DEPT)散列函数散列函数 H(SNO)=Address900412900412李林李林计算机系算机系 H(900412900412)=addraddr存存储空空间900412900412李
25、林李林计算机系算机系qq 键键所映射的地址范所映射的地址范所映射的地址范所映射的地址范围围固定固定固定固定(地址范(地址范(地址范(地址范围设围设的太大或的太大或的太大或的太大或太小都不好太小都不好太小都不好太小都不好,为为什么?什么?什么?什么?)。上述原因上述原因上述原因上述原因导导致直接文件目前在数据致直接文件目前在数据致直接文件目前在数据致直接文件目前在数据库库系系系系统统中使用不多。中使用不多。中使用不多。中使用不多。直接文件存在的直接文件存在的直接文件存在的直接文件存在的问题问题:qq 地址重叠地址重叠地址重叠地址重叠问题问题(处处理地址重叠增加了开理地址重叠增加了开理地址重叠增加
26、了开理地址重叠增加了开销销)。qq 直接文件只直接文件只直接文件只直接文件只对对散列散列散列散列键键的的的的访问访问有效。有效。有效。有效。qq 不便于不便于不便于不便于处处理理理理变长记录变长记录。qq 对对于通用的于通用的于通用的于通用的DBMSDBMS很很很很难难找到通用的散列函数。找到通用的散列函数。找到通用的散列函数。找到通用的散列函数。3.3.3.3.索引文件索引文件索引文件索引文件索引相当于一个映射机构,把关系中相索引相当于一个映射机构,把关系中相应记录的某个(些)属性的的某个(些)属性的键值转换为该记录的存的存储地地址(或地址集)。址(或地址集)。addr1addr2addr3
27、SNOAddress学生表的索引文件学生表的索引文件900412900412addr2900417900417addr1900418900418addr3存存储空空间900418900418周力周力计算机系算机系900412900412李林李林计算机系算机系900417900417陈燕燕计算机系算机系n n索引与散列的区索引与散列的区索引与散列的区索引与散列的区别别索引文件有索引文件有索引文件有索引文件有记录记录才占用才占用才占用才占用存存存存储储空空空空间间,使用散列空文件也占用全部文件空,使用散列空文件也占用全部文件空,使用散列空文件也占用全部文件空,使用散列空文件也占用全部文件空间间。n
28、 n索引本省占用空索引本省占用空索引本省占用空索引本省占用空间间,但索引一般,但索引一般,但索引一般,但索引一般较记录较记录小得多小得多小得多小得多针对非散列非散列键和非索引属性的和非索引属性的访问,都不能有效,都不能有效发挥直直接文件或索引文件的接文件或索引文件的优势。散列或索引失效。散列或索引失效时,两者,两者谁的的访问代价更大?代价更大?1.1.1.1.主索引主索引主索引主索引以主以主以主以主键为键为索引索引索引索引键键(primary index)primary index)。2.2.次索引次索引次索引次索引以非主以非主以非主以非主键为键为索引索引索引索引键键(secendary in
29、dex)secendary index),建立次索引可以提高建立次索引可以提高建立次索引可以提高建立次索引可以提高查询查询的效率,但增加了索的效率,但增加了索的效率,但增加了索的效率,但增加了索引引引引维护维护的开的开的开的开销销。3.3.3.3.倒排文件倒排文件倒排文件倒排文件主索引主索引主索引主索引+次索引的极端情况(文件的次索引的极端情况(文件的次索引的极端情况(文件的次索引的极端情况(文件的所有属性上都建立索引),有利于多属性所有属性上都建立索引),有利于多属性所有属性上都建立索引),有利于多属性所有属性上都建立索引),有利于多属性值值的的的的查查找,但数据更新找,但数据更新找,但数据
30、更新找,但数据更新时时开开开开销销很大。很大。很大。很大。为为了便于了便于了便于了便于检检索,索引索,索引索,索引索,索引项总项总是按索引是按索引是按索引是按索引键键排序。排序。排序。排序。受按受按受按受按门门牌号找住牌号找住牌号找住牌号找住户户的启示(的启示(的启示(的启示(住住住住户户在在在在“物理物理物理物理”上按上按上按上按门门牌号牌号牌号牌号码码排序排序排序排序),提出),提出),提出),提出非稠密索引非稠密索引非稠密索引非稠密索引。注意:索引注意:索引注意:索引注意:索引项项 记录记录,并不是文件中的并不是文件中的并不是文件中的并不是文件中的记录记录按索引按索引按索引按索引键键排序
31、排序排序排序文件中的文件中的文件中的文件中的记录记录按索引按索引按索引按索引键键排序排序排序排序吗吗?n非稠密索引与稠密索引非稠密索引与稠密索引1.1.不不为每个每个键值设立索引立索引项的索引的索引非稠密索引非稠密索引2.2.可以可以节省索引的存省索引的存储空空间,代价是文件要按索引,代价是文件要按索引键排序排序3.对一个文件,只能一个文件,只能为一个索引一个索引键(一般(一般为主主键)建)建立非稠密索引立非稠密索引(为什么?)什么?)4.4.4.4.非稠密索引中,若干个非稠密索引中,若干个非稠密索引中,若干个非稠密索引中,若干个记录组记录组成一个成一个成一个成一个单单元存元存元存元存储储区,
32、区,区,区,单单元存元存元存元存储储区中的区中的区中的区中的记录记录按索引按索引按索引按索引键键排序。排序。排序。排序。5.5.5.5.单单元存元存元存元存储储区装区装区装区装满满后,可向溢出区溢出(用指后,可向溢出区溢出(用指后,可向溢出区溢出(用指后,可向溢出区溢出(用指针针指向溢指向溢指向溢指向溢出区),但溢出太多出区),但溢出太多出区),但溢出太多出区),但溢出太多时时,指,指,指,指针链针链接次数增加,将接次数增加,将接次数增加,将接次数增加,将导导致数致数致数致数据据据据库库性能下降。性能下降。性能下降。性能下降。6.6.6.6.可以建立多可以建立多可以建立多可以建立多级级非稠密索
33、引(非稠密索引(非稠密索引(非稠密索引(通常最高一通常最高一通常最高一通常最高一级级索引索引索引索引应应尽量尽量尽量尽量保保保保证证可以常可以常可以常可以常驻驻内存内存内存内存)。)。)。)。1 12 23 34 45 56 67 78 89 91010111112121211211341341671671821822032032112112232232292292312312372372412411313141415151616255255259259267267271271单单元存元存元存元存储储区区区区1821824 42012012232237 72232232412411212251
34、25127127116162712712892891919289289311311242431131141941928284194194304303131430430单单元元元元存存存存储储区区区区最最最最高高高高键键值值单单元元元元存存存存储储最最最最高高高高键键值值相相相相对对地地地地址址址址最最最最高高高高键键值值271271430430601601191191 201 201 249 249 251 251示例示例溢出区溢出区溢出区溢出区溢溢溢溢出出出出链链头头指指指指针针相相相相对对地址地址地址地址索引索引索引索引键键1 12 23 34 45 56 67 78 89 9101011
35、1112121211211341341671671821822032032112112232232292292312312372372412411313141415151616255255259259267267271271单单元存元存元存元存储储区区区区1821824 42012012232237 7223223241241121225125127127116162712712892891919289289311311242431131141941928284194194304303131430430单单元元元元存存存存储储区区区区最最最最高高高高键键值值单单元元元元存存存存储储最最最最高高
36、高高键键值值相相相相对对地地地地址址址址最最最最高高高高键键值值271271430430601601191191 201 201 249 249 251 251溢出区溢出区溢出区溢出区溢溢溢溢出出出出链链头头指指指指针针相相相相对对地址地址地址地址索引索引索引索引键键查找索引找索引键为211的的记录的存的存储地址地址2117211 稠密索引稠密索引(dense index)n n每个每个每个每个键值对应键值对应一个索引一个索引一个索引一个索引项项稠密索引。稠密索引。稠密索引。稠密索引。n n稠密索引的稠密索引的稠密索引的稠密索引的预查预查找找找找功能功能功能功能(用(用(用(用记录记录的地址代
37、替的地址代替的地址代替的地址代替记录记录参与参与参与参与集合运算,减少集合运算,减少集合运算,减少集合运算,减少I/OI/O次数)次数)次数)次数)。n n索引溢出的索引溢出的索引溢出的索引溢出的问题问题稠密索引中,每增加一个稠密索引中,每增加一个稠密索引中,每增加一个稠密索引中,每增加一个键值键值,就要增加一个索引,就要增加一个索引,就要增加一个索引,就要增加一个索引项项。索引也会有溢出的可能。索引也会有溢出的可能。索引也会有溢出的可能。索引也会有溢出的可能。解决方法:解决方法:解决方法:解决方法:1.1.1.1.在每个索引在每个索引在每个索引在每个索引块块中中中中预预留留留留发发展的空展的
38、空展的空展的空间间2.2.2.2.建立索引溢出区建立索引溢出区建立索引溢出区建立索引溢出区 例如:某个例如:某个例如:某个例如:某个键值对应键值对应100100100100个个个个记录记录,且,且,且,且这这100100100100个个个个记录记录分散在分散在分散在分散在100100100100个物理个物理个物理个物理块块中,中,中,中,虽虽然通然通然通然通过过稠密索引可以一稠密索引可以一稠密索引可以一稠密索引可以一次次次次获获得得得得这这100100100100个地址,但仍然要个地址,但仍然要个地址,但仍然要个地址,但仍然要访问访问100100100100个物理个物理个物理个物理块块。1.1
39、.1.1.稠密索引中,若稠密索引中,若稠密索引中,若稠密索引中,若键值键值不唯一,不唯一,不唯一,不唯一,则则在最低在最低在最低在最低级级索引中,索引中,索引中,索引中,每个每个每个每个键值对应键值对应的可能是一个的可能是一个的可能是一个的可能是一个地址集(地址集(地址集(地址集(对应对应多个多个多个多个记录记录)。如果。如果。如果。如果这这些些些些记录记录分散在不同的物理分散在不同的物理分散在不同的物理分散在不同的物理块块内,稠密索引内,稠密索引内,稠密索引内,稠密索引的的的的优优点并不能体点并不能体点并不能体点并不能体现现出来出来出来出来(并不一定能减少(并不一定能减少(并不一定能减少(并
40、不一定能减少I/OI/O)。)。)。)。采用簇集索引:把采用簇集索引:把采用簇集索引:把采用簇集索引:把键值键值相同的相同的相同的相同的记录记录在物理地址上集中存放。在物理地址上集中存放。在物理地址上集中存放。在物理地址上集中存放。键键键键指针指针指针指针头块头块链块链块1 1 1 1链块链块n n索引区索引区索引区索引区2.2.2.2.解决方法解决方法解决方法解决方法簇集索引(簇集索引(簇集索引(簇集索引(clustering indexclustering index)3.3.3.3.缺点:缺点:缺点:缺点:建立簇集索引的开建立簇集索引的开建立簇集索引的开建立簇集索引的开销较销较大,整个文
41、件要重新大,整个文件要重新大,整个文件要重新大,整个文件要重新组织组织。常用索引常用索引总结索引索引索引索引主索引主索引主索引主索引次索引次索引次索引次索引按主按主按主按主键键排序排序排序排序非稠密索引非稠密索引非稠密索引非稠密索引不按主不按主不按主不按主键键排序排序排序排序稠密索引稠密索引稠密索引稠密索引簇集索引簇集索引簇集索引簇集索引按索引按索引按索引按索引键键排序并簇集,排序并簇集,排序并簇集,排序并簇集,稠密索引稠密索引稠密索引稠密索引非簇集索引非簇集索引非簇集索引非簇集索引不按索引不按索引不按索引不按索引键键排序,排序,排序,排序,稠密索引稠密索引稠密索引稠密索引5.45.4动态索引
42、索引从数据从数据结构角度看:静构角度看:静态索引是个多分索引是个多分树;动态索索引是一种平衡多分引是一种平衡多分树(即(即B-树),常用),常用B+树。B+树的限制和的限制和规定:定:q 每个每个节点最多有点最多有2k个个键值,k称称为B+树的秩的秩(Order);q 根根节点至少有一个点至少有一个键值,其它,其它节点至少有点至少有k个个键值,节点内,点内,键值有序存放有序存放;q 除叶除叶节点无子女外,其它点无子女外,其它节点若有点若有J个个键值,则有有J+1个子女个子女;q 所有叶所有叶节点都点都处于于树的同一的同一层,即,即树始始终保持平衡。保持平衡。102015从根向叶搜索,直至相从根
43、向叶搜索,直至相应叶叶节点,若点,若该叶叶节点不点不满,则将将键值插入叶插入叶节点中;如叶点中;如叶节点已点已满(即已即已经有有2 2K个个键值),),则将此叶将此叶节点分裂点分裂为二,叶二,叶节点分裂后,其双点分裂后,其双亲节点也必点也必须增加一个增加一个键值,若双,若双亲节点不点不满,插入,插入过程程结束;否束;否则双双亲节点点继续分裂分裂为两个两个节点,如点,如此此继续直到插入直到插入过程中止。程中止。插入算法:插入算法:(K=1):10,15,20,25,30,35,40,50101510,15202520,25301015203025201015,253015253510203040
44、,50先从根先从根节点出点出发,找到,找到待待删除除键值所在叶所在叶节点;若点;若删除除该键值后,叶后,叶节点中点中键值数减数减为K-1个,个,则向其左向其左右兄弟叶右兄弟叶节点借一个点借一个键值,以保持每个叶以保持每个叶节点存放点存放键值不少于不少于K个个;若其左右叶;若其左右叶节点都只有点都只有K个个键值,则可可将将该叶叶节点与其左(或右)叶点与其左(或右)叶节点合并成包含点合并成包含2 2K-1个个键值的叶的叶节点,合并后,其双点,合并后,其双亲节点要减少一个点要减少一个键值,有可,有可能能导致双致双亲节点的合并。点的合并。删除算法:除算法:15253510203040,501010,1
45、53525,3510,153040,50 SHST索引集索引集顺序集序集B B+树实现树实现的主索引的主索引的主索引的主索引B B+树实现树实现的主索引包含如下的主索引包含如下的主索引包含如下的主索引包含如下2 2 2 2部分:索引集和部分:索引集和部分:索引集和部分:索引集和顺顺序集。序集。序集。序集。节点类型节点类型块中索引键数块中索引键数索引集索引集节点点节点类型节点类型节点类型节点类型块中索引键数块中索引键数块中索引键数块中索引键数前向指针前向指针前向指针前向指针后向指针后向指针后向指针后向指针顺序集序集节点点注:注:1.1.节点一般是一个物理点一般是一个物理块。2.2.元元组标识符符
46、tid,实际上是上是记录的地址,由的地址,由块号和号和记录在在块中中的指的指针号号组成(使用成(使用记录在在块中的指中的指针号号表示表示记录在在块中的位置,中的位置,好于直接用好于直接用记录在在块中的地址,方便中的地址,方便记录在在块内移内移动)。)。n n要找要找要找要找键值键值K KX X所所所所对应对应的的的的记录时记录时,从索引从索引从索引从索引树树的根开始,按下面的的根开始,按下面的的根开始,按下面的的根开始,按下面的规则规则自上而下地搜索:自上而下地搜索:自上而下地搜索:自上而下地搜索:1.1.若若若若K Kx xKKKn-1n-1,则则沿沿沿沿P Pn n所指的所指的所指的所指的
47、节节点向下搜索;点向下搜索;点向下搜索;点向下搜索;3.3.若若若若K Ki-1i-1 K Kx x K Ki i,则则沿沿沿沿P Pi i所所所所指的指的指的指的节节点向下搜索。点向下搜索。点向下搜索。点向下搜索。P0K0Ki-1PiKiKn-1PnKxKxKx注意:注意:索引集索引集节点中的点中的键值不一定不一定是文件中是文件中当前存在的当前存在的键值(仅起起“导航路航路标”的作用)的作用)。在搜索。在搜索过程中,即使程中,即使发现索引集索引集节点中的点中的键值等于要找的等于要找的键值,查找仍要按上述找仍要按上述规则进行下去。行下去。问题:若在某个索引集:若在某个索引集结点中找到了待点中找
48、到了待查找找记录相相应的索引的索引键值,是否,是否还要要继续遍遍历B+树,为什么?什么?索引集与索引集与顺序集的序集的联系系顺序集序集节点中的点中的键值要要满足如下关系:足如下关系:如果如果Pi=P0,则Ks0Ks1Ks1Ks0Kn-1;否否则:Ki-1Ks0Ks1Ks(n-1)Ki.nB+树实现的主索引稍加修改后也可用于次索引的主索引稍加修改后也可用于次索引(把(把顺序集序集结点的点的tid换成指成指针,因,因为一个一个键值可能可能对应多个多个tid)。nB+树实现的各种索引都是稠密索引(非稠密索引的概的各种索引都是稠密索引(非稠密索引的概念源于静念源于静态索引),提供了索引),提供了顺序搜
49、索的功能,序搜索的功能,这是它是它的的优点。点。n n搜索搜索搜索搜索B B+树树所需的所需的所需的所需的I/OI/O次数决定于其次数决定于其次数决定于其次数决定于其级级数。数。数。数。设索引属性不同索引属性不同键值的数目的数目为N,若索引若索引键不不是候是候选键,则记录数通常大于数通常大于N。B+树的的级数决定于数决定于N,而不是而不是记录数!数!假假设B+树索引部分共有索引部分共有L级,其秩,其秩为k,则各各级的最小的最小结点数依次点数依次为:1,2,2(k+1),2(k+1)L-2 L决定了找到所需决定了找到所需顺序集序集结点所需的点所需的I/O次数(次数(访问数据数据还要要额外的外的I/O),),例如例如k=99,N=2,000,000,有有L5,即至多即至多经过4 4次次I/O就可以找到相就可以找到相应的的顺序集序集结点。点。顺序集至少有序集至少有2(k+1)L-2个个结点。点。得出:得出:N2(k+1)L-2kL2+log(k+1)(N/2k)1+log(k+1)(N/2)n nB+树提供提供3 3种存取路径:种存取路径:1.1.通通过索引集索引集进行行树形搜索形搜索2.通通过顺序集序集进行行顺序搜索序搜索3.先通先通过索引找到入口,再沿索引找到入口,再沿顺序集序集顺序搜索序搜索
限制150内