版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、2020年9月13日星期日,数据结构与算法,Page: 1,第9章 索引技术,主要内容,1. 基本概念 2. 线性索引 稠密索引 分块索引 多重表 倒排表 3. 树型索引 2-3树 B-树 B+树,2020年9月13日星期日,数据结构与算法,Page: 2,9.1索引的基本概念,在索引问题以及数据库中,常常将数据元素称为记录(record)。,文件 文件(file)通常是指存储在外存上的记录集合。从操作系统的角度看,文件是无结构的连续字节序列,从数据库的角度看,文件是有结构的记录集合,每个记录可由若干个数据项组成。记录是文件中进行存取的基本单位,数据项是文件中可使用的最小单位。,索引 索引(i
2、ndex)是把一个关键码与它对应的记录相关联的过程,一个索引属于某一个文件,它由若干索引项构成,每个索引项(index item)至少应包含关键码对应的记录在存储器中的位置等信息。,2020年9月13日星期日,数据结构与算法,Page: 3,9.1索引的基本概念,索引并不需要重新排列记录在文件中的顺序,一个文件可能有多个相关的索引,每个索引往往支持一个关键码,并且通过该索引实现对文件中记录的快速访问。,静态索引 静态索引(static index)是指索引结构在文件创建时生成。一旦生成就固定下来,只有当文件再组织时才允许改变。,动态索引 动态索引(dynamic index)是指在文件创建时生
3、成的索引结构。在文件执行插入、删除等操作时,索引结构本身也随之发生改变。,2020年9月13日星期日,数据结构与算法,Page: 4,9.1索引的基本概念,树形索引 索引项组织为树结构,称其为树形索引。,对一些大型文件,索引本身可能也很大,可对索引再建立一个索引,这样就构成了多级索引。当某级索引很大时,也可能要驻留在外存。,线性索引 索引项组织为线性结构,则称其为线性索引或索引表。,2020年9月13日星期日,数据结构与算法,Page: 5,9.2 线性索引,一、稠密索引 稠密索引主要适用于静态索引。,在线性索引中,若文件中的每个记录对应一个索引项,则这种索引称为稠密索引。在稠密索引中,无论文
4、件是否按关键码有序,索引项总是按关键码顺序排列。 见P298 图8-1,优点:对数据库记录有效查找和随机访问; 缺点:查找过程中可能需要多次访问磁盘使查找的性能降低。一旦在文件中插入或删除了记录,就必须更新稠密索引。,2020年9月13日星期日,数据结构与算法,Page: 6,9.2 线性索引,二、分块索引 分块索引既适用于静态索引,也适用于动态索引。,对文件分块使其分块有序。分块有序是指将文件划分为若干块,每一块内不要求有序,但第二块中所有记录的关键码均大于第一块中所有记录关键码,第三块中所有记录的关键码均大于第二块中所有的关键码.依此类推。,对于分块有序的文件,每块只需对应一个索引项,这种
5、索引方法叫做分块索引。每块对应一个索引项,各索引项按关键码有序排序,形成一个索引表。,2020年9月13日星期日,数据结构与算法,Page: 7,9.2 线性索引,二、分块索引,在分块索引表中进行的查找称为分块查找(也称为索引顺序查找) 1、在索引表中确定待查关键码所在的块。 2、在相应块中查找待查关键码。 见P299 图8-3,2020年9月13日星期日,数据结构与算法,Page: 8,9.2 线性索引,三、多重表,多重表(multiple list)是一种多索引结构,除了为文件建立一个主索引外,还为每个需要查找的次关键码建立一个索引,在文件中为建立索引的次关键码分别增设一个指针域,用于将关
6、键码相同的记录连接在一起,或将在同一块中的记录连接在一起(对分块索引) 见P300 图8-4,2020年9月13日星期日,数据结构与算法,Page: 9,9.2 线性索引,四、倒排表,倒排表(reverse list)是对次关键码建立一种索引表,在倒排表中,索引项包括次关键码的值和具有的各记录的地址。其中记录号表存储具有相同关键码值的所有记录的记录号,并且它们有序排列。 见P301 图8-5,其中,记录号表存储具有相同次关键码值的所有记录的记录号,并且它们有序排列。 索引不是由记录来确定属性(即数据项)值,而是由属性值来确定记录的位置,因而称为倒排表。,2020年9月13日星期日,数据结构与算
7、法,Page: 10,9.3 树形索引,树形索引是一种树结构的索引,树中每个结点是一个索引项,一般应包含关键码及其对应的记录地址,对树结构的查找一般也快于线性查找。 树形索引多用作动态索引结构,即树中结点可动态地增加或撤消,树形索引常采用链接存储结构实现。,2020年9月13日星期日,数据结构与算法,Page: 11,9.3 树形索引,一、 2-3树 一颗2-3树(见P302图9-7)是具有下列特性的树。 (1)一个结点包含一个或者两个关键码; (2)每个内部结点有2个子女(如果它包含一个关键码)或者3个子女(若它包含两个关键码),并因此得名2-3树; (3)所有叶子结点都在树的同一层。,2-
8、3树最大的优点是它能够以相对较低的代价保持树高的平衡。,2020年9月13日星期日,数据结构与算法,Page: 12,9.3 树形索引,一、 2-3树,2020年9月13日星期日,数据结构与算法,Page: 13,9.3 树形索引,一、 2-3树 2-3树还有一类似于二叉排序树的特征,对于每一个结点,左子树中所有结点的值都小于第一个关键码的值,而中间子树的值均大于第一个关键码的值,若有右子树的话那么中间子树中所有结点的值都小于第二个关键码的值,而右子树的值大于第二个关键码的值,一个高度为k的2-3树至少有2k-1个叶子结点,此时每个分支结点都有2个子女,形成一颗满二叉树的形状,一个高度为k的2
9、-3树至多有3k-1个叶子结点,此时每个分支结点都有3个子女。 在2-3树中查找一个关键码的过程类似于在二叉排序树中查找。,2020年9月13日星期日,数据结构与算法,Page: 14,9.3 树形索引,一、 2-3树,查找:,在2-3树中查找一个关键码的过程类似于在二叉排序树中的查找。 查找从根结点开始,如果根结点不包含被查找的关键码 k,那么查找就在可能包含关键码k的子树中继续进行。存储在根结点中的关键码确定哪一个子树是正确的子树。,2020年9月13日星期日,数据结构与算法,Page: 15,9.3 树形索引,一、 2-3树,插入:,向一个2-3树中插入一个记录的过程类似于二叉排序树的插
10、入,新记录也是插到相应的叶子结点中。,插入过程如下: 首先要找到被插入记录应该插入的叶子结点。 如果这个叶子结点只包含一个记录,就可以把新记录直接填加到这个叶子结点中。 如果新记录要插入到叶子结点L中,而L已经包含了两个记录,那么就需要把L分成两个结点,这称为一次“分裂”。首先创建一个新结点L,L得到这三个记录的关键码中最小的一个,L 得到最大的一个,中间的关键码与一个,2020年9月13日星期日,数据结构与算法,Page: 16,9.3 树形索引,指向L 的指针传回父结点,这称为一次“提升”。然后把被提升的关键码插入父结点。如果父结点当前只包含一个记录(即只有两个子女),那么就只需简单地把被
11、提升的关键码和指向L 的指针添加到父结点中。如果父结点已经满了,那么就重复“分裂提升”过程。当提升需要根结点分裂时,2-3树的高度就增加了一层。,2020年9月13日星期日,数据结构与算法,Page: 17,9.3 树形索引,2020年9月13日星期日,数据结构与算法,Page: 18,9.3 树形索引,一、 2-3树,删除:,当从2-3树中删除一个关键码时,有三种情况要考虑: 从一个包含两个记录的叶子结点删除一个记录。 只简单删除该记录即可。,2020年9月13日星期日,数据结构与算法,Page: 19,9.3 树形索引,一、 2-3树,删除:, 唯一的一个记录从一个叶子结点删除。,又分二种
12、情形: 相邻的兄弟结点有两个记录,则移一个记录填补即可,但需修改父结点。,2020年9月13日星期日,数据结构与算法,Page: 20,9.3 树形索引,一、 2-3树,删除:,相邻的兄弟结点都只有一个记录,则把该结点与一个兄弟结点合并,并删除该结点,但也需修改父结点,有可能影响至根结点并导致树减少一层。, 从一个内部结点删除一个记录。,被删除的记录用其子树的最小的关键码代替,逐步向下至叶子结点的关键码。,2-3树的插入和删除操作都会引起叶子结点的分裂或者合并。 2-3树是树高平衡的,最大深度是 log2n+1。 2-3树的插入、查找和删除操作都需要O(log2n)时间。,2020年9月13日
13、星期日,数据结构与算法,Page: 21,9.3 树形索引,二、 B-树 B-树是一种平衡的多路查找树,主要面向动态查找,通常用在文件系统中。,1、B-树的定义 一颗m阶的B-树,或者为空树,或者为满足下列特性的m叉树; (1)所有的叶子结点都出现在同一层上,并且不带信息,叶子的双亲称为终端结点; (2)树中每个结点至多有m棵子树; (3)若根结点不是终端结点,则至少有两棵子树; (4)除根结点之外的所有非终端结点至少有 m/2 棵子树;,2020年9月13日星期日,数据结构与算法,Page: 22,9.3 树形索引,二、 B-树 所有的非终端结点都包含以下数据: (n,A0,K1,A1,K2
14、,Kn,An) 其中,n(m/2 1nm 1)为关键码的个数,Ki(1in)为关键码,且KiKi+1(1in-1),Ai(0in)为指向子树根结点的指针,且指针Ai所指子树中所有结点的关键码均小于Ki+1大于Ki。,B-树是2-3树的推广,2-3树是一个3阶B-树。,2020年9月13日星期日,数据结构与算法,Page: 23,9.3 树形索引,二、 B-树,2020年9月13日星期日,数据结构与算法,Page: 24,9.3 树形索引,二、 B-树,在m阶B-树中每个结点至多有m棵子树(m-1个关键码 ),除根结点之外的所有非终端结点至少有 m/2 棵子树; 若根结点不是终端结点,则至少有两
15、棵子树(即一个关键码),至多有m棵子树(即m-1个关键码); B-树的叶子结点可以看作是外部结点(即查找失败的结点,实际不存在),指向这些结点的指针为空。,2020年9月13日星期日,数据结构与算法,Page: 25,9.3 树形索引,二、 B-树,查找:,B-树的每个结点上是多关键码的有序表,在到达某个结点时,先在有序表中查找,若找到,则查找成功;否则,按照指针信息到相应的子树中查找,当到达叶子结点时,则说明树中没有对应的关键码,查找失败。 在B-树上的查找过程是一个顺指针查找结点和在结点中查找关键码交叉进行的过程。 如查找关键码53,在B-树上进行查找包含两种基本操作: 在B-树中查找结点
16、; 在结点中查找关键码。,2020年9月13日星期日,数据结构与算法,Page: 26,9.3 树形索引,二、 B-树,插入:,假定要在m阶B-树中插入关键码key,设n=m-1,即n为结点中关键码数目的最大值,B-树的插入过程如下:, 定位: 查找插入的终端结点, 该结点的关键码数目n,则直接插入即可; 否则,执行“分裂提升”过程。,分裂提升: 将结点p“分裂”成两个结点p1和p2,中间关键码k提升到父结点,k的左指针指向p1,右指针指向p2。 若父结点的关键码数溢出则继续向根部“分裂提升” 导致树的高度增加一层。,2020年9月13日星期日,数据结构与算法,Page: 27,9.3 树形索
17、引,二、 B-树,删除:,设在m阶B-树中删除关键码key。 首先要找到key的位置,即“定位”。定位的结果是返回了key所在结点的指针q,假定key是结点q中第i个关键码Ki,若结点q不是终端结点,则用Ai所指的子树中的最小键值x来“替换”Ki。由于x所在结点一定是终端结点,这样,删除问题就归结为在终端结点中删除关键码。,如果终端结点中关键码的个数大于m/2 -1,则可直接删除该关键码。,2020年9月13日星期日,数据结构与算法,Page: 28,9.3 树形索引,二、 B-树,例如在下图所示B树中删除关键码90。,2020年9月13日星期日,数据结构与算法,Page: 29,9.3 树形
18、索引,二、 B-树,如果在终端结点中删除一个关键码后,其关键码的个数不足 m/2-2,则不符合m阶B-树的要求,需要从兄弟结点借关键码或合并结点,以保证B-树的特性,具体分两种情况:, 兄弟够借: 借来的关键码上移到父结点,父结点相应的关键码下移到被删结点中。, 兄弟不够借: 则执行“合并”操作,合并过程可能导致到根结点,并使B-树的树高减少一层。,见P309 图914示例,2020年9月13日星期日,数据结构与算法,Page: 30,9.3 树形索引,三、 B+树 在基于磁盘的大型系统中,最普遍实现的是B-树的一个变体,称为B+树。,一棵m阶的B+树在结构上与m阶的B-树相同,但在关键码的内
19、部安排上有所不同,具体如下: (1)具有m棵子树的结点含有m个关键码,即每一个关键码对应一棵子树。 (2)关键码K是它所对应的子树的根结点中最大(或最小)关键码。 (3)所有的终端结点中包含了全部关键码信息,及指向关键码记录的指针。 (4)各终端结点按关键码的大小次序链在一起,形成单链表,并设置头指针。,2020年9月13日星期日,数据结构与算法,Page: 31,9.3 树形索引,三、 B+树 与B-树类似,在B树中,结点内的关键码仍然有序排列,并且对同一结点内的任意两个关键码Ki和Kj,若KiKj,则Ki小于Kj对应的子树中的所有关键码。,与二叉排序树和2-3树最显著的不同是B树只在终端结点存储记录,内部结点存储关键码(用于引导查找)。,例如图9-15所示为一棵3阶的B+树,通常在B树上有两个头指针,一个指向根结点,另一个指向关键码最小的终端结点 。因此,可以对B+树进行两种查找操作:一种是从最小关键码起顺序查找,另一种是从根结点开始随机查找。,2020年9月13日星期日,数据结构与算法,Page: 32,9.3 树形索引,三、 B+树,2020年9月13日星期日,数据结构与算法,Page: 33,9.3 树形索引,三、 B+树 B+树特别适合范围查找。一旦找到了范围中的第一个记录,通过顺序处
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 20261029-082002-人教版高二化学选择性必修1化学反应原理期末测试卷(含答案解析)
- 《思想道德与法治(2025版)》期末考试典型例题(附答案解析)
- (2025年)全国临床护理三基训练试题及答案
- (完整版)医院康复科考核试题及答案
- (2025年)电工证考试题模拟试题初级电工考试题(含答案)
- 2025 年老年人三力测试题库及答案
- 3-6岁儿童学习与发展指南(2026版)测试题题库及答案
- (完整版)2025年护士资格考试真题及答案
- 【注安】2025年注安管理考试真题及答案
- 安排技术团队现场设备调试通知函5篇范文
- 《护理管理培训》课件
- 2026重庆国际物流枢纽园区建设有限责任公司及子公司招聘19人笔试模拟试题及答案解析
- 检察官遴选考试真题及答案解析
- 江苏省无锡市梅村高级中学2025-2026学年高一上学期10月阶段检测物理试卷(含答案)
- 2026秋新北师大版数学六年级上册教学课件:数学好玩 五子棋
- TCNAS 59-2026 《患者自控镇痛护理》全面解读
- 生物酶制剂生产流程技术指南
- 2026及未来5年中国全自动商用咖啡机市场数据分析及竞争策略研究报告
- 超声评估胆囊腺肌症
- TSG08-2026《特种设备使用管理规则》解析
- 北师大版四年级上册书法练习指导 教案
评论
0/150
提交评论