《第五数据库的存储结构》由会员分享，可在线阅读，更多相关《第五数据库的存储结构（55页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章 数据库的存储结构数据库的存储结构冈郧供窟夷猾枷肋粱胶宠植喜缎寝追陇诸翌兢牌痊册肢彭替纳菏清去阵炒第五数据库的存储结构第五数据库的存储结构5.1 5.1 数据库存储介质的特点数据库存储介质的特点n n采用多级存储器，用的最多的辅存是磁盘。采用多级存储器，用的最多的辅存是磁盘。采用多级存储器，用的最多的辅存是磁盘。采用多级存储器，用的最多的辅存是磁盘。n n光盘由于速度和价格上的原因，近期无法取光盘由于速度和价格上的原因，近期无法取光盘由于速度和价格上的原因，近期无法取光盘由于速度和价格上的原因，近期无法取代硬盘。代硬盘。代硬盘。代硬盘。 n n磁带是顺序存取存储器，通常用作后备存储
2、磁带是顺序存取存储器，通常用作后备存储磁带是顺序存取存储器，通常用作后备存储磁带是顺序存取存储器，通常用作后备存储器。器。器。器。 数据库是大量、持久数据的集合，在现阶段数据库是大量、持久数据的集合，在现阶段用内存作为数据库的存储介质是不合适的用内存作为数据库的存储介质是不合适的。浚驶咆汹越歪讹传弗珠崭危弦宫缚催计庭贬蛆转写讨荤妊洋越涵很谩踞抠第五数据库的存储结构第五数据库的存储结构n活动头磁盘的存取时间由三部分组成：活动头磁盘的存取时间由三部分组成：寻道寻道时间时间、等待时间以及传输时间。、等待时间以及传输时间。n磁盘上的数据划分为大小相等的物理块。磁磁盘上的数据划分为大小相等的物理块。磁盘
3、与内存间的数据交换以物理块为单位。盘与内存间的数据交换以物理块为单位。以物理块为交换单位的优点：以物理块为交换单位的优点：以物理块为交换单位的优点：以物理块为交换单位的优点：1).1).1).1).减少减少减少减少I/OI/OI/OI/O的次数的次数的次数的次数，从而减少寻道和等待的时间。，从而减少寻道和等待的时间。，从而减少寻道和等待的时间。，从而减少寻道和等待的时间。2).2).2).2).减少间隙的数目减少间隙的数目减少间隙的数目减少间隙的数目，提高磁盘空间利用率。，提高磁盘空间利用率。，提高磁盘空间利用率。，提高磁盘空间利用率。物理快的大小由物理快的大小由物理快的大小由物理快的大小由O
4、SOSOSOS决定。决定。决定。决定。阀捐揣秤陇勿猎嫉刮拟枚微蒂吓坟蔷痰败秆试良莉湃啼蓟误垛贷悸刃会津第五数据库的存储结构第五数据库的存储结构n一般，在磁盘和内存之间设立缓冲区以解决一般，在磁盘和内存之间设立缓冲区以解决二者的速度不匹配问题。二者的速度不匹配问题。 由于有多个缓冲块可供申请使用，磁盘的读写由于有多个缓冲块可供申请使用，磁盘的读写操作和读写数据的处理可以重叠进行。操作和读写数据的处理可以重叠进行。读出：读出：i块块缓冲块缓冲块A处理：处理：处理处理A中中i块块i+1块块缓冲块缓冲块B i+2块块缓冲块缓冲块A处理处理B中中i+1块块绿档裴板邀捍恤娩应出砚耽处捡赢烘照困晃奋海贝刘渡
5、阴榷壬辩棘次景厌第五数据库的存储结构第五数据库的存储结构qq OS OS OS OS与与与与DBMSDBMSDBMSDBMS都有各自的缓冲区。都有各自的缓冲区。都有各自的缓冲区。都有各自的缓冲区。qq 不少不少不少不少DBMSDBMSDBMSDBMS采用采用采用采用延迟写延迟写延迟写延迟写与与与与提前读提前读提前读提前读技术，减少技术，减少技术，减少技术，减少I/OI/OI/OI/O，改善性能。，改善性能。，改善性能。，改善性能。签罪修琶遏酌傣匠妈炬貌喀兹官增谍桥虎纵完雄哭邓法章烛响膳贴勇励练第五数据库的存储结构第五数据库的存储结构5.2 5.2 记录的存储结构记录的存储结构n记录是目前商用数
6、据库的基本数据单元，有定记录是目前商用数据库的基本数据单元，有定长和变长之分。长和变长之分。n记录的存储结构记录的存储结构1.1.1.1.定位法定位法定位法定位法每个字段按其最大可能长度分配定长的每个字段按其最大可能长度分配定长的每个字段按其最大可能长度分配定长的每个字段按其最大可能长度分配定长的 位置位置位置位置LIbbbMINGbbbMALEbb196751218桃焊虑疗邮身戍谴怎坐牛囱胚伟裤邯访悯肾痔麓桨系衬捧翘否多犁天珊氨第五数据库的存储结构第五数据库的存储结构2.2.2.2.相对法相对法相对法相对法每个字段没有固定的长度，而是用特每个字段没有固定的长度，而是用特每个字段没有固定的长度
7、，而是用特每个字段没有固定的长度，而是用特 殊的字符分隔开殊的字符分隔开殊的字符分隔开殊的字符分隔开LI?MING?MALE?1967#问题：问题：字段中也需要用到这些分隔符时，如何进行字段中也需要用到这些分隔符时，如何进行表示？表示？汀箱染搁爸镇绣栽喊酥蘸逢王讥吓矿樊原释纶党掖雨屈袄捶贵煌小揍氨踪第五数据库的存储结构第五数据库的存储结构3.3.3.3.计数法计数法计数法计数法每个字段的开始加上表示该字段长度每个字段的开始加上表示该字段长度每个字段的开始加上表示该字段长度每个字段的开始加上表示该字段长度 的字段的字段的字段的字段02LI04MING04MALE041967问题：计数法对问题：计
8、数法对字段的实际长度字段的实际长度有什么要求？有什么要求？绿挪支夷缝谤人鸭狙铺靳锈饮棱撮未闭妄绑遥钉昧那蔓叛谤祟裳娠肌时呵第五数据库的存储结构第五数据库的存储结构5.2.2 记录在物理块上的分配记录在物理块上的分配n n磁盘上，记录必须分配到物理块中。磁盘上，记录必须分配到物理块中。磁盘上，记录必须分配到物理块中。磁盘上，记录必须分配到物理块中。 记录跨快存储（记录跨快存储（记录跨快存储（记录跨快存储（spannedspanned） 记录不垮块存储（记录不垮块存储（记录不垮块存储（记录不垮块存储（unspannedunspanned）设为物理块的有效空间大小，为固定长记设为物理块的有效空间大小
9、，为固定长记录的大小，若录的大小，若，则每个物理块可容纳的记录，则每个物理块可容纳的记录数为：数为：p=B/Rp称为块因子（称为块因子（Blocking Factor）。）。控朔丸已跌循登逛钧酪氓玉巴胚赎惕贬矽足斗逻阉汉蓟饰小镣世田构勾衣第五数据库的存储结构第五数据库的存储结构 记录一般不会刚好填满物理块，会留下不用的零头记录一般不会刚好填满物理块，会留下不用的零头空间：空间：BpRR 为了利用这部分空间，可以利用记录的跨块存储组为了利用这部分空间，可以利用记录的跨块存储组织织(spanned organization)。记录记录1记录记录2 2记录记录3 3记录记录4 4膘婴恬合室技镣诽乃蒂
10、晤亩缘讲起魁烯尖那贯挂话穆舶神某鞭食秽聪抹枕第五数据库的存储结构第五数据库的存储结构n n定长记录（跨块）定长记录（跨块）定长记录（跨块）定长记录（跨块）记录记录1记录记录2 2记录记录3 3记录记录4 4块块i记录记录4(剩余部剩余部分分)记录记录5 5记录记录6 6记录记录7 7块块i i+1伐宿嘘娱苔羚例扎祭碧画山焉睫面塞付帮厨抖晾挪略差矗肋笛睛琅信路稽第五数据库的存储结构第五数据库的存储结构n n变长记录（跨块）变长记录（跨块）变长记录（跨块）变长记录（跨块）记录记录1记录记录2 2记录记录3 3块块i记录记录3(剩剩余部分余部分)记录记录4 4记录记录5 5块块i i+1悼拿断蜘杆径
11、琶陶侗沏讲窄莲里荤钒翘安砚爱郧自簧树终嚼欧名磕榨倡纤第五数据库的存储结构第五数据库的存储结构5.2.3 物理块在磁盘上的分配物理块在磁盘上的分配 早期的早期的早期的早期的DBMSDBMSDBMSDBMS中，通常由操作系统分配数中，通常由操作系统分配数中，通常由操作系统分配数中，通常由操作系统分配数据库所需的物理块，逻辑上相邻的数据可能据库所需的物理块，逻辑上相邻的数据可能据库所需的物理块，逻辑上相邻的数据可能据库所需的物理块，逻辑上相邻的数据可能被分散到磁盘的不同区域。使得访问数据时，被分散到磁盘的不同区域。使得访问数据时，被分散到磁盘的不同区域。使得访问数据时，被分散到磁盘的不同区域。使得访
12、问数据时，性能下降。性能下降。性能下降。性能下降。 现代现代现代现代DBMSDBMSDBMSDBMS中，都改由中，都改由中，都改由中，都改由DBMSDBMSDBMSDBMS初始化时向操初始化时向操初始化时向操初始化时向操作系统一次性的申请所需的存储空间。作系统一次性的申请所需的存储空间。作系统一次性的申请所需的存储空间。作系统一次性的申请所需的存储空间。俯程杉挖媳稠干擎陡氨奏甲吧汞啮胺型拱否陕纬负狂春瓜袋膏肯涡链沧丑第五数据库的存储结构第五数据库的存储结构1 1、连续分配法（、连续分配法（contiguous allocationcontiguous allocation）2 2 2 2、链接
13、分配法（、链接分配法（、链接分配法（、链接分配法（linked allocationlinked allocationlinked allocationlinked allocation） 物理块未必分配在磁盘的连续存储空间上，物理块未必分配在磁盘的连续存储空间上，物理块未必分配在磁盘的连续存储空间上，物理块未必分配在磁盘的连续存储空间上，各物理块用指针链接，各物理块用指针链接，各物理块用指针链接，各物理块用指针链接，有利于文件的扩展，但有利于文件的扩展，但有利于文件的扩展，但有利于文件的扩展，但效率较差。效率较差。效率较差。效率较差。 将一个文件的块分配在磁盘的连续空间上，将一个文件的块分配
14、在磁盘的连续空间上，块的次序就是其存储的次序，块的次序就是其存储的次序，有利于顺序存取有利于顺序存取多块文件，不利于文件的扩充多块文件，不利于文件的扩充。礁睡折鉴荧昌送蚁外疆糯蘑骸锡蛙夕粘浮责毋助冈蔼量桩丝佩森瓦峪铱父第五数据库的存储结构第五数据库的存储结构3 3 3 3、簇集分配法（、簇集分配法（、簇集分配法（、簇集分配法（clustered allocationclustered allocationclustered allocationclustered allocation） 上述两种方法的结合。上述两种方法的结合。上述两种方法的结合。上述两种方法的结合。4 4 4 4、索引分配法（
15、、索引分配法（、索引分配法（、索引分配法（indexed allocationindexed allocationindexed allocationindexed allocation） 每个文件有一个逻辑块号与其物理块地址对每个文件有一个逻辑块号与其物理块地址对照的索引。照的索引。讹足飞萍容狸忙钒见寓膝杯崇类郎急戳凑夷踌枕菊贺走胶萤狮倡序墒斌冶第五数据库的存储结构第五数据库的存储结构n n数据压缩技术数据压缩技术数据压缩技术数据压缩技术1.1.1.1.消零或空格符法（消零或空格符法（消零或空格符法（消零或空格符法（null suppressionnull suppressionnull s
16、uppressionnull suppression） 例如，例如，例如，例如，bbbbbbbbbbbbbbbbbbbb可以用可以用可以用可以用#5#5#5#5表示；表示；表示；表示； 000000 000000 000000 000000可以用可以用可以用可以用66表示等。表示等。表示等。表示等。2.2.2.2.串型代替法（串型代替法（串型代替法（串型代替法（pattern pattern pattern pattern substitutionsubstitutionsubstitutionsubstitution） 对反复出现的字符串，可以用一个对反复出现的字符串，可以用一个对反复出现的
17、字符串，可以用一个对反复出现的字符串，可以用一个省略符代替。省略符代替。省略符代替。省略符代替。吩杉菱掐昭目塌探婆晌奠钥疙悯矾谐繁锥琼震阶培筋咨扒构捎蹦山耻膏嘘第五数据库的存储结构第五数据库的存储结构例如，串型表如右：例如，串型表如右：例如，串型表如右：例如，串型表如右：IBM PC/XT0000#原始数据原始数据IBM PC/XT 00001IBM PC/XT 00002压缩数据压缩数据#1#2仿封夜悄慑透插骏柳箔酋跪郑古逗消评簧错肩辞丰子疯挺委帆痘淳皖俺嘎第五数据库的存储结构第五数据库的存储结构3.3.3.3.索引法（索引法（索引法（索引法（indexingindexingindexing
18、indexing） 串行代替法的变种，对重复出现的串行，串行代替法的变种，对重复出现的串行，串行代替法的变种，对重复出现的串行，串行代替法的变种，对重复出现的串行，单独存储，在用到这些串行的地方，单独存储，在用到这些串行的地方，单独存储，在用到这些串行的地方，单独存储，在用到这些串行的地方，用指针用指针用指针用指针引用引用引用引用它。它。它。它。砧隋龙折染安陶悠盐湿能鲜发茧澄枉凤味彝介喘朋待普晾籽努呀赘迫僧女第五数据库的存储结构第五数据库的存储结构索引法示例：索引法示例：BeijingNanjingShanghaiCITYCITY表表SHOP#CITY0001Nanjing0002Nanjin
19、g0003Nanjing0004Shanghai原始数据原始数据0005ShanghaiSHOP#CITY0001000200030004压缩数据压缩数据0005问题：问题：问题：问题：索引法对串型的长度有什么要求？索引法对串型的长度有什么要求？索引法对串型的长度有什么要求？索引法对串型的长度有什么要求？择怎近州涵劣卢邑谗揉毛尹怀找昭何跨腊扯任卫众单舱凄龄浮闺左犬鄙嚏第五数据库的存储结构第五数据库的存储结构5.3 5.3 文件结构和存取路径文件结构和存取路径5.3.1 5.3.1 5.3.1 5.3.1 访问文件的方式访问文件的方式访问文件的方式访问文件的方式 传统的数据模型都以记录为基础，记
20、录的集合构成传统的数据模型都以记录为基础，记录的集合构成传统的数据模型都以记录为基础，记录的集合构成传统的数据模型都以记录为基础，记录的集合构成文件。文件须按一定的结构组织和存储记录，按一定文件。文件须按一定的结构组织和存储记录，按一定文件。文件须按一定的结构组织和存储记录，按一定文件。文件须按一定的结构组织和存储记录，按一定的存取路径访问有关记录。的存取路径访问有关记录。的存取路径访问有关记录。的存取路径访问有关记录。 对数据库的操作最终要落实到对文件的操作。对数据库的操作最终要落实到对文件的操作。对数据库的操作最终要落实到对文件的操作。对数据库的操作最终要落实到对文件的操作。 文件结构及其
21、所提供的存储路径直接影响数据访问文件结构及其所提供的存储路径直接影响数据访问文件结构及其所提供的存储路径直接影响数据访问文件结构及其所提供的存储路径直接影响数据访问的速度，通常针对不同的数据访问采用不同的文件结的速度，通常针对不同的数据访问采用不同的文件结的速度，通常针对不同的数据访问采用不同的文件结的速度，通常针对不同的数据访问采用不同的文件结构。构。构。构。丝敌治嚏码对环酌肖议栽呸帝然图赊捂帧宋糜讼旭肯撑坚斜啸耶衔苛邮鞍第五数据库的存储结构第五数据库的存储结构 1.1.1.1.查询文件的全部或相当多的记录（查询文件的全部或相当多的记录（查询文件的全部或相当多的记录（查询文件的全部或相当多的
22、记录（15%15%15%15%）2.2.2.2.查询某一特定记录查询某一特定记录查询某一特定记录查询某一特定记录3.3.3.3.查询某些记录查询某些记录查询某些记录查询某些记录4.4.4.4.范围查询范围查询范围查询范围查询5.5.5.5.记录的更新记录的更新记录的更新记录的更新文件访问方式按设计文件结构的观点分文件访问方式按设计文件结构的观点分文件访问方式按设计文件结构的观点分文件访问方式按设计文件结构的观点分5 5 5 5类类类类舰蔽候酋蛰纷苞鞍巧自账诺譬焊诛演晰羹铲铂齐眶钮措慑臼杰剪庙毡壤知第五数据库的存储结构第五数据库的存储结构5.3.2 5.3.2 5.3.2 5.3.2 数据库对文
23、件的要求数据库对文件的要求数据库对文件的要求数据库对文件的要求 一些一些一些一些DBMSDBMSDBMSDBMS就以就以就以就以OSOSOSOS的的文件管理系统作为的的文件管理系统作为的的文件管理系统作为的的文件管理系统作为其物理层的基础，更多的其物理层的基础，更多的其物理层的基础，更多的其物理层的基础，更多的DBMSDBMSDBMSDBMS不用不用不用不用OSOSOSOS的文件的文件的文件的文件管理系统，而是独立设计其存储结构。原因管理系统，而是独立设计其存储结构。原因管理系统，而是独立设计其存储结构。原因管理系统，而是独立设计其存储结构。原因如下：如下：如下：如下：qq 传统文件系统不能提
24、供实现传统文件系统不能提供实现传统文件系统不能提供实现传统文件系统不能提供实现DBMSDBMSDBMSDBMS功能所需的附功能所需的附功能所需的附功能所需的附加信息。加信息。加信息。加信息。DBMSDBMSDBMSDBMS为了实现其功能，须在文件目录、为了实现其功能，须在文件目录、为了实现其功能，须在文件目录、为了实现其功能，须在文件目录、文件描述块、物理块等部分附加一些信息。文件描述块、物理块等部分附加一些信息。文件描述块、物理块等部分附加一些信息。文件描述块、物理块等部分附加一些信息。qq 传统文件系统主要面向批处理，数据库系统要传统文件系统主要面向批处理，数据库系统要传统文件系统主要面向
25、批处理，数据库系统要传统文件系统主要面向批处理，数据库系统要求即时访问、动态修改。这就要求文件的结构能求即时访问、动态修改。这就要求文件的结构能求即时访问、动态修改。这就要求文件的结构能求即时访问、动态修改。这就要求文件的结构能适应数据的动态变化，提供快速访问路径。适应数据的动态变化，提供快速访问路径。适应数据的动态变化，提供快速访问路径。适应数据的动态变化，提供快速访问路径。断嫌糊死爬橙歪很牡芝锰忆翌勾串矢幂挑陶蠢巴赏炙咯哥羞命蒜骚适瓮蛊第五数据库的存储结构第五数据库的存储结构qq 传统文件系统服务对象特殊，用途单一，共享传统文件系统服务对象特殊，用途单一，共享传统文件系统服务对象特殊，用途
26、单一，共享传统文件系统服务对象特殊，用途单一，共享度低；数据库中的文件供所有用户共享，有些用度低；数据库中的文件供所有用户共享，有些用度低；数据库中的文件供所有用户共享，有些用度低；数据库中的文件供所有用户共享，有些用途甚至是不可知的。途甚至是不可知的。途甚至是不可知的。途甚至是不可知的。qq 减少减少减少减少DBMSDBMSDBMSDBMS对对对对OSOSOSOS的依赖，提高的依赖，提高的依赖，提高的依赖，提高DBMSDBMSDBMSDBMS的可移植性。的可移植性。的可移植性。的可移植性。qq 传统文件系统一旦建立以后，数据量比较稳定；传统文件系统一旦建立以后，数据量比较稳定；传统文件系统一
27、旦建立以后，数据量比较稳定；传统文件系统一旦建立以后，数据量比较稳定；数据库中文件的数据量变化较大。数据库中文件的数据量变化较大。数据库中文件的数据量变化较大。数据库中文件的数据量变化较大。杏薛廷耻掘爱草搜痔堑门棘煽墓棒亩鸭场甫避射程缺扬等府湾热搞燎娘任第五数据库的存储结构第五数据库的存储结构5.3.3 5.3.3 5.3.3 5.3.3 文件的基本类型文件的基本类型文件的基本类型文件的基本类型 不同类型的访问各有其使用的文件结构和不同类型的访问各有其使用的文件结构和存取路径。存取路径。DBMSDBMS通常提供多种文件结构，供数通常提供多种文件结构，供数据库设计者选用。据库设计者选用。1.1.
28、堆文件（堆文件（heap fileheap file）2.2.直接文件（直接文件（direct filedirect file）3.3.索引文件（索引文件（indexed fileindexed file）暑斋酌喳驰雹涯腿镰桌浸涡帧管脏且狗挟幕达疡乞者液挤摆皿侧彩谍祷踩第五数据库的存储结构第五数据库的存储结构n n最简单、最早使用的文最简单、最早使用的文最简单、最早使用的文最简单、最早使用的文件结构。记录按其插入件结构。记录按其插入件结构。记录按其插入件结构。记录按其插入的先后次序存放（的先后次序存放（的先后次序存放（的先后次序存放（所有所有所有所有记录在物理上不一定相记录在物理上不一定相记录
29、在物理上不一定相记录在物理上不一定相邻接邻接邻接邻接）n n堆文件插入容易、查找堆文件插入容易、查找堆文件插入容易、查找堆文件插入容易、查找不方便（不方便（不方便（不方便（所提供的唯一所提供的唯一所提供的唯一所提供的唯一存取路径就是顺序搜索存取路径就是顺序搜索存取路径就是顺序搜索存取路径就是顺序搜索）堆堆文文件件记录记录1 1记录记录6 6记录记录2 2记录记录1 1记录记录2 2记录记录3 3记录记录5 5记录记录6 61.1.1.1.堆文件堆文件堆文件堆文件记录记录4 4怀骚疽烫肚续改选孪渔鲤陕抓型嘻搽纫华县剖羊冬劣巍砒亲恭笔苹辰谈舜第五数据库的存储结构第五数据库的存储结构n n适于访问全
30、部或相当多的记录，对于其它类访问效率适于访问全部或相当多的记录，对于其它类访问效率适于访问全部或相当多的记录，对于其它类访问效率适于访问全部或相当多的记录，对于其它类访问效率较低。较低。较低。较低。（设文件记录数为（设文件记录数为（设文件记录数为（设文件记录数为N N N N，查找某一记录的平均访问，查找某一记录的平均访问，查找某一记录的平均访问，查找某一记录的平均访问次数为次数为次数为次数为N+1/2N+1/2N+1/2N+1/2）n n若堆文件的记录按检索属性排序，可用二分查找法。若堆文件的记录按检索属性排序，可用二分查找法。若堆文件的记录按检索属性排序，可用二分查找法。若堆文件的记录按检
31、索属性排序，可用二分查找法。（但要以排序为代价）（但要以排序为代价）（但要以排序为代价）（但要以排序为代价）健监冲蛤帐釉搜运混诊就圃民判墓唾氟稳俯枕体孰段违拒蚌捡羊玛返枫具第五数据库的存储结构第五数据库的存储结构堆堆文文件件记录记录1 1记录记录3 3记录记录5 5记录记录6 6记录记录4 4记录记录7 7记录记录8 8记录记录2 2 假设，要删除右图堆文件中假设，要删除右图堆文件中的第的第2，4，6条数据记录。条数据记录。 直接删除这三条记录的情况直接删除这三条记录的情况如右图所示。如右图所示。 带来什么问题？带来什么问题？n n 删除记录较麻烦删除记录较麻烦删除记录较麻烦删除记录较麻烦 空
32、间回收问题，后续记录空间回收问题，后续记录空间回收问题，后续记录空间回收问题，后续记录需搬移，影响对文件的操作效需搬移，影响对文件的操作效需搬移，影响对文件的操作效需搬移，影响对文件的操作效率。率。率。率。毛伙讼缨饭律围酋一卞曲硫撇咬捞沮朋挖沾蚌互镁褒爹洛锥驼且饲合身叔第五数据库的存储结构第五数据库的存储结构作删除作删除标记标记堆堆文文件件记录记录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
33、 1记录记录3 3记录记录5 5记录记录7 7记录记录8 8集中删除集中删除记录，并记录，并进行记录进行记录重排重排 解决方法解决方法碳惧拖钩耀窜需尽葱凋鬼豢歹质糟伞君丑矗俭理贝痛扁辣瘁葡栗哎娠碾话第五数据库的存储结构第五数据库的存储结构2.2.2.2.直接文件直接文件直接文件直接文件 直接文件中，将记录的某一属性用散列函数直直接文件中，将记录的某一属性用散列函数直直接文件中，将记录的某一属性用散列函数直直接文件中，将记录的某一属性用散列函数直接映射成记录的地址，被散列的属性称为散列键。接映射成记录的地址，被散列的属性称为散列键。接映射成记录的地址，被散列的属性称为散列键。接映射成记录的地址，
34、被散列的属性称为散列键。Student(SNO,SNAME,SEX,BIRTHDATE,DEPT)Student(SNO,SNAME,SEX,BIRTHDATE,DEPT)散列函数散列函数 H(SNO)=Address900412900412李林李林计算机系计算机系 H(900412900412)=addraddr存储空间存储空间900412900412李林李林计算机系计算机系币呜勤援卑耐刘羌迭嫁庶泵冬厂惮嗽袭哑踊虽津蔷举喊荫驯制围闷浪棚蚌第五数据库的存储结构第五数据库的存储结构qq 键所映射的地址范围固定键所映射的地址范围固定键所映射的地址范围固定键所映射的地址范围固定（地址范围设的太大或（
35、地址范围设的太大或（地址范围设的太大或（地址范围设的太大或太小都不好太小都不好太小都不好太小都不好, , , ,为什么？为什么？为什么？为什么？）。上述原因导致直接文件目前在数据库系统中使用不多。上述原因导致直接文件目前在数据库系统中使用不多。上述原因导致直接文件目前在数据库系统中使用不多。上述原因导致直接文件目前在数据库系统中使用不多。直接文件存在的问题：直接文件存在的问题：直接文件存在的问题：直接文件存在的问题：qq 地址重叠问题地址重叠问题地址重叠问题地址重叠问题（处理地址重叠增加了开销）（处理地址重叠增加了开销）（处理地址重叠增加了开销）（处理地址重叠增加了开销）。qq 直接文件只对散
36、列键的访问有效。直接文件只对散列键的访问有效。直接文件只对散列键的访问有效。直接文件只对散列键的访问有效。qq 不便于处理变长记录。不便于处理变长记录。不便于处理变长记录。不便于处理变长记录。qq 对于通用的对于通用的对于通用的对于通用的DBMSDBMSDBMSDBMS很难找到通用的散列函数。很难找到通用的散列函数。很难找到通用的散列函数。很难找到通用的散列函数。寅躲提念棘辕蹈迅的趾舱荒馁动伤驴傻伪勇羊钝扩畅淑陈斑律私赎脯穆否第五数据库的存储结构第五数据库的存储结构3.3.3.3.索引文件索引文件索引文件索引文件 索引相当于一个映射机构，把关系中相应记录索引相当于一个映射机构，把关系中相应记录
37、的某个（些）属性的键值转换为该记录的存储地的某个（些）属性的键值转换为该记录的存储地址（或地址集）。址（或地址集）。addr1addr2addr3SNOSNOAddressAddress学生表的索引文件学生表的索引文件900412900412addr2900417900417addr1900418900418addr3存储空间存储空间900418900418周力周力计算机系计算机系900412900412李林李林计算机系计算机系900417900417陈燕陈燕计算机系计算机系曼驶脖狂回茧夸白姻富谎破胯韵叶沸亦涯拯翅慢幽雏髓匡芹蠕甥篮咏乎抓第五数据库的存储结构第五数据库的存储结构n n索引与散列
38、的区别索引与散列的区别索引与散列的区别索引与散列的区别索引文件有记录才占用索引文件有记录才占用索引文件有记录才占用索引文件有记录才占用 存储空间，使用散列空文件也占用全部文件空间。存储空间，使用散列空文件也占用全部文件空间。存储空间，使用散列空文件也占用全部文件空间。存储空间，使用散列空文件也占用全部文件空间。n n索引本省占用空间，但索引一般较记录小得多索引本省占用空间，但索引一般较记录小得多索引本省占用空间，但索引一般较记录小得多索引本省占用空间，但索引一般较记录小得多 针对非散列键和非索引属性的访问，都不能有效发挥直针对非散列键和非索引属性的访问，都不能有效发挥直接文件或索引文件的优势。
39、散列或索引失效时，两者谁的访接文件或索引文件的优势。散列或索引失效时，两者谁的访问代价更大？问代价更大？首镊眠鹃奴乘恫蝗杖不岭页潘莫躲巾猎姥奇喝锥绰蕉段年丢祸荔炭兢豆蕊第五数据库的存储结构第五数据库的存储结构1.1.1.1.主索引主索引主索引主索引以主键为索引键以主键为索引键以主键为索引键以主键为索引键(primary index)(primary index)(primary index)(primary index)。2.2.2.2.次索引次索引次索引次索引以非主键为索引键以非主键为索引键以非主键为索引键以非主键为索引键(secendary (secendary (secendary (s
40、ecendary index)index)index)index)，建立次索引可以提高查询的效率，但增，建立次索引可以提高查询的效率，但增，建立次索引可以提高查询的效率，但增，建立次索引可以提高查询的效率，但增加了索引维护的开销。加了索引维护的开销。加了索引维护的开销。加了索引维护的开销。3.3.3.3.倒排文件倒排文件倒排文件倒排文件主索引主索引主索引主索引+ + + +次索引的极端情况（文件次索引的极端情况（文件次索引的极端情况（文件次索引的极端情况（文件的所有属性上都建立索引），有利于多属性值的的所有属性上都建立索引），有利于多属性值的的所有属性上都建立索引），有利于多属性值的的所有属性
41、上都建立索引），有利于多属性值的查找，但数据更新时开销很大。查找，但数据更新时开销很大。查找，但数据更新时开销很大。查找，但数据更新时开销很大。位摆伍掖遁淮搜揖饥悄欧乓涤蟹镜哄然铅赣替整蛰却烦娄彤矢谎挝枚众漾第五数据库的存储结构第五数据库的存储结构 为了便于检索，索引项总是按索引键排序。为了便于检索，索引项总是按索引键排序。为了便于检索，索引项总是按索引键排序。为了便于检索，索引项总是按索引键排序。 受按门牌号找住户的启示（受按门牌号找住户的启示（受按门牌号找住户的启示（受按门牌号找住户的启示（住户在住户在住户在住户在“ “物理物理物理物理” ”上上上上按门牌号码排序按门牌号码排序按门牌号码排
42、序按门牌号码排序），提出），提出），提出），提出非稠密索引非稠密索引非稠密索引非稠密索引。 注意：索引项注意：索引项注意：索引项注意：索引项 记录记录记录记录, , , ,并不是文件中的记录并不是文件中的记录并不是文件中的记录并不是文件中的记录按索引键排序按索引键排序按索引键排序按索引键排序文件中的记录按索引键排序吗？文件中的记录按索引键排序吗？文件中的记录按索引键排序吗？文件中的记录按索引键排序吗？娟婚凄祸傈氰捡乃泥蒂嗣毛兽闲绍挫促愁应禾唇烷雕疵庚燥挞玄急出与魂第五数据库的存储结构第五数据库的存储结构n非稠密索引与稠密索引非稠密索引与稠密索引1.1.不为每个键值设立索引项的索引不为每个键值设
43、立索引项的索引非稠密索引非稠密索引2.2.可以节省索引的存储空间，代价是文件要按索引可以节省索引的存储空间，代价是文件要按索引键排序键排序3.3.对一个文件，只能为一个索引键（一般为主键）对一个文件，只能为一个索引键（一般为主键）建立非稠密索引建立非稠密索引（为什么？）（为什么？）理珍榆甚幸呀炔既嘲矗芍赢斌综畴琳纂止丙予丰些涌酱滞俯消鲤贞漱漱孝第五数据库的存储结构第五数据库的存储结构4.4.4.4.非稠密索引中，若干个记录组成一个单元存储区，单非稠密索引中，若干个记录组成一个单元存储区，单非稠密索引中，若干个记录组成一个单元存储区，单非稠密索引中，若干个记录组成一个单元存储区，单元存储区中的记
44、录按索引键排序。元存储区中的记录按索引键排序。元存储区中的记录按索引键排序。元存储区中的记录按索引键排序。5.5.5.5.单元存储区装满后，可向溢出区溢出（用指针指向溢单元存储区装满后，可向溢出区溢出（用指针指向溢单元存储区装满后，可向溢出区溢出（用指针指向溢单元存储区装满后，可向溢出区溢出（用指针指向溢出区），但溢出太多时，指针链接次数增加，将导致数出区），但溢出太多时，指针链接次数增加，将导致数出区），但溢出太多时，指针链接次数增加，将导致数出区），但溢出太多时，指针链接次数增加，将导致数据库性能下降。据库性能下降。据库性能下降。据库性能下降。6.6.6.6.可以建立多级非稠密索引（可以建
45、立多级非稠密索引（可以建立多级非稠密索引（可以建立多级非稠密索引（通常最高一级索引应尽量通常最高一级索引应尽量通常最高一级索引应尽量通常最高一级索引应尽量保证可以常驻内存保证可以常驻内存保证可以常驻内存保证可以常驻内存）。）。）。）。 殃输梧剖苦媚摄猪湃驾突川溪陪致评谤悦菲纫捞粒湃矩富咎密仓首赞恶盲第五数据库的存储结构第五数据库的存储结构1 12 23 34 45 56 67 78 89 91010111112121211211341341671671821822032032112112232232292292312312372372412411313141415151616255255259
46、259267267271271单元存单元存单元存单元存储区储区储区储区1821824 42012012232237 7223223241241121225125127127116162712712892891919289289311311242431131141941928284194194304303131430430单单单单元元元元存存存存储储储储区区区区最最最最高高高高键键键键值值值值单单单单元元元元存存存存储储储储最最最最高高高高键键键键值值值值相相相相对对对对地地地地址址址址最最最最高高高高键键键键值值值值271271430430601601191191 201 201 249 24
47、9 251 251示例示例溢出区溢出区溢出区溢出区溢溢溢溢出出出出链链链链头头头头指指指指针针针针相对地址相对地址相对地址相对地址索引键索引键索引键索引键澈缄甫楷涣漾侮轰盆粟橇危镰几惑闯屿鬃爸遵畅鲜邓朝批卖淮羚幕僵铜亚第五数据库的存储结构第五数据库的存储结构1 12 23 34 45 56 67 78 89 91010111112121211211341341671671821822032032112112232232292292312312372372412411313141415151616255255259259267267271271单元存单元存单元存单元存储区储区储区储区182182
48、4 42012012232237 7223223241241121225125127127116162712712892891919289289311311242431131141941928284194194304303131430430单单单单元元元元存存存存储储储储区区区区最最最最高高高高键键键键值值值值单单单单元元元元存存存存储储储储最最最最高高高高键键键键值值值值相相相相对对对对地地地地址址址址最最最最高高高高键键键键值值值值271271430430601601191191 201 201 249 249 251 251溢出区溢出区溢出区溢出区溢溢溢溢出出出出链链链链头头头头指指指指
49、针针针针相对地址相对地址相对地址相对地址索引键索引键索引键索引键查找索引键为查找索引键为211的记录的存储地址的记录的存储地址2117211 巡钝赴部阅藻妻卷院寿返篓皮爬岳象粕鞠丫捣咸寐柳喀詹姬朵踪台膊蠕乐第五数据库的存储结构第五数据库的存储结构稠密索引稠密索引（dense indexdense index）n n每个键值对应一个索引项每个键值对应一个索引项每个键值对应一个索引项每个键值对应一个索引项稠密索引。稠密索引。稠密索引。稠密索引。n n稠密索引的稠密索引的稠密索引的稠密索引的预查找预查找预查找预查找功能功能功能功能（用记录的地址代替记录参与（用记录的地址代替记录参与（用记录的地址代替
50、记录参与（用记录的地址代替记录参与集合运算，减少集合运算，减少集合运算，减少集合运算，减少I/OI/OI/OI/O次数）次数）次数）次数）。n n索引溢出的问题索引溢出的问题索引溢出的问题索引溢出的问题 稠密索引中，每增加一个键值，就要增加一个索引项。稠密索引中，每增加一个键值，就要增加一个索引项。稠密索引中，每增加一个键值，就要增加一个索引项。稠密索引中，每增加一个键值，就要增加一个索引项。索引也会有溢出的可能。索引也会有溢出的可能。索引也会有溢出的可能。索引也会有溢出的可能。解决方法：解决方法：解决方法：解决方法：1.1.1.1.在每个索引块中预留发展的空间在每个索引块中预留发展的空间在每
51、个索引块中预留发展的空间在每个索引块中预留发展的空间 2. 2. 2. 2.建立索引溢出区建立索引溢出区建立索引溢出区建立索引溢出区馆锄宪厅坞奈趴狱北汤恋余靖村个尔浩肝凯觉何葱塌覆棵闭老注颓怯劈婉第五数据库的存储结构第五数据库的存储结构 例如：某个键值对应例如：某个键值对应例如：某个键值对应例如：某个键值对应100100100100个记录，且这个记录，且这个记录，且这个记录，且这100100100100个记录个记录个记录个记录分散在分散在分散在分散在100100100100个物理块中，虽然通过稠密索引可以一个物理块中，虽然通过稠密索引可以一个物理块中，虽然通过稠密索引可以一个物理块中，虽然通过
52、稠密索引可以一次获得这次获得这次获得这次获得这100100100100个地址，但仍然要访问个地址，但仍然要访问个地址，但仍然要访问个地址，但仍然要访问100100100100个物理块。个物理块。个物理块。个物理块。1.1.1.1.稠密索引中，稠密索引中，稠密索引中，稠密索引中，若键值不唯一，则在最低级索引中，若键值不唯一，则在最低级索引中，若键值不唯一，则在最低级索引中，若键值不唯一，则在最低级索引中，每个键值对应的可能是一个每个键值对应的可能是一个每个键值对应的可能是一个每个键值对应的可能是一个地址集（对应多个记录）地址集（对应多个记录）地址集（对应多个记录）地址集（对应多个记录）。如果这些
53、记录分散在不同的物理块内，。如果这些记录分散在不同的物理块内，。如果这些记录分散在不同的物理块内，。如果这些记录分散在不同的物理块内，稠密索引稠密索引稠密索引稠密索引的优点并不能体现出来的优点并不能体现出来的优点并不能体现出来的优点并不能体现出来（并不一定能减少（并不一定能减少（并不一定能减少（并不一定能减少I/OI/OI/OI/O）。）。）。）。烧腐慈撒蓄躇磁着摈今亿砰莱忘蓬净凸蝇庭颤萎拓坤月辣泌婶注八枉塑君第五数据库的存储结构第五数据库的存储结构采用簇集索引：把键值相同的记录在物理地址上集中存放。采用簇集索引：把键值相同的记录在物理地址上集中存放。采用簇集索引：把键值相同的记录在物理地址上
54、集中存放。采用簇集索引：把键值相同的记录在物理地址上集中存放。键键键键指针指针指针指针头块头块头块头块链块链块链块链块1 1 1 1链块链块链块链块n n n n索引区索引区索引区索引区2.2.2.2.解决方法解决方法解决方法解决方法簇集索引（簇集索引（簇集索引（簇集索引（clustering indexclustering indexclustering indexclustering index）类凰蛋吉掉拌庐砖嫂蛆帛繁晋厂涯剔情讳墓买胳惩霞寞颁享楞泄毛床掣圭第五数据库的存储结构第五数据库的存储结构3.3.3.3.缺点：缺点：缺点：缺点：建立簇集索引的开销较大，整个文件要重新组织。建立簇集
55、索引的开销较大，整个文件要重新组织。建立簇集索引的开销较大，整个文件要重新组织。建立簇集索引的开销较大，整个文件要重新组织。朝锯腺犬嘘构学拍硒绵撰涯勇僳铭菊啄张厕汹识摄离藤庇拥眷昌箭猩浴黍第五数据库的存储结构第五数据库的存储结构常用索引总结常用索引总结索引索引索引索引主索引主索引主索引主索引次索引次索引次索引次索引按主键排序按主键排序按主键排序按主键排序非稠密索引非稠密索引非稠密索引非稠密索引不按主键排序不按主键排序不按主键排序不按主键排序稠密索引稠密索引稠密索引稠密索引簇集索引簇集索引簇集索引簇集索引按索引键排序并簇集，按索引键排序并簇集，按索引键排序并簇集，按索引键排序并簇集， 稠密索引稠
56、密索引稠密索引稠密索引非簇集索引非簇集索引非簇集索引非簇集索引不按索引键排序，不按索引键排序，不按索引键排序，不按索引键排序， 稠密索引稠密索引稠密索引稠密索引码葛尿塔衙冲寅灸荒琶借署厚椿集画翔帝学颜南魏虾锭陈山除梳德寝闻蒜第五数据库的存储结构第五数据库的存储结构5.4 5.4 动态索引动态索引 从数据结构角度看：静态索引是个多分树；动态索从数据结构角度看：静态索引是个多分树；动态索引是一种平衡多分树（即引是一种平衡多分树（即B-B-树），常用树），常用B+树。树。 B+树的限制和规定：树的限制和规定：q 每个节点最多有每个节点最多有2k个键值，个键值，k称为称为B+树的秩树的秩(Order)
57、;q 根节点至少有一个键值，其它节点至少有根节点至少有一个键值，其它节点至少有k个键值个键值,节点内，键值有序存放节点内，键值有序存放;q 除叶节点无子女外，其它节点若有除叶节点无子女外，其它节点若有J个键值，则有个键值，则有J+1个子女个子女;q 所有叶节点都处于树的同一层，即树始终保持平衡。所有叶节点都处于树的同一层，即树始终保持平衡。雏摘绣诺毗茵芭猖踏氟凝搽此峦帽蝎效凤讥好腥惟错髓钾咒告珐援桌酣吐第五数据库的存储结构第五数据库的存储结构102015 从根向叶搜索，直至相应从根向叶搜索，直至相应叶节点，若该叶节点不满，则叶节点，若该叶节点不满，则将键值插入叶节点中；如叶节将键值插入叶节点中
58、；如叶节点已满（点已满（即已经有即已经有2K2K个键值个键值），），则将此叶节点分裂为二，叶节则将此叶节点分裂为二，叶节点分裂后，其双亲节点也必须点分裂后，其双亲节点也必须增加一个键值增加一个键值，若双亲节点不，若双亲节点不满，插入过程结束；否则双亲满，插入过程结束；否则双亲节点继续分裂为两个节点，如节点继续分裂为两个节点，如此继续直到插入过程中止。此继续直到插入过程中止。插入算法：插入算法：(K=1): 10，15，20，25，30，35，40，50101510, 15202520,25301015203025201015,253015253510203040,50超驴闰辉姜叫焊坪胰断侨仑凝
59、湃可顿孩歪呼衡毫辨符追僧专反高蜀熊襟遏第五数据库的存储结构第五数据库的存储结构 先从根节点出发，找到先从根节点出发，找到待删除键值所在叶节点；若待删除键值所在叶节点；若删除该键值后，叶节点中键删除该键值后，叶节点中键值数减为值数减为K-1K-1个，则个，则向其左向其左右兄弟叶节点借一个键值，右兄弟叶节点借一个键值，以保持每个叶节点存放键值以保持每个叶节点存放键值不少于不少于K K个个；若其左右叶节；若其左右叶节点都只有点都只有K K个键值，则可个键值，则可将将该叶节点与其左（或右）叶该叶节点与其左（或右）叶节点合并成包含节点合并成包含2K-12K-1个键值个键值的叶节点，合并后，其双亲的叶节点
60、，合并后，其双亲节点要减少一个键值节点要减少一个键值，有可，有可能导致双亲节点的合并。能导致双亲节点的合并。删除算法：删除算法：15253510203040,501010,153525,3510,153040,50真构聂包锻垢垮涝缀味篓困惜逼驰酒翻鲜玩丸怠凿作瑚赂嗓带硫桨绿亿釉第五数据库的存储结构第五数据库的存储结构 SHST索引集索引集顺序集顺序集B B+ +树实现的主索引树实现的主索引树实现的主索引树实现的主索引牵东简字瞪秀太绍赏裤板甜龄午葫颧兵先位惟镐早曰在辽女姐起季守撤匠第五数据库的存储结构第五数据库的存储结构B B B B+ + + +树实现的主索引包含如下树实现的主索引包含如下树实
61、现的主索引包含如下树实现的主索引包含如下2 2 2 2部分：索引集和顺序集。部分：索引集和顺序集。部分：索引集和顺序集。部分：索引集和顺序集。节点类型节点类型块中索引键数块中索引键数索引集节点索引集节点节点类型节点类型节点类型节点类型块中索引键数块中索引键数块中索引键数块中索引键数前向指针前向指针前向指针前向指针后向指针后向指针后向指针后向指针顺序集节点顺序集节点注：注：1.1.节点一般是一个物理块。节点一般是一个物理块。2.2.元组标识符元组标识符tidtid，实际上是记录的地址，由块号和，实际上是记录的地址，由块号和记录在块中记录在块中的指针号的指针号组成（使用组成（使用记录在块中的指针号
62、记录在块中的指针号表示记录在块中的位置，表示记录在块中的位置，好于直接用记录在块中的地址，方便记录在块内移动）。好于直接用记录在块中的地址，方便记录在块内移动）。恐瞧造宠捡磷俭憎劫尉毛材拽绘参暇待亥伸贿贮秧袖阁普勇岩潞拇鲤穆填第五数据库的存储结构第五数据库的存储结构n n要找键值要找键值要找键值要找键值K K K KX X X X所对应的记录时，从所对应的记录时，从所对应的记录时，从所对应的记录时，从索引树的根开始，按下面的规索引树的根开始，按下面的规索引树的根开始，按下面的规索引树的根开始，按下面的规则自上而下地搜索：则自上而下地搜索：则自上而下地搜索：则自上而下地搜索：1. 1.若若若若K
63、 Kx xKKKn-1n-1，则沿，则沿，则沿，则沿P Pn n所指的所指的所指的所指的节点向下搜索；节点向下搜索；节点向下搜索；节点向下搜索；3. 3.若若若若K Ki-1i-1 K Kx x K Ki i，则沿，则沿，则沿，则沿P Pi i所所所所指的节点向下搜索。指的节点向下搜索。指的节点向下搜索。指的节点向下搜索。 P0K0Ki-1PiKiKn-1PnKxKxKx疯兵返兽项旦耕思毋遏龚驭营毡蝉存饲月乡譬占漳签御裸窃择但尹暴幌润第五数据库的存储结构第五数据库的存储结构注意：注意：索引集节点中的键值索引集节点中的键值不一定不一定是文件中是文件中当前存在的键值（仅起当前存在的键值（仅起“导航
64、路标导航路标”的作用）。的作用）。在搜索过程中，即使发现索引集节点中的键在搜索过程中，即使发现索引集节点中的键值等于要找的键值，查找仍要按上述规则进值等于要找的键值，查找仍要按上述规则进行下去。行下去。问题：若在某个索引集结点中找到了待查找问题：若在某个索引集结点中找到了待查找记录相应的索引键值，是否还要继续遍历记录相应的索引键值，是否还要继续遍历B+B+树，为什么？树，为什么？达哺拯懈泞乘垛愁汐疹拙桓锁醋夯砸疵券英姿疗茅瑶梯草舒失崎蓬脾曳趾第五数据库的存储结构第五数据库的存储结构索引集与顺序集的联系索引集与顺序集的联系顺序集节点中的键值要满足如下关系：顺序集节点中的键值要满足如下关系：如果如
65、果Pi=P0，则，则Ks0Ks1Ks1Ks0Kn-1; ;否则：否则：Ki-1Ks0Ks1Ks(n-1)Ki .唐离部摹掸著狄蚂庚汤荚酗浑渺掏猩帅食栓赢纷鲤映掷姆咏瞎瓢侵暮雁秽第五数据库的存储结构第五数据库的存储结构nB B+ +树实现的主索引稍加修改后也可用于次索引树实现的主索引稍加修改后也可用于次索引（把顺（把顺序集结点的序集结点的tidtid换成指针，因为一个键值可能对应多个换成指针，因为一个键值可能对应多个tidtid）。nB B+ +树实现的各种索引都是稠密索引（非稠密索引的概树实现的各种索引都是稠密索引（非稠密索引的概念源于静态索引），提供了顺序搜索的功能，这是它念源于静态索引），
66、提供了顺序搜索的功能，这是它的优点。的优点。阂恭夜喘粗靛迭诈携煌切嗜奈全期嘉绘悄嘱赂存返达百扇拎李宠翼颇散葡第五数据库的存储结构第五数据库的存储结构n n搜索搜索搜索搜索B B B B+ + + +树所需的树所需的树所需的树所需的I/OI/OI/OI/O次数决定于其级数。次数决定于其级数。次数决定于其级数。次数决定于其级数。 设索引属性不同键值的数目为设索引属性不同键值的数目为N，若索引键不，若索引键不是候选键，则记录数通常大于是候选键，则记录数通常大于N。 B+树的级数决定于树的级数决定于N，而不是记录数！，而不是记录数！ 假设假设B+树索引部分共有树索引部分共有L级，其秩为级，其秩为k，则
67、各级，则各级的最小结点数依次为：的最小结点数依次为： 1，2，2(k+1)，2(k+1)L-2恨燎空调摔攫际歼垄炉盾菜曙沫惊泉枫痔口抚灰茁枚氯聂攒徘价驱握病曝第五数据库的存储结构第五数据库的存储结构 L L决定了找到所需顺序集结点所需的决定了找到所需顺序集结点所需的I/OI/O次数（访问次数（访问数据还要额外的数据还要额外的I/OI/O），例如），例如k=99k=99，N=2,000,000N=2,000,000，有，有L5L5，即至多经过，即至多经过4 4次次I/OI/O就可以找到相应的顺序集结点。就可以找到相应的顺序集结点。顺序集至少有顺序集至少有2(k+1)L-2个结点。个结点。得出：得出：N2(k+1)L-2kL2+log(k+1)(N/2k)1+ log(k+1)(N/2)粗届躇躁堤孔殉楞固嫩劝窑橡权蔓瘸赖追甚骗汪瘸她樟礼掀土竖探岸金急第五数据库的存储结构第五数据库的存储结构n nB B+ +树提供树提供3 3种存取路径：种存取路径：1.1.通过索引集进行树形搜索通过索引集进行树形搜索2.2.通过顺序集进行顺序搜索通过顺序集进行顺序搜索3.3.先通过索引找到入口，再沿顺序集顺先通过索引找到入口，再沿顺序集顺 序搜索序搜索粮守蔑厚衅逸舍浊卡忍伏崎坷胰肄盎智斩岂蔗去旬培昨翱伏开捞缩腐竹爱第五数据库的存储结构第五数据库的存储结构
