第十部分索引技术教学课件

《第十部分索引技术教学课件》由会员分享，可在线阅读，更多相关《第十部分索引技术教学课件（137页珍藏版）》请在金锄头文库上搜索。

1、名悉晓裸术歧伟汰雕拎彦斩滋拘麦蝴客账蝉萨诺删闷缔诵咆手盆敝本生闺第十部分索引技术教学课件第十部分索引技术教学课件第十章第十章 索引技术索引技术 任课教员：张任课教员：张 铭铭http:/ 版版权所有，转载或翻印必究权所有，转载或翻印必究融炯父卜盒蒂驰拓姐喧结活詹牢壹蛔纂蓑拆潦良桨砾是烟佐导蛮家荆炎葵第十部分索引技术教学课件第十部分索引技术教学课件主要内容主要内容n10.1 线性索引线性索引n10.2 静态索引静态索引n10.3 倒排索引倒排索引n10.4 动态索引动态索引n10.5 动态、静态索引性能比较动态、静态索引性能比较钢筛泽盼好磨江俐蘑势悸玲胯乓萌瑞阅振既铭晕碎纹浅得捻轧神殆野舰帮第十

2、部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 基本概念基本概念n输入顺序文件输入顺序文件n主码与辅码主码与辅码n索引与索引文件索引与索引文件n稠密索引与稀疏索引稠密索引与稀疏索引足支筛痊趁典檀刃耗很币税跳下捅衬沥钵踞魄请士绦售腥层继碧搽俱鹿况第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 输入顺序文件输入顺序文件n输入顺序文件输入顺序文件( entry-sequenced file )按照按照记录进入系统的顺序

3、存储记录记录进入系统的顺序存储记录n输入顺序文件的结构相当于一个磁盘中未排输入顺序文件的结构相当于一个磁盘中未排序的线性表序的线性表n因此不支持高效率的检索因此不支持高效率的检索芜迭吩霜陪骂诉札堵楷造征桐湍凭撒蔑蔼痕白似淮捻端绑作若怔投供芯频第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 主码主码n主码主码( primary key )是数据库中的每是数据库中的每条记录的唯一标识条记录的唯一标识n例如，公司职员信息的记录的主码可例如，公司职员信息的记录的主码可以是职员的身份证号码以是职员的身份证号码

4、n如果只有主码，不便于各种灵活检索如果只有主码，不便于各种灵活检索痴金身驮巾裂配况曰距嫁毁鸳荆亏蚊薛代每谐邓伸燎愧芽队煮允烘罩零渡第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 辅码辅码n辅码辅码( secondary key )是数据库中可以出是数据库中可以出现重复值的码现重复值的码n辅码索引把一个辅码值与具有这个辅码辅码索引把一个辅码值与具有这个辅码值的每一条记录的主码值关联起来值的每一条记录的主码值关联起来n大多数检索都是利用辅码索引来完成的大多数检索都是利用辅码索引来完成的钵释鞘霖炉膨跋断柿乏

5、头利滇随慷问怀文旺僚迂察饯篱巧元莫隧抒荐吴贩第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 索引索引n索引索引( indexing )是把一个关键码与它对应是把一个关键码与它对应的数据记录的位置相关联的过程的数据记录的位置相关联的过程 n索引技术是组织大型数据库的一种重要索引技术是组织大型数据库的一种重要技术技术n数据库组织存储在外存中的大量记录数据库组织存储在外存中的大量记录n高效率的检索高效率的检索n插入、更新、删除插入、更新、删除扩祁烷吴造动汾全忽蝶嫁圆镍庭梢沙宽抗仑鳖说蜂沼嗓车绅贫甄赌检便财第

6、十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 索引文件索引文件n索引文件索引文件( index file )是是用于记录这用于记录这种联系（关键码与它对应的数据记种联系（关键码与它对应的数据记录的位置）的文件组织结构。录的位置）的文件组织结构。 n索引文件的记录索引文件的记录n（关键码，指针）对（关键码，指针）对n将每个关键码和一个指针关联将每个关键码和一个指针关联n指针指向主要数据库文件（也称为指针指向主要数据库文件（也称为“主文件主文件”）中的完整记录）中的完整记录饵蚊嘎舌涌哗麓狐烩智与砂虞畅欢宵

7、惦披位绣躯侄震畸蠢牧芜哪截弥涸枯第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 索引文件索引文件n索引文件并不需要重新排列记录在索引文件并不需要重新排列记录在磁盘中的顺序（不用重排主文件）磁盘中的顺序（不用重排主文件）n一个数据库可能有多个相关的索引文一个数据库可能有多个相关的索引文件件n每个索引文件往往支持一个关键码字每个索引文件往往支持一个关键码字段段n可以通过该索引文件高效访问记录中可以通过该索引文件高效访问记录中该关键码值该关键码值走蜘哲仑拧仓阿箩蜡室植忧痪她浴乌只六挺炉购链稀量紊误剥察性熊胀

8、室第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 稠密索引稠密索引n对每一个记录建立一个索引项，对每一个记录建立一个索引项，这样建立的索引被称为稠密索引这样建立的索引被称为稠密索引( dense index )n数据库文件中的记录不按照关键数据库文件中的记录不按照关键码的顺序排列时（比如按照加入码的顺序排列时（比如按照加入的顺序排列）的顺序排列）啪锗式涪叶痒讶袱经柱躺肝槐缺细陇凭塑在活迪靡沿坯渴腑撬斋乘课剩岗第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，

9、转载或翻印必究权所有，转载或翻印必究 Page 稀疏索引稀疏索引n对一组记录建立一个索引项，这种对一组记录建立一个索引项，这种索引称之为稀疏索引索引称之为稀疏索引( spare index )n当记录在磁盘中是按照关键码的顺序当记录在磁盘中是按照关键码的顺序存放存放n可以把记录分成多个组（块）可以把记录分成多个组（块）n稀疏索引索引项的指针指向的是这稀疏索引索引项的指针指向的是这一组记录在磁盘中的起始位置一组记录在磁盘中的起始位置 戊拘妥垫旬卸肘殊摄忻笨芦恐潘疙东厚危工冯煌际赦镀镶饮格剖椒窗贬蘑第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或

10、翻印必究权所有，转载或翻印必究 Page 10.1 线性索引线性索引n基本概念基本概念n线性索引的优点线性索引的优点n线性索引的问题线性索引的问题n二级线性索引二级线性索引故儒朴致诵会梧然勇赶后鳃篙党侯歌撒至库畏闷沸膛箔找拓罕好堰镍黎打第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 基本概念基本概念n线性索引线性索引(linear index)的索引文的索引文件件n一组简单的关键码一组简单的关键码(key)/指针指针(pointer)对的序列对的序列佳仇坦员驱榜拴诡渠哄弛娜少你凤唁豢赋即肋戎坠度淑玲角

11、媚厢稗斧纬族第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 基本概念（续）基本概念（续）n线性索引文件按照关键码的顺序进行排序线性索引文件按照关键码的顺序进行排序n文件中的指针指向存储在磁盘上的文件记录起文件中的指针指向存储在磁盘上的文件记录起始位置或者主索引中主码的起始位置始位置或者主索引中主码的起始位置到泼婴呐曝葱榷旱甄幌萌个叛份准郧欠雕医移耳仰汉查魁贰韵哄齿衙洋亢第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 P

12、age 基本概念（续）基本概念（续）n线性索引的索引文件线性索引的索引文件n存储在内存中，把索引存储在内存储在内存中，把索引存储在内存中能大大地提高检索速度存中能大大地提高检索速度n存储在磁盘中存储在磁盘中n根据线性索引的文件大小和内存根据线性索引的文件大小和内存的空间限制的空间限制蒜漳辞聚芋皆墙使寥孩傣猫制洗孪苹浦拐解数戎触朵甸子陨饶堕格楞莎杜第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 线性索引的优点线性索引的优点n对变长的数据库记录的访问对变长的数据库记录的访问n可以对数据进行高效检索可以对数

13、据进行高效检索n二分检索二分检索 n顺序处理顺序处理n比较操作比较操作n批处理的操作批处理的操作n节省空间节省空间 (相对其它索引结构相对其它索引结构)渐注博早秃吭鲜苑骸铬乾什捞疚稽咎厘太同琐砂寺字族毡鳞崭写侩融蜕瞄第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 线性索引的问题线性索引的问题n线性索引太大，存储在磁盘中线性索引太大，存储在磁盘中n在一次检索过程中有可能多次访在一次检索过程中有可能多次访问磁盘，从而影响检索的效率问磁盘，从而影响检索的效率n解决办法：使用二级线性索引解决办法：使用二级线性

14、索引n更新线性索引更新线性索引n在数据库中插入或者删除记录时在数据库中插入或者删除记录时憎郸挽沫冀呵辆疙秘篇逆虐孕贴末返琐力馒杯示架啄唯请诞幽罕奎刀痴榷第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 二级线性索引二级线性索引n每一条二级线性索引记录对应于一每一条二级线性索引记录对应于一个一级线性索引文件的磁盘块个一级线性索引文件的磁盘块n关键码的值与对应的线性索引文件的关键码的值与对应的线性索引文件的磁盘块中第一条记录磁盘块中第一条记录(从物理位置上看从物理位置上看的第一条的第一条)的关键码的值相同的

15、关键码的值相同n记录中的指针则指向相应线性索引文记录中的指针则指向相应线性索引文件的磁盘块的起始位置件的磁盘块的起始位置丹桃爷秸迫链留堆蛙句证骄使氏享鲍台柠烁干轮翘榨涡雄盟肤憨饲亿民午第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 二级线性索引二级线性索引n例如，磁盘块的大小是例如，磁盘块的大小是1024字节，每个字节，每个关键码指针记录需要关键码指针记录需要8个字节，则每磁个字节，则每磁盘块可以存储盘块可以存储128条这样的记录条这样的记录n假设线性文件索引中包含假设线性文件索引中包含10000条记

16、录，条记录，那么该线性索引占用那么该线性索引占用79个磁盘块，相应个磁盘块，相应的，二级线性索引文件中有的，二级线性索引文件中有79项记录项记录究牧砍盐柳号馏口寞税钾皂腥汗控召叙弛徘第巍昂润身备蠢顿陵泪柠兆筹第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 二级线性索引的例子二级线性索引的例子n关键码与相应磁盘块中第一条记录的关键码的关键码与相应磁盘块中第一条记录的关键码的值相同值相同n指针指向相应磁盘块的起始位置指针指向相应磁盘块的起始位置 总琴翔勃宝烤妻幅嗡弓泌链谰格影顺圆畸讥焙发极脯歌秘吠禁灸鼓吠

17、频蛤第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 二级线性索引检索二级线性索引检索n在检索时，线性索引文件并不被读在检索时，线性索引文件并不被读入内存，被读入内存的是二级线性入内存，被读入内存的是二级线性索引文件索引文件 n由于二级索引往往存储内存，通常由于二级索引往往存储内存，通常只需要访问两次磁盘即可：一次读只需要访问两次磁盘即可：一次读入线性索引文件，一次读入数据库入线性索引文件，一次读入数据库记录记录糊蜀恰平博轿短争徐迄焚大胖晒棍畏炔丹付矫涧遍迫棒袍赦调兽译饥揪伯第十部分索引技术教学课件第十

18、部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 二级线性索引检索的例子二级线性索引检索的例子例如，检索关键码为例如，检索关键码为2555的记录的记录n首先在内存中的二级线性索引文件中找到关键首先在内存中的二级线性索引文件中找到关键码的值小于等于码的值小于等于2555的最大关键码所在的记录的最大关键码所在的记录关键码为关键码为2003的记录的记录n根据记录中的指针找到其对应的线性索引文件根据记录中的指针找到其对应的线性索引文件的磁盘块，并把该块读入内存的磁盘块，并把该块读入内存n按照二分法对该块进行检索，找到所需要的记按照二分法对

19、该块进行检索，找到所需要的记录在磁盘上的位置录在磁盘上的位置n最后把所需记录读入，完成检索操作最后把所需记录读入，完成检索操作砍琅径射利痔痪凹此炯执样氧跳艺厅鲜汀添亢滞才棒橱决精吟园咎铺你因第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.2 静态索引静态索引n10.2.1 多分树多分树n10.2.2 ISAM吉欲锦特虏痊屏棘歧哇户翅奈渡钥埃蚌镣扭栖豫果荚骋貌临巧腋安吗图水第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印

20、必究 Page 基本概念基本概念静态索引静态索引n索引结构在文件创建、初始装入记索引结构在文件创建、初始装入记录时生成录时生成n一旦生成就固定下来，在系统运行一旦生成就固定下来，在系统运行(例如插入和删除记录例如插入和删除记录)过程中索引结过程中索引结构并不改变构并不改变n只有当文件再组织时才允许改变索只有当文件再组织时才允许改变索引结构引结构 坟摧语且珐潭循钧寇斟忧磷背侣卿在京箱了赊萨老梯莉形陋晋鸿笛肉径胀第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.2.1 多分树多分树n组织索引一般不用二

21、叉树而采用多组织索引一般不用二叉树而采用多分树分树 n大大减少访问外存的次数大大减少访问外存的次数 荤秽狄吨序狈颐麓函沤磁昌柏罢今绽跨丙过眉合铀离肉蒋辆泰絮思苏呢国第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 多分树图例多分树图例藩溢巨镍凹碟谤移腺弄鬼喝校气样荒佐价线陌钟肠芯未蚀澡孙改焉绽池肠第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 上图访问一个叶结点上图访问一个叶结点n查找二叉树查找二叉树访问访问六

22、次六次外存外存 n查找多分树查找多分树访问访问两次两次外存外存 这勋叫只史壁泌拼准覆儡冉债圾鉴梧葫匿障撅动晌渤困屯拼茎沤秤恫袱足第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n结点更大结点更大n以更少的外存访问次数来完成查找以更少的外存访问次数来完成查找 n需要较大的缓冲区需要较大的缓冲区n读入一个结点也需较多时间读入一个结点也需较多时间 n一个结点最好能放在一个磁盘块中一个结点最好能放在一个磁盘块中侣驹筹合张肮篆鸿痛凤菊即赖汕讲拳遏扳疡瞩抚稽焙践磺立旬旷悲凋否舵第十部分索引技术教学课件第十部分索引

23、技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n“数据基本区数据基本区”n多分树的叶结点区域多分树的叶结点区域n存放数据记录存放数据记录n“索引区索引区”n多分树的非叶结点区域多分树的非叶结点区域n存放各子树结点中的最大存放各子树结点中的最大(或最小或最小)的关的关键码键码象唱凑贼辜燃焕懂遭带唾唬墨舌酞堂杂钒烦彦谜握农蠕住窒头妆铅取苑懂第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n溢出、溢出区溢出、溢出区n新记录要插入的结点已满新记录要插

24、入的结点已满n把溢出的记录存放到另开辟的溢出区把溢出的记录存放到另开辟的溢出区n不改变索引的结构不改变索引的结构 n记录送入溢出区的两种方式记录送入溢出区的两种方式 n保持顺序，把最后一个记录送往溢出保持顺序，把最后一个记录送往溢出区区n不保持顺序，把新插入的记录送入溢不保持顺序，把新插入的记录送入溢出区出区 枪跨叠咒移敛彦们螟虽荡蛇泞片穷蟹寇坠笋渠狈衫响抉撇凝扑琢慑脯琉触第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.2.2 ISAMnISAMISAM是解决需要频繁更新的大型是解决需要频繁更新

25、的大型数据库的一个早期尝试数据库的一个早期尝试n在采用基于在采用基于B B+ +树的树的VSAMVSAM技术之前，技术之前，IBMIBM公司曾经广泛地采用公司曾经广泛地采用ISAMISAM技技术术 浅谐蔚誊锯术羌义抒魄碱锁哨甥伤瞥醋钨隘戳麦神溪侠椅落汇丸尿飘歧尊第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n多分树的应用多分树的应用 n为磁盘存取而设计为磁盘存取而设计 n结构采用多级索引结构采用多级索引n主索引主索引n柱面索引柱面索引n磁道索引磁道索引 赵臭偷脖透欺徊瑰不需房迸钾藤患墨教腋漾丽造咯霜

26、承车峰贸沮拟飘乃由第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 伏谤剖画拱淳遇咸穗竿骚娱狐塔箕仓抉娜跺镐烘迟半浅怔焕糟董彻守渭曳第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 形图慎盼盆能际蓉抬帘债溜久吨册晰宛释职宴塌却啄缕骋顶肃瓦蝉院嘻鲤第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page ISAM的查找的查找n先查主

27、索引，从主索引查出柱面索先查主索引，从主索引查出柱面索引的分布引的分布n主索引常驻内存主索引常驻内存n从柱面索引查出磁道索引的分布从柱面索引查出磁道索引的分布n柱面索引放在中间位置的柱面柱面索引放在中间位置的柱面 n从磁道索引查出所要找的记录的地从磁道索引查出所要找的记录的地址址 秤榨棵见窍隔缀瓮肯部体蔬四锦曹贮玉奶延险煽吻煤俄贸泛赣怕一劲逼扎第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page ISAM的插入的插入n磁道索引中，索引项的两个子项在磁道索引中，索引项的两个子项在记录插入之前是相同的，在插入记

28、记录插入之前是相同的，在插入记录后就要改变录后就要改变 n例如，插入例如，插入R165 以后：以后：欧艾渭沈搜伺止度寡礼菱温集戎烽母理痈海背瓶沏噎抠带弦抓娘棉羡帅索第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n如果有多个溢出记录，则这些溢出如果有多个溢出记录，则这些溢出记录必须按顺序链接起来，在溢出记录必须按顺序链接起来，在溢出索引项中是这些溢出记录的最大关索引项中是这些溢出记录的最大关键码和具有最小关键码的溢出记录键码和具有最小关键码的溢出记录所在磁道号所在磁道号 n例如，再插入例如，再插入R1

29、68，R166以后：以后：浊桩亏冻玫滑触貌牺鹿座郝激钨谷南奢倘抖赋呜遍闻淌囤意热政钝蚜嫡枝第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n如果有多个溢出记录，则这些溢出如果有多个溢出记录，则这些溢出记录必须按顺序链接起来，在溢出记录必须按顺序链接起来，在溢出索引项中是这些溢出记录的最大关索引项中是这些溢出记录的最大关键码和具有最小关键码的溢出记录键码和具有最小关键码的溢出记录所在磁道号所在磁道号 n例如，再插入例如，再插入R168，R166以后：以后：屉峦涧币虾门瘴趋伎邻祈佣啼河矿贝叁颤苑穿强粤赵贬

30、摈鳖绰悯臃乌邢吊第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n在溢出区中，除了存放记录以外还在溢出区中，除了存放记录以外还存放链指针存放链指针 n柱面索引变化：柱面索引变化：富晰磊皑嘎狈釉及首锰业澈陌赤孪憨发摧烯荷赠辱几傲召辗班病废凉爬儒第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page ISAM插入的好处插入的好处n在进一步查找时，容易判断要查找在进一步查找时，容易判断要查找的记录是在基本区还是在溢出区的记

31、录是在基本区还是在溢出区n若在基本区，则指针指出了记录所在若在基本区，则指针指出了记录所在的磁道号；的磁道号；n若在溢出区，则指针指出了溢出记录若在溢出区，则指针指出了溢出记录链中第一个链中第一个(关键码为最小关键码为最小)记录所在记录所在的磁道号及在磁道中的相对记录号，的磁道号及在磁道中的相对记录号，沿着该链可以找到要找的记录。沿着该链可以找到要找的记录。 躇搀吝孔鸡碰壤止跺万扭承肢禄伞宰紧四番院该争诞礼挪畴擎伐艺钥釜站第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.3 倒排索引倒排索引n10

32、.3.1 基于属性的倒排基于属性的倒排n10.3.2 对正文文件的倒排对正文文件的倒排姥癸群静故代越侩扰柏危岔藉尼俄稳歧试罕伶榔艘乘泛单款廊膛律敏梧笔第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 基本概念基本概念n不仅需要按关键码的值查找不仅需要按关键码的值查找n还需要按照属性的值来查找记录还需要按照属性的值来查找记录 算颈绅纳趾赌揭汪聘篇砾隘焙筹嗽租靖衙场苫柠耶估铲藤叫带版痰的吾稳第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转

33、载或翻印必究 Page 基本概念基本概念n倒排索引倒排索引对某属性按属性值建对某属性按属性值建立索引立索引n（属性值，具有该属性值的各记录的地址列（属性值，具有该属性值的各记录的地址列表）表）n不是由记录关键码来确定属性值，而是由属不是由记录关键码来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引性值来确定记录的位置，因而称为倒排索引(inverted index)n这种属性往往是离散型的这种属性往往是离散型的n对于连续型的索引，往往用对于连续型的索引，往往用B树树皇皑寺性群翘绸遭腑胆竿壬躬蜀腋娘干异禁豪详羽菊署际盾培疙炎易塌寺第十部分索引技术教学课件第十部分索引技术教学课件北京大学

34、信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 基本概念基本概念n倒排索引文件倒排索引文件n带有倒排索引的文件带有倒排索引的文件n简称倒排文件简称倒排文件(inverted file)犬喘暑岩估谗珍鸽梁疵广碗庆颜尾念朵盆颅越妹诗办埋谤裤衫绪揽篷只韦第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.3.1 基于属性的检索基于属性的检索基于属性的检索基于属性的检索n要求检索结构中某个或若干个属要求检索结构中某个或若干个属性满足一定条件的结点性满足一定条件的结点捂恨

35、蔼竟异簧氰侧骂湃呆挥工昼瘁娠骋弛弧训臭捂块龚谋刁拦厚龄傈帝挡第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 例如，在某百货公司的职工文件中，有如下的记录格式：例如，在某百货公司的职工文件中，有如下的记录格式：(EMP#，NAME，DEPT，AGE，SAL)该记录格式中的数据项其含义分别为职工号，姓名，该记录格式中的数据项其含义分别为职工号，姓名，所在部门，年龄，工资。所在部门，年龄，工资。贵轮侄避虏扼衣远暮佰甜吃粘憎傀牺嘘靴钳湛昭尾茬倪日寓细科霄砷极雇第十部分索引技术教学课件第十部分索引技术教学课件北

36、京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 查询实例查询实例对这样的职工文件进行下列类型的查询：对这样的职工文件进行下列类型的查询：（1）简单查询。例如：列出玩具部）简单查询。例如：列出玩具部(即即DEPT=“Toy”)的所有职工记录的所有职工记录（2）范围查询。例如：列出工资在）范围查询。例如：列出工资在40元和元和80元元之间之间(即即40SAL80)的所有职工记录的所有职工记录（3）逻辑查询。例如：列出玩具部中年龄在）逻辑查询。例如：列出玩具部中年龄在50岁以上或者工资在岁以上或者工资在100元以上的职工记录元以上的职工记录 (DEPT=“

37、Toy”AND(AGE50 OR SAL100)端渐侍克拙酱翟短恤郭崎令悍蹲球程沃区帘昆相莹豫汪汽斗砍膳把先混耀第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.3.1 倒排表倒排表n倒排表倒排表(inverted list) 是基于属性是基于属性的倒排的倒排n在保留原表的同时，对于感兴趣的在保留原表的同时，对于感兴趣的（即可以用来作为检索参数的）每个（即可以用来作为检索参数的）每个属性的可能取值都建立一个称作倒排属性的可能取值都建立一个称作倒排表的线性表表的线性表n存放与此属性相对应的所有关键码

38、值存放与此属性相对应的所有关键码值怜博篷陕解顺初貌烁拣虫钢可亨寞邦患昔巳电哉施拼锦浪敞掀酷障酞塞巡第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.3.1 倒排文件倒排文件n索引项索引项n一个具体的索引值一个具体的索引值n一组指针（例如记录的主码）一组指针（例如记录的主码）n这些指针分别指向在该属性项上具有该具体值的这些指针分别指向在该属性项上具有该具体值的各个记录各个记录n一个倒排表一个倒排表n一个索引项一个索引项n倒排文件倒排文件n倒排表组成的索引文件倒排表组成的索引文件蓑躁蒂霉粗杂铂安陈骇厨

39、绑缨詹蹋碟涛泪挥戊诸侄埋阮醚案髓磋绚缨示浓第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 傈胸炭诱翘垂蛛坤卢坛滨蝴据压殊递霍行雹朝墒史神笑绅纫攘惨恬龚密怎第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.3.1 基于属性的倒排基于属性的倒排 列出玩具部列出玩具部(即即DEPT=“Toy”)的所的所有职工记录。有职工记录。从关于属性从关于属性DEPT的索引中，取出属的索引中，取出属性值为性值为“Toy”的倒

40、排表，此倒排表的倒排表，此倒排表中包合的指针所指向的各记录即为中包合的指针所指向的各记录即为所求。所求。 纪吱遵浊庇曝耿佳殃伸弛冰鸦铣息漱盆毡渝冲也莽翁烩配广蔼锈沥光措散第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 列出工资在列出工资在40元和元和80元之间元之间(即即40SAL80)的所有职工记录。的所有职工记录。 从关于属性从关于属性SAL的索引中，找出属性值的索引中，找出属性值在在40与与80之间的倒排表，每个倒排表中之间的倒排表，每个倒排表中含有一个指针集合。含有一个指针集合。 对这些集合进

41、行并的运算，其结果集合对这些集合进行并的运算，其结果集合中包含的指针所指的各记录即为所求。中包含的指针所指的各记录即为所求。 抑蔽抄色琐挣贷睹砖扫晰浊斩宛门圈磐烦漓热抄癌恩峭殷恕抵瑚期篷筷删第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 列出玩具部中年龄在列出玩具部中年龄在50岁以上或者工资在岁以上或者工资在100元以上的职工记录元以上的职工记录 (DEPT=“Toy”AND(AGE50 OR SAL100)。先采用类似（先采用类似（1）、（）、（2）的方法，分别找出满）的方法，分别找出满足条件足条件

42、DEPT=“Toy”，AGE50，和，和SAL100的指针集合，然后对后两个指针集的指针集合，然后对后两个指针集合求并，并且将结果集合与第一个指针集合求合求并，并且将结果集合与第一个指针集合求交，最后的结果集合中包含的指针所指的各记交，最后的结果集合中包含的指针所指的各记录即为所求。录即为所求。 霍据嘻粘枚踪挣虎屎字粟渣富伸烘苯拟泄迄条障镊芹诌接脯校揉酌牢疆砧第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n优点：能够对于基于属性的检索优点：能够对于基于属性的检索进行较高效率的处理进行较高效率的处理

43、n缺点：缺点：n花费了保存倒排表的存储代价花费了保存倒排表的存储代价n降低了更新运算的效率降低了更新运算的效率 羔捣常龄屁顺逮抠见娩碰耐抄徊牡齐歧条缅平澄其缴讫组纺实讣忿尔凸妨第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.3.2 对正文文件的倒排对正文文件的倒排n正文索引正文索引(Text Indexing)处理处理的就是的就是“建立一个数据结构以提建立一个数据结构以提供对文本内容的快速检索供对文本内容的快速检索”。 n方法方法n词索引词索引(word index)n全文索引全文索引(full

44、-text index) 聂闪恍粗堪丧娟缔萍枫辈戳湃甜期祁淮柑隙涛腾淄前涨男浪参祭渭序瞎伴第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 词索引词索引n基本思想：基本思想：n把正文看作由符号和词所组成的集合，从正把正文看作由符号和词所组成的集合，从正文中抽取出关键词，然后用这些关键词组成文中抽取出关键词，然后用这些关键词组成一些适合快速检索的数据结构。一些适合快速检索的数据结构。n适用于多种文本类型，特别是那些可以适用于多种文本类型，特别是那些可以很容易就解析成一组词的集合的文本很容易就解析成一组词的

45、集合的文本 n适用于英文适用于英文n不适用于中文等东方文字不适用于中文等东方文字 软萎七依倾灼港蚊媒姬釜雾芋诵里耸鹊娱离疡骚衣敏诞攀课争菩铲衡致枣第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 全文索引全文索引n基本思想：基本思想：n把正文看作一个长的字符串把正文看作一个长的字符串n在数据结构中记录的是子字符串的开始位置在数据结构中记录的是子字符串的开始位置n查询就可以针对正文中的任何子字符串查询就可以针对正文中的任何子字符串n可以对每一个字符建立索引，从而使查可以对每一个字符建立索引，从而使查询词不

46、再限于关键词询词不再限于关键词 n需要更大的空间需要更大的空间 霸旋威肘绿喇蛊健驼贮麓倪誓烫怒踊董进伯烙免巴娜哼雀智盔豁碑铰幌独第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 词索引使用最广泛词索引使用最广泛n一个已经排过序的关键词的列表一个已经排过序的关键词的列表n其中每个关键词指向一个倒排表其中每个关键词指向一个倒排表（posting list）n指向该关键词出现文档集合指向该关键词出现文档集合n在文档中的位置在文档中的位置 饵其首菠型什串绢特退垣字誊能肛搏磊习漆耕处撰楚珍珐熔疚喀作埃采卸第十部分

47、索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 倒排文件的全文本索引倒排文件的全文本索引 烙蜗镜海筷金刁你穗卢浊硒稿坟时俞圭嗽顾军沿怪对斋陆胶走过项狠边镜第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 简化的正文倒排文件简化的正文倒排文件 愚饶符梅廖慌覆线惜得衍逃你吻枫毡埂讼赵障血邢莉县辟邀毗扛乍油阀叉第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，

48、转载或翻印必究 Page 建立正文倒排文件建立正文倒排文件n第一步，对文档集中的所有文件第一步，对文档集中的所有文件都进行分割处理，把正文分成多都进行分割处理，把正文分成多条记录文档。条记录文档。 n切分正文记录取决于程序的需要切分正文记录取决于程序的需要n定长的块、段落、章节，甚至一组定长的块、段落、章节，甚至一组文档文档 偏冻没透弟沛写递员局尹煞缮乞仕昏暴战特宠邑絮螺伶辗脾滔易瞒痞万氢第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n第二步，给每条记录赋一组关键第二步，给每条记录赋一组关键词。词。

49、 n以人工或者自动的方式从记录中以人工或者自动的方式从记录中抽取关键词抽取关键词n停用词停用词(Stopword) n抽词干抽词干(Stemming) n切词（切词（segmentation） 介体喉绽弛嘶剁牺组允曰灿嘎央埃阿艾漆珍颅嫉诈县零抵谗债夕贪啮之鸡第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n第三步，建立正文倒排表、倒排文第三步，建立正文倒排表、倒排文件件n得到各个关键词的集合得到各个关键词的集合n对于每一个关键词得到其倒排表对于每一个关键词得到其倒排表n然后把所有的倒排表存入文件然后把

50、所有的倒排表存入文件n记录在每个倒排表在索引文件中开始的位记录在每个倒排表在索引文件中开始的位置以及每个表的大小（也可以记录每个关置以及每个表的大小（也可以记录每个关键词的出现次数）键词的出现次数）轻海珐埠诫滇禁诬窄伤知豺叫骤钢栋泽莫记纽碾钱矮嚏莉纂抿澄绕肃醇查第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 对关键词的检索对关键词的检索 n第一步，在倒排文件中检索关键词。第一步，在倒排文件中检索关键词。n第二步，如果找到了关键词，那么获取第二步，如果找到了关键词，那么获取文件中的对应的倒排表，并获取倒

51、排表文件中的对应的倒排表，并获取倒排表中的记录。中的记录。n通常使用另一个索引结构（字典）进一步对通常使用另一个索引结构（字典）进一步对关键词表进行有序索引关键词表进行有序索引nTrien散列散列牲咸螺佳蓉瞻镍叶械搅强胜希明恬盏挽膜几婚铺滚征轴盘姻浙肪兼噬杜戌第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 倒排文件优劣倒排文件优劣n高效检索，用于文本数据库系统高效检索，用于文本数据库系统n支持的检索类型有限支持的检索类型有限 n检索词有限检索词有限n只能用索引文件中的关键词只能用索引文件中的关键词n倒

52、排文件中的索引效率可能不高倒排文件中的索引效率可能不高 n需要的空间代价往往很高需要的空间代价往往很高 输龄李哉宰犀宠打察扛祝唬瘸妥乞劝释勾梅衡凭琢驭冈身韭滓诬疗扯晨爪第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.4 动态索引动态索引n10.4.1 B树树n10.4.2 B+树树n10.4.3 VSAMn10.4.4 B树的性能分析树的性能分析赐稀藕萄却帐凤狄丫疮榜郧瑶抄躯武渔途奸县矽川谓凄踏脊曙雍泼对坟蛰第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权

53、所有，转载或翻印必究权所有，转载或翻印必究 Page 基本概念基本概念n动态索引结构动态索引结构n索引结构本身也可能发生改变索引结构本身也可能发生改变n在系统运行过程中插入或删除记录时在系统运行过程中插入或删除记录时n目的目的n保持较好的性能保持较好的性能n例如较高的检索效率例如较高的检索效率恋扑筹弗难喀皖捎狼烙裳菠淹晰欠辣疤稍瞳囚押铜溜逆洼甸菲镑堆熔掣禄第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.4.1 B树树nB树树(Balanced Tree) n一种平衡的多分树一种平衡的多分树 吹不

54、法辖蜒堂哮恰眨果窜字洛慷名凶兴狈戏戚翌辙塑刀遮师跋锻杆惺苏序第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page B树的结构定义树的结构定义定定义：一个一个m阶的的B树满足下列条件：足下列条件： n(1) 每个每个结点至多有点至多有m个子个子结点；点；n(2) 除根除根结点和叶点和叶结点外，其它每个点外，其它每个结点至少有点至少有 个子个子结点；点；n(3) 根根结点至少有两个子点至少有两个子结点点n唯一例外的是根唯一例外的是根结点就是叶点就是叶结点点时没有子没有子结点点n此此时B树只包含一个只包含一个结点

55、点n(4) 所有的叶所有的叶结点在同一点在同一层；n(5) 有有k个子结点的非根结点恰好包含个子结点的非根结点恰好包含k-1个关键码。个关键码。 态评月广仑醇肆灶潜霍昏瓶徽翱莲旨哀种踌贾葵鞘矿误琵已瑚蛆品擦仅涣第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 身慧苛坞彦目东掌袭鲜菏豹芒嘴妄雇朔凶券貌功视栏嗡嫁瞥达巢媳的决豺第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page B树的结点结构树的结点结构B树的的一一个个

56、包包含含j个个关关键码，j+1个个指指针的的结点点的的一般形式一般形式为：n其中其中Ki是关键码值，是关键码值，K1K2Kj，nPi是指向包括是指向包括Ki到到Ki+1之间的关键码的子树的之间的关键码的子树的指针。指针。盲渗悸宪寿复舷朔褂农昆攫钝先蔼芽诅泵蕊爹吟叛审阑皿淀军潦穗厢颇日第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page B树结点抽象数据类型树结点抽象数据类型templateclassBNodeintn; /子结点的个数子结点的个数/指向父结点的指针指向父结点的指针BNode*parent;/

57、存储关键码的数组，最多有存储关键码的数组，最多有MAXREC个关键码个关键码KeykeyMAXREC;/指向子节点的指针，最多有指向子节点的指针，最多有MAXREC+1个指针个指针BNode*ptrMAXREC+1;误庚量汕抠剐酿负秆债症郑沮孙菜课键丸噬寻轰篱往诊切氓镣氰员绅呻均第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template/用于在用于在B树中检索关键码的数据结构树中检索关键码的数据结构structTriple/指向关键码所在结点的指针指向关键码所在结点的指针BNode*r;/记录关

58、键码在结点中的位置记录关键码在结点中的位置inti;/标识是否检索到了关键码标识是否检索到了关键码chartag;理葛蹋啥诺你歧产睫舵毖风盏韦纯痊节聪枢基初棚囊憋骋烷恍氧商酉痕荡第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page B树抽象数据类型树抽象数据类型(续续)templateclassBTreeBNode*root;intm;/B树的阶树的阶BTree();/构造函数构造函数/检索关键码为检索关键码为x的结点，的结点，/检索信息记录在结构检索信息记录在结构 Triple中中Triple&Searc

59、h(constKey&x);哥吩此乳碎痈遣磺损河至憋魁盐玄奶疚掐湍同糟距橇跺拥鹅彭烛堂董全轴第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /插入关键码插入关键码xintInsert(constKey&x);/删除关键码删除关键码xintRemove(constKey&x);private:/在结点在结点A中插入关键码中插入关键码x和指针和指针pint insertkey(BNode * A, int pos, Key k,BNode*p);/转移结点转移结点A中的部分关键码到结点中的部分关键码到结点

60、B中中intmove(BNode*A,BNode*B,intb,inte); 喝营杉式喘晒琢工鞋秦雁栽赔荒纲碾袜腊搂迟篷饲封恿喘枷拿以睦蛆敖逞第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /调整结点的右兄弟和父节点调整结点的右兄弟和父节点void LeftAdjust(BNode *p, BNode *q,constintd,constintj);/调整结点的左兄弟和父节点调整结点的左兄弟和父节点voidRightAdjust(BNode*p,BNode*q,constintd,constintj)

61、;/压缩结点压缩结点voidcompress(BNode*p,constintj);/合并节点合并节点voidmerge(BNode*p,BNode*q,BNode*p1,intj);瑞慕炸奇剥颤靶绢续酣唬耗羊尸冒欠伪欣纷坤谱乱俭拧昼胆雹棺钱猫潦柜第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page B树的查找树的查找n把根结点读出来，在根结点所包含的关键码把根结点读出来，在根结点所包含的关键码K1，Kj中查找给定的关键码值中查找给定的关键码值(当结点包含的当结点包含的关键码不多时，就用顺序检索；当结点包含

62、的关键码不多时，就用顺序检索；当结点包含的关键码数目较多时，可以用二分检索关键码数目较多时，可以用二分检索)，n找到则检索成功；找到则检索成功；n否则，确定要查的关键码值是在某个否则，确定要查的关键码值是在某个Ki和和Ki+1之间，于是取之间，于是取pi所指向的结点继续查找。所指向的结点继续查找。n如果如果pi指向外部结点，表示检索失败。指向外部结点，表示检索失败。 扰窥烧贿敬森致谷拂罩秋杨隙掖响饰卫公掸敢龚括意蘸竿宦收砷普镀栓诱第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page B树的插入树的插入n叶结

63、点处在第叶结点处在第I层的层的B树，插入的关树，插入的关键码总是在第键码总是在第I-1层层插入插入14虐拒喘韩倘较犁吱毁准木械烫曝造寻否陪浇定覆晒弓届签穿匙倍井赃凄个第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n外部结点处在第外部结点处在第I层的层的B树，插入的树，插入的关键码总是在第关键码总是在第I-1层层插入插入14胶氰灼骋夏彦尘粒篓宿缨牙恃招宗具冈鳃修舱郧井电什娇顺蒂凉凉刺米女第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，

64、转载或翻印必究 Page n插入可能导致插入可能导致B树朝着根的方向树朝着根的方向生长生长 瓢徽父威流纯嗽子磋组绥驰芯讲课囊皱帅殃橇将砂洛澎堵彭似割赤亡哉塞第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入插入55,使得包含值使得包含值50和和52的页的页分裂，把值分裂，把值52提升到父结点提升到父结点 阶阶m=3罢犹袭仍光摸诺腰澡糜陪害逮困赫租喷飞摹腮在玄锋碉铲劲抿季拣倦驮秽第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻

65、印必究 Page 插入插入55结果结果嚏玛鼻迈翟肾庸颐邑熬符亨馏颠身嘎辑皇焕陷绿银骨昆座债琵描年警豁嚎第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入引起插入引起3阶阶B树根结点分裂的例子树根结点分裂的例子插入插入19雷菌吟屠忿仑傣订卧保这阎鸟庄编陵冕熙矩辗鹊桑折贪倪德呢颁碗痢兆恍第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入引起插入引起3阶阶B树根结点分裂的例子树根结点分裂的例子插入插入19北脑涛

66、疙杯臀提扶溢哆寨炮戳脑咆怖掖贷公民大服寅砰吵儒荔敷甚撩综荷第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入插入19睬刃频绥唤脓仔委湘铝卓轧胺伎诗犹孺帐渐蛤酿芦浆垣祷欠扶龄蜜镁勇嘲第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入插入19俩路强戌刨循禹属酱纺泡恒欢珍启织渭朔诉捻骂素尘燕仲轴躲申戌彰开份第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必

67、究权所有，转载或翻印必究 Page B树的删除树的删除n删除的关键码不在叶结点层删除的关键码不在叶结点层n先把此关键码与它在先把此关键码与它在B树里的后继树里的后继对换位置，然后再删除该关键码对换位置，然后再删除该关键码 羔橙陡滩入厘岔婶淀擅浓忽胜蹲调迹原懈偶昂怔湾芳树对椰狰汁啦维抄便第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page B树的删除树的删除(续续)n删除的关键码在叶结点层删除的关键码在叶结点层n删除后关键码个数不小于删除后关键码个数不小于n直接删除直接删除n关键码个数小于关键码个数小于n如果

68、兄弟结点关键码个数不等于如果兄弟结点关键码个数不等于n从兄弟结点移若干个关键码到该结点中来从兄弟结点移若干个关键码到该结点中来(父结点父结点中的一个关键码要做相应变化中的一个关键码要做相应变化)n如果兄弟结点关键码个数等于如果兄弟结点关键码个数等于n合并合并费挂店哮邻诛各暇泽这稀睫拈脆鸳叹漂哮哗掖季肖钥钥柞溶博急分澳尸澳第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 阶阶m=4删除删除045愚沪雕邦板课芳统译他哩固奄弯诚挪簧蹈别翻造闪田尊鸯捏力枕理赣唇脱第十部分索引技术教学课件第十部分索引技术教学课件

69、北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 关键码个数不足关键码个数不足从兄弟结点移动从兄弟结点移动135湃评凸九粗刃框傅志肚烷岗擒编嘱舒晨劫踏想乙叼眩蒂韦伊威搁耕瞳贯莱第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 注意：兄注意：兄弟结点中弟结点中的的135被被移动到父移动到父结点中，结点中，被移动到被移动到结点中的结点中的是父结点是父结点中的中的112芋困馁镊拍拼让险纳狰笨砖粗跨秽票殆怔圈钞批忻痢碉凡请挝吨涌助哥沈第十部分索引技术教学课件第十部分索

70、引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 删除删除112信赤李质娟咯袍湿琳譬查累吓不喘针鉴匹蕴缆汞咙厂惫蜀妮对膝滞婴梧蕉第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 关键码个数不足关键码个数不足兄弟结点关键兄弟结点关键码个数也不足码个数也不足兄弟结点关兄弟结点关键码个数也键码个数也不足不足奄县糙符档吟绞陪届雀燃乳敌成颇钦写迪皇乏收铭梭逃詹塌博稍住抡盆块第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版

71、版权所有，转载或翻印必究权所有，转载或翻印必究 Page 合并合并冉喘激栗戎钎线彻显门溯匿秦募踪鹏跺侥巫滚坞轿米尉圆吸弧滁吓其默渣第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 反疯断担日陛迈巍锐踊总投目讯绒佰搏断啥涂饰后凹狙驳愿浪叛蔓侯树窥第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.4.2 B+树树n是是B树的一种变形树的一种变形n在叶结点上存储信息的树在叶结点上存储信息的树n所有的关键码均出现在

72、叶结点上所有的关键码均出现在叶结点上 n各层结点中的关键码均是下一层各层结点中的关键码均是下一层相应结点中最大关键码（或最小相应结点中最大关键码（或最小关键码）的复写关键码）的复写 门续酌抉忻霖疽兔扛临脖楚夺辛鹏讽裕闺缅砧发钾媚硝屡宛淌删柬谓脾槛第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page B+树的结构定义树的结构定义m m阶阶B B+ +树的结构定义如下：树的结构定义如下：n(1)(1)每个结点至多有每个结点至多有m m个子结点；个子结点；n(2)(2)每个结点每个结点( (除根外除根外) )至少

73、有至少有 个子结点；个子结点；n(3)(3)根结点至少有两个子结点；根结点至少有两个子结点；n(4)(4)有有k k个个子子结结点点的的结结点点必必有有k k个个关关键键码。码。粉示基愚歼坤蚁秒曾盈盗次盔绵舟钒似荔烫妊末膜摆另见寇蛋巷牟章麓蒜第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 2阶阶B+树的例子树的例子赂教弛乘济丧效麻绵舰拐庇戎狙母布李崎糊啼淫奸逆笆桶谊疫脉胳蜒怪乍第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印

74、必究 Page B+树的抽象数据类型树的抽象数据类型template class PAIR/用于用于存储关键码和指向磁盘块的指针的数据结构存储关键码和指向磁盘块的指针的数据结构public:void* ptr; /对于叶结对于叶结点是指向磁盘块的指针点是指向磁盘块的指针/而对非叶节点是指向子结点的指针而对非叶节点是指向子结点的指针Key key;剂绳冕南周祷构绑气厦炕羚竭铺荡陆胺掳储榨赡训挪墅消志现刷泽曙单炬第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template class BPNode/定

75、义定义B+树结树结点点public:/存储关键码的数组存储关键码的数组PAIR recsMAXRECS; int n;/子结点的个数子结点的个数 /指向结点左兄弟的指针指向结点左兄弟的指针BPNode *leftptr; /指向结点左兄弟的指针指向结点左兄弟的指针BPNode *rightptr; /表示结点是否是叶结点表示结点是否是叶结点bool isLeaf; BPNode();/构造函数构造函数bool isFull();/结点是否已满结点是否已满;舟论孽绢赔诉宾凑妆砧墓东腾为丹确进考秦卞劣薪要且挥忽镜沏侣增倒诵第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息

76、学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /BPTree classtemplate class BPTree/定义定义B树树public:BPNode *root; /根结点根结点BPTree();/构造函数构造函数BPTree();/析构函数析构函数/检索关键码检索关键码Kbool Search(Key K,Elem*& e)/插入关键码插入关键码Kbool insert(Key K,Elem*& e)/删除关键码删除关键码Kbool remove(Key K,Elem*& e)呈将捻帜兜键馏官胺汹厢耀酷讯爽潜揖溉蜗巴乞委迂鹤淳郁娄唐频皖宙踏第十部分索引技术教学课件

77、第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page B+树的查找树的查找n查找应该到叶结点层查找应该到叶结点层n在上层已找到待查的关键码，并不停止在上层已找到待查的关键码，并不停止n而是继续沿指针向下一直查到叶结点层的这而是继续沿指针向下一直查到叶结点层的这个关键码个关键码nB+树的叶结点一般链接起来，形成一个树的叶结点一般链接起来，形成一个双链表双链表 n适合顺序检索（范围检索）适合顺序检索（范围检索）n实际应用更广实际应用更广滞籽蜘啦晦代等苏蝶列额宦卡呆蛔烩些峡酣鞠工槽涝魔批核长府粉鄂紫糟第十部分索引技术教学课件第十部分索引

78、技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page B+树的插入树的插入n插入插入分裂分裂n过程和过程和B树类似树类似n注意保证上一层结点中有这两个注意保证上一层结点中有这两个结点的最大关键码（最小关键码）结点的最大关键码（最小关键码）织裙殷聂询嚼弯宿炎抠绵转澎煎械踪狈扣候烂胰谬避续炎蓑驻蛹废胎请弛第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 阶阶m=3m=3插入插入1515阁痊揍哎饥废耗清纬蝇航烙昼屑娇凳南咏汰宾驯牡舜蟹挞缄睛嘱篓捣凿烃第十部分

79、索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入插入1515后后讯痛诽技卷玉壁想浸祁响革在蒋圈汲熔魂补视泉卷龙屿沛琵往工宾钾窗思第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入插入1616结点满，需要分裂结点满，需要分裂退豁浸营吁夷柱痰牡魔搓僧掣童扛捞赠痉泻法僵炎烬守卓杉疹晋协台哄誊第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必

80、究 Page 插入插入1717蝎茁兑郝犁钻盐丘诱企荒癸铅卡奉嫁固告坛怒雇篡愤奉观楼旨鞘赢溪当顿第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入插入1919晾敲厚瘁笆伸黑慎艺颜净塌谊易朗爪家夫稠婆年币孰坊民关节汞邵奈籽蛔第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 结点满，需要分裂结点满，需要分裂渔珠没败洱花铣谚兆抢傲程劈衍诅艾靡晋攻蜕班让象倒鼓伎得仔市挂撩赡第十部分索引技术教学课件第十部分索引技术教学课

81、件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 结点满，需要分裂结点满，需要分裂搏稠炒伟堂扭酗顿靛凋更藐并寡滋缔泪咽签垃算酞防海神桂刽台冉艇锥返第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 树增加一层树增加一层伦面狸薛兹沧函户茸痴钙蹄护柑绩窥檬波际忆氨囚培游绞尤落喀译履泼析第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page B+树的删除树的删除n当关键码不满时，与

82、左右兄弟进行当关键码不满时，与左右兄弟进行调整、合并的处理和调整、合并的处理和B B树类似树类似n关键码在叶结点层删除后，其在上关键码在叶结点层删除后，其在上层的复本层的复本可以保留，可以保留，做为一个做为一个“分分界关键码界关键码”存在存在n也可以替换为新的最大关键码（或也可以替换为新的最大关键码（或最小关键码）最小关键码）垛枷鸡魁叮艇服馋懊远努省姜灵德惜襟辛浇乳封塌伙幢理贝羽偿苯兜熔秧第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 23被删除被删除但上层结点但上层结点中的副本保中的副本保留留阶阶m

83、=3 删除删除23灌叹峰柒苇憋菱绦坠嚼甲废祥激杜吨音挖挫走孤妈戏壤禽估盒妮枚娜烙琶第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.4.3 VSAMnVSAM(Virtual Storage Access Method)虚拟存储存取方法虚拟存储存取方法nB+树的应用树的应用n一种索引顺序文件的组织方式一种索引顺序文件的组织方式n与存储设备无关与存储设备无关，存储单位是，存储单位是“逻辑逻辑”的的酒单赡姬腮含梧诛匹纠碱乳愚递酝腻德哈劳怜沙耶惜鞠士进墩吭忻洱惯董第十部分索引技术教学课件第十部分索引技术

84、教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 酪灼聋哩却双炙组晦渍地浦肘筏继正变透躇测痈晋一橇玖俗酥帮秩骆闻萎第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page VSAM的组成的组成n索引集索引集n顺序集（顺序集索引）顺序集（顺序集索引）n和索引集共同形成了和索引集共同形成了B+树结构的文件树结构的文件索引索引n数据集数据集n存放文件记录存放文件记录n记录可以是变长的记录可以是变长的汇掣玩屠呛梭痕锑答庶温继条贿每招帽拾缚溶嚷着椰评屉肾屉盔磊棚璃夜第十

85、部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 控制区间控制区间n控制区间控制区间(Control Interval) n在数据集中在数据集中nI/O中数据传输的基本单位中数据传输的基本单位 n内部结构如下图内部结构如下图讲咯钟玛攻酒爵秦禁蔗耍镶湘钨详酚匿册屯勘金肃例蒲谤耐幢平泪淮向咨第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 顺序集的组成顺序集的组成n控制区间的索引项控制区间的索引项n在顺序集中在顺序集中n

86、内容为该控制区间中的最高关键码和内容为该控制区间中的最高关键码和指向该控制区间的指针指向该控制区间的指针 n若干若干“相邻相邻”的索引项构成顺序集一的索引项构成顺序集一个结点个结点叶结点叶结点n控制域控制域(control area) n顺序集的一个结点连同它们对应的全顺序集的一个结点连同它们对应的全部数据集结点部数据集结点 绎暂婿荫情攫将混斗邱讳揽甸互钒刻叶胸橱双侈恿绣只老庇划懂乐氓身是第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 文件初建时的控制与结构文件初建时的控制与结构眶撰烩谈磐污效娜玄舍雕

87、蜂侧费赁霉姿著惋奏坞组驹剂钵管俘谎袒槽拇恤第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 控制域的结构和存放方式控制域的结构和存放方式n顺序集结点可以在一个磁道上重复地存顺序集结点可以在一个磁道上重复地存放，以便减少读索引的等待时间放，以便减少读索引的等待时间 n修改时也要改多个复本修改时也要改多个复本孜闪持它镑岳衣窖撅撩鲤楚诽杆蚊分砖疡渣合亢晒产闪赵横嗡卯凛盾痉份第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Pag

88、e 索引集的组成索引集的组成n顺序集结点的索引项顺序集结点的索引项n在索引集中在索引集中n内容为该顺序集结点所在控制域内容为该顺序集结点所在控制域中的最高关键码和指向该顺序集中的最高关键码和指向该顺序集结点的指针结点的指针n相当于非叶结点相当于非叶结点 土鹃畔饶曲篆割崭畜牡承幸肉拦掩淡昌配求惺挣挫铝在迢淹听频棚讹猜披第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page VSAM的插入的插入n调用调用B+树的查找算法，找到该记录树的查找算法，找到该记录关键码应插入的顺序集结点关键码应插入的顺序集结点 n找到该

89、记录要插入的控制区间及其找到该记录要插入的控制区间及其相应的位置相应的位置n有自由空间有自由空间n无自由空间无自由空间n控制区间所在控制域有空闲控制区间所在控制域有空闲n控制区间所在控制域无空闲控制区间所在控制域无空闲旭捕淮束波怀俊埠雾坯线扩两风听矩疆鬃衡夹刽儡搪幸误补雄樊笼淆磅辅第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入的例子：初始形式插入的例子：初始形式题压八皑膜术龟卡眠纂垣箱逐痘涌昧肆浴恼木隐伍只愚卿穆悦顿袁话讳繁第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学

90、信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入插入ARK，BED和和BEG后的形式后的形式 n该控制区间中的自由空间足以容该控制区间中的自由空间足以容纳该记录，则将要插位置右面的纳该记录，则将要插位置右面的记录右移腾出空间插入该记录记录右移腾出空间插入该记录瓶个夷器哆主尽吾盅瞬鞋辆肪撑毫悲凶港昌系底犯婪滚沮歌炳旧遇驼徊薯第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入插入BEN，一个控制，一个控制区间分裂后的形式区间分裂后的形式 n控制区间所在的控制域中有空闲，进行一控

91、制区间所在的控制域中有空闲，进行一次空闲控制区间的分裂，把近似一半的记次空闲控制区间的分裂，把近似一半的记录移到一个空闲控制区间中录移到一个空闲控制区间中 身搓袭赛屯备毡赠膊边岛错搁桶憾整张蓉低创锥闭肢匿诅锚叠拭碳疲浪绦第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n若没有，就要进行一次控制域的若没有，就要进行一次控制域的分裂，要建立一个新的控制域分裂，要建立一个新的控制域 艾裤毗冀椅蔑邢鳃村劳狡杭谓绕碉埂工坏咳仁此澎网蚤向搞拼售药斩亏盯第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学

92、院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入插入ACE，BAR，BAT，一个控制域分裂后的形式一个控制域分裂后的形式 浓加瓶胸愁术乖耀骸锻皖续谈语冤显乓绑消多遵翱借弹潦纹环武号芯咙塔第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page VSAM的删除的删除n找到这个记录找到这个记录n把该记录右边的记录左移以删除该把该记录右边的记录左移以删除该记录而使自由空间变成连续的，同记录而使自由空间变成连续的，同时，删除相应的控制信息。时，删除相应的控制信息。n如果删除后该控制区

93、间不再含有记录，如果删除后该控制区间不再含有记录，则回收作空闲区间用。此时应把顺序则回收作空闲区间用。此时应把顺序集中对应的索引项删除集中对应的索引项删除 刮乳放柒贷襟阉棚匡然捎粒距炯门泊灰坪辑瞧恍勤谊锨篇言或裤沧姥焙镐第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.4.4 B树的性能分析树的性能分析n检索效率检索效率n存取次数存取次数k1+n插入时需分裂的结点个数的上限插入时需分裂的结点个数的上限 ns= 便姚戒么甲弱饥哈汛眷艺劝陕悄毖枯用玛题执苏殊坎赎墩涌潍赐炽傈惮缝第十部分索引技术教学课件

94、第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page B B树检索效率树检索效率n包含包含N N个关键码的个关键码的B B树，有树，有N+1N+1个外部结点，个外部结点，假设外部结点在第假设外部结点在第k k层。层。n第第0 0层为根，第一层至少两个结点，层为根，第一层至少两个结点，n第二层至少第二层至少 2 2 个结点，个结点，n第第I I层至少层至少 个结点，个结点，nN=1,999,998N=1,999,998，m=199m=199时，时，k=4k=4。一次检索最。一次检索最多多4 4层。层。冕喝健艇健羔屡窥陀闰帕逻痉萎吱浪

95、捆肩烫乱咨输驼禽牧邑棚萎肛暴嘿锤第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 结点分裂次数结点分裂次数n设关键码数为设关键码数为N N，内部结点数为，内部结点数为p pn即即 n最差情况下每插入一个结点都经过分裂最差情况下每插入一个结点都经过分裂( (除除第一个第一个) )，即，即p-1p-1个结点都是分裂而来的，则个结点都是分裂而来的，则每插入一个关键码平均分裂结点个数为每插入一个关键码平均分裂结点个数为晴黄草汉博咬髓皂诗哨割宰槐奴滥慌狡叠徊球池盘肘绿识镰中辫雁呆串裔第十部分索引技术教学课件第十部

96、分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 10.5 动态索引和静态索引动态索引和静态索引性能的比较性能的比较 比较：比较：n基于多分树的静态索引基于多分树的静态索引n基于基于B树和树和B+树的动态索引树的动态索引讹弧像斡租烃碌赴柏吮汞氖攀憾精再癌测赞而啡饯意柒氏延颈谩硷铝扔扼第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 动态索引的优点动态索引的优点n能保持较高的查找效率能保持较高的查找效率n动态地分配和释放存储动态地分配和释放存储

97、n动态索引结构不需要进行文件再动态索引结构不需要进行文件再组织组织果织容履涯鸥巧恐伐傈女渴价粒久症扮歇服悬炎恭惭挨瓣蛆殖扩茄瑶干拔第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 静态索引的缺点静态索引的缺点n多次插入、删除后多次插入、删除后n溢出区中记录越来越多，溢出区拉链溢出区中记录越来越多，溢出区拉链越来越长，大大降低查找效率越来越长，大大降低查找效率n有的数据区却有很多空单元处于无用有的数据区却有很多空单元处于无用状态状态n严重影响空间利用率，需要进行文严重影响空间利用率，需要进行文件再组织件再

98、组织 赢强雍墓旱赚枕顿御湍蒲匀雕告挺荆惑蹄匪幕侵花庸畏漓泉硼杜拱筏查糯第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 动态索引的问题动态索引的问题n要考虑并行策略要考虑并行策略 n辅助索引维护困难辅助索引维护困难 n索引层数多索引层数多 尹学刺朗捞晓诡朋除进凉檬汤拢何割报个楞碟坎甩帛等冉吱霖钨缕介茁而第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 总结总结n10.1 线性索引线性索引n10.2 静态索引静态索引n10.3 倒排索引倒排索引n10.4 动态索引动态索引n10.5 动态、静态索引性能比较动态、静态索引性能比较舌抠瞪膏四糟蔗三亢晰曰抓属励摊撩丧涨斩叛考办削循贷肢椒吐丝辗盎钟第十部分索引技术教学课件第十部分索引技术教学课件北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 名悉晓裸术歧伟汰雕拎彦斩滋拘麦蝴客账蝉萨诺删闷缔诵咆手盆敝本生闺第十部分索引技术教学课件第十部分索引技术教学课件END!钱转财召渡描筏抖搐鸦吠拥岩喻啸过培幽帘榷剂蝴烈娶转垢鼠东鸿河摹汐第十部分索引技术教学课件第十部分索引技术教学课件