C++数据结构(第2版)课件第9章 索引技术.ppt

第 9 章 索引技术,本章的基本内容是： 索引的基本概念 线性索引技术 树形索引,9.1 索引的基本概念,数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构，索引技术是组织大型数据库以及磁盘文件的一种重要技术。,在索引问题以及数据库中，常常将数据元素称为记录。,文件：通常指存储在外存上的记录集合。 索引：把一个关键码与它对应的记录相关联的过程称为索引。索引由若干索引项构成。 索引项至少应包含关键码和关键码对应的记录在存储器中的位置等信息。 静态索引：索引结构在文件创建时生成，一旦生成就固定下来，只有当文件再组织时才允许改变。 动态索引：在文件创建时生成索引结构，在文件执行插入/删除操作时，索引结构本身也随之发生改变。,9.1 索引的基本概念,索引的基本概念,线性索引：若将索引项组织为线性结构，则称其为线性索引或索引表； 树形索引：若将索引项组织为树结构，则称其为树形索引。 多级索引：对索引再建立一个索引，就构成了多级索引。,9.1 索引的基本概念,索引的基本概念,对一些大型文件，其索引本身可能也很大，在这种情况下，可以建立多级索引。,稠密索引：在线性索引中，若文件中的每个记录对应一个索引项，则这种索引称为稠密索引。 在稠密索引中，无论文件是否按关键码有序，索引项总是按关键码顺序排列。 只要内存空间允许，通常把稠密索引存储在内存中，从而大大提高记录的查找速度。,稠密索引,9.2 线性索引技术,稠密索引主要适用于静态索引。,稠密索引示例,9.2 线性索引技术,有序,无序或有序,优点：实现对数据库记录有效的查找（采用折半查找技术）和随机访问（按记录号访问）。 缺点：如果文件中包含的记录太多，索引表本身可能会因为太大而无法在内存中存储；文件中插入或删除记录，必须更新稠密索引，而稠密索引的插入和删除操作代价很高。,9.2 线性索引技术,稠密索引,文件,外存,稠密索引,内存,分块索引,9.2 线性索引技术,稠密索引空间代价很大,分块索引,分块索引需要将文件划分为若干块，且要求分块有序。,多级索引,9.2 线性索引技术,分块索引,有序,9.2 线性索引技术,分块索引,在分块索引表中进行的查找称为分块查找（也称为索引顺序查找），分两步进行： 在索引表中确定待查关键码所在的块； 在相应块中查找待查关键码。,块内查找顺序查找,设有n个记录的文件分为m个块，每个块均为t个记录，则n=mt。设Lb为查找索引表确定关键码所在块的平均查找长度，Lw为在块内查找关键码的平均查找长度，则分块查找的平均查找长度为： ASL=Lb + Lw 若采用顺序查找对索引表进行查找，则分块查找的平均查找长度为：,9.2 线性索引技术,分块索引,ASL=Lb + Lw=,9.2 线性索引技术,多重表,稠密索引、分块索引,对主关键码建立索引,为文件建立索引的目的是什么?,对主关键码进行查找,对次关键码进行查找,对次关键码建立索引,多重表、倒排表,9.2 线性索引技术,多重表,多重表除了为文件建立一个主索引外，还为每个需要查找的次关键码建立一个索引。 在文件中，为建立索引的次关键码分别增设一个指针域，用于将次关键码相同的记录链结在一起（稠密索引），或将在同一块中的记录链结在一起（分块索引）。,9.2 线性索引技术,多重表,9.2 线性索引技术,倒排表,9.3 树形索引,2 3 树,2-3树：是具有下列特性的树： 一个结点包含1个或者2个关键码。 每个内部结点有2个子女（包含一个关键码）或者3个子女（包含两个关键码）。 所有叶子结点都在树的同一层。,9.3 树形索引,2 3 树示例,形状上有什么特性?,9.3 树形索引,2 3 树示例,包含1个或者2个关键码； 有2个子女或者3个子女； 叶子结点在同一层。,9.3 树形索引,2 3 树示例,结点的值有什么特性?,9.3 树形索引,2 3 树示例,左子树中所有结点的值均小于第一个关键码的值； 中间子树中所有结点的值均大于第一个关键码的值，且小于第二个关键码的值； 右子树中所有结点的值均大于第二个关键码的值。,9.3 树形索引,2 3 树查找操作,21,182133,2123,9.3 树形索引,2 3 树插入操作,新记录将插入到相应的叶子结点中。,18 33,9.3 树形索引,2 3 树插入操作,新记录将插入到相应的叶子结点中。,9.3 树形索引,2 3 树插入操作,新记录将插入到相应的叶子结点中。,9.3 树形索引,2 3 树插入操作,新记录将插入到相应的叶子结点中。,18 33,12,23 30,48,10,15,20 21,24,31,45 47,50 52 55,插入,9.3 树形索引,2 3 树插入操作,新记录将插入到相应的叶子结点中。,18 33,12,23 30,48,10,15,20 21,24,31,45 47,分裂,50,55,52,9.3 树形索引,2 3 树插入操作,新记录将插入到相应的叶子结点中。,18 33,12,23 30,10,15,20 21,24,31,45 47,提升,50,55,48 52,9.3 树形索引,2 3 树删除操作,情况1：从包含2个记录的叶子结点删除1个记录。,解决方法：直接删除这个记录。,18 33,12,23 30,48,10,15,24,31,45 47,50 52,9.3 树形索引,2 3 树删除操作,情况1：从包含2个记录的叶子结点删除1个记录。,解决方法：直接删除这个记录。,21,9.3 树形索引,2 3 树删除操作,情况2：从包含1个记录的叶子结点中删除这个记录。,解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。,18 33,12,21 30,48,10,15,20,23,31,45 47,50 52,9.3 树形索引,2 3 树删除操作,情况2：从包含1个记录的叶子结点中删除这个记录。,解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。,18 33,12,21 30,48,10,15,20,23,31,45 47,50 52,9.3 树形索引,2 3 树删除操作,情况2：从包含1个记录的叶子结点中删除这个记录。,解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。,18 33,12,20 21,48,10,15,30,31,45 47,50 52,9.3 树形索引,2 3 树删除操作,情况2：从包含1个记录的叶子结点中删除这个记录。,解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。,18 33,12,20 21,48,10,15,30,31,45 47,50 52,9.3 树形索引,2 3 树删除操作,情况2：从包含1个记录的叶子结点中删除这个记录。,解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。,20 21,48,33,31,45 47,50 52,9.3 树形索引,2 3 树删除操作,情况2：从包含1个记录的叶子结点中删除这个记录。,10 12,18 30,解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。,48,33,30,45 47,50 52,9.3 树形索引,2 3 树删除操作,情况2：从包含1个记录的叶子结点中删除这个记录。,解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点，这可能减少树的高度。,25,20,9.3 树形索引,2 3 树删除操作,情况2：从包含1个记录的叶子结点中删除这个记录。,解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点，这可能减少树的高度。,2-3树的优点：能够以相对较低的代价保持树高平衡。,9.3 树形索引,2 3 树删除操作,情况3：从内部结点删除一个记录。,解决方法：将被删除记录用右边子树中的最小关键码Y代替（ Y一定在某个叶子结点中），然后再删除Y。,9.3 树形索引,2 3 树删除操作,情况3：从内部结点删除一个记录。,解决方法：将被删除记录用右边子树中的最小关键码Y代替（ Y一定在某个叶子结点中），然后再删除Y。,20 33,12,23 30,48,10,15,21,24,31,45 47,50 52,B树,9.3 树形索引,m阶B树：是满足下列特性的树： 所有叶子结点都在同一层上，并且不带信息，叶子的双亲称为终端结点。 树中每个结点至多有m棵子树； 若根结点不是终端结点，则至少有两棵子树； 除根结点外，其他非终端结点至少有m/2 棵子树；,B树是23树的推广，2-3树是一个3阶B树 。,所有非终端结点都包含以下数据： （n，A0，K1，A1，K2，Kn，An） 其中，n（m/2 1nm 1）为关键码的个数； Ki（1in）为关键码，且KiKi+1（1in-1）； Ai（0in）为指向子树根结点的指针，且指针Ai所指子树中所有结点的关键码均小于Ki+1大于Ki。,B树,9.3 树形索引,1 18,1 11,1 27,1 39,3 47 53 64,1 99,F,F,F,F,F,F,F,F,F,F,F,F,2 43 78,1 35,9.3 树形索引,B树示例,B+树,m阶B树：是满足下列特性的树： 含有m个关键码，每一个关