第9章索引技术

1、数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术第九章第九章 索引技术索引技术本章的基本内容是：本章的基本内容是：索引的基本概念索引的基本概念线性索引技术线性索引技术树形索引树形索引数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.1 索引的基本概念索引的基本概念数据结构的最终目的是提高数据的处理速度，数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结索引是为了加快查找速度而设计的一种数据结构，索引技术是组织大型数据库以及磁盘文件构，索引技术是组织大型数据库以及磁盘文件的一种重要技术。的一种重要技术。 在索引问

2、题以及数据库中，常常将数据元素在索引问题以及数据库中，常常将数据元素称为记录。称为记录。 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术文件：通常指存储在外存上的记录集合。文件：通常指存储在外存上的记录集合。索引：把一个关键码与它对应的记录相关联的过程。索引：把一个关键码与它对应的记录相关联的过程。索引由若干索引项构成，索引项至少应包含关键码和索引由若干索引项构成，索引项至少应包含关键码和关键码对应的记录在存储器中的位置等信息。关键码对应的记录在存储器中的位置等信息。静态索引：索引结构在文件创建时生成，一旦生成就静态索引：索引结构在文件创建时生成，一旦生成就固定下来

3、，只有当文件再组织时才允许改变。固定下来，只有当文件再组织时才允许改变。 动态索引：在文件创建时生成索引结构，在文件执行动态索引：在文件创建时生成索引结构，在文件执行插入插入/ /删除等操作时，索引结构本身也随之发生改变。删除等操作时，索引结构本身也随之发生改变。9.1 索引的基本概念索引的基本概念索引的基本概念索引的基本概念数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术线性索引：若将索引项组织为线性结构，则称其为线线性索引：若将索引项组织为线性结构，则称其为线性索引或索引表性索引或索引表；树形索引：若将索引项组织为树结构，则称其为树形树形索引：若将索引项组织为树结

4、构，则称其为树形索引索引。多级索引：对索引再建立一个索引，就构成了多级索多级索引：对索引再建立一个索引，就构成了多级索引。引。 9.1 索引的基本概念索引的基本概念索引的基本概念索引的基本概念对一些大型文件，其索引本身可能也很大，在这种情对一些大型文件，其索引本身可能也很大，在这种情况下，可以建立多级索引。况下，可以建立多级索引。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术稠密索引：在线性索引中，若文件中的每个记录对应稠密索引：在线性索引中，若文件中的每个记录对应一个索引项，则这种索引称为稠密索引。一个索引项，则这种索引称为稠密索引。在稠密索引中，无论文件是否按关

5、键码有序，索引项在稠密索引中，无论文件是否按关键码有序，索引项总是按关键码顺序排列。总是按关键码顺序排列。只要内存空间允许，通常把稠密索引存储在内存中，只要内存空间允许，通常把稠密索引存储在内存中，从而大大提高记录的查找速度。从而大大提高记录的查找速度。 稠密索引稠密索引9.2 线性索引技术线性索引技术稠密索引主要适用于静态索引。稠密索引主要适用于静态索引。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术稠密索引示例稠密索引示例9.2 线性索引技术线性索引技术 8 20 52 35 40 61 56 关键码关键码 其它数据项其它数据项文件文件r1r2r3r4r5r6r

6、7 8203540525661关键码关键码 指针指针索引表索引表有序有序无序或有序无序或有序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术优点：实现对数据库记录有效的查找（采用折半查优点：实现对数据库记录有效的查找（采用折半查找技术）和随机访问（按记录号访问）。找技术）和随机访问（按记录号访问）。缺点：如果文件中包含的记录太多，索引表本身可缺点：如果文件中包含的记录太多，索引表本身可能会因为太大而无法在内存中存储；文件中插入或能会因为太大而无法在内存中存储；文件中插入或删除记录，必须更新稠密索引，而删除记录，必须更新稠密索引，而稠密索引的插入稠密索引的插入和删除操作

7、代价很高。和删除操作代价很高。 9.2 线性索引技术线性索引技术稠密索引稠密索引 文件文件 外存外存 稠密索引稠密索引 内存内存数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术分块索引分块索引9.2 线性索引技术线性索引技术稠密索引空间代价很大稠密索引空间代价很大减少索引项的个数减少索引项的个数分块索引分块索引分块索引需要将文件划分为若干块，且要求分块有序。分块索引需要将文件划分为若干块，且要求分块有序。块内无序：每一块内不要求有序块内无序：每一块内不要求有序块间有序：块与块之间有序块间有序：块与块之间有序分块有序分块有序多级索引多级索引每块建立一个索引项每块建立一个

8、索引项数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.2 线性索引技术线性索引技术分块索引分块索引35 20 8 52 40 61 65 88 76 第第1块块文件文件关键码关键码 其他数据项其他数据项第第2块块第第3块块35 361 388 3索引表索引表最大值最大值 块长块长 块首地址块首地址 有序有序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.2 线性索引技术线性索引技术分块索引分块索引在分块索引表中进行的查找称为分块查找（也称在分块索引表中进行的查找称为分块查找（也称为索引顺序查找），分两步进行：为索引顺序查找），分两步进

9、行： 在索引表中确定待查关键码所在的块；在索引表中确定待查关键码所在的块； 在相应块中查找待查关键码。在相应块中查找待查关键码。索引表查找索引表查找顺序查找顺序查找折半查找折半查找块内查找块内查找顺序查找顺序查找数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术 设有设有n个记录的文件分为个记录的文件分为m个块，每个块均为个块，每个块均为t个个记录，则记录，则n=mt。设。设Lb为查找索引表确定关键码所为查找索引表确定关键码所在块的平均查找长度，在块的平均查找长度，Lw为在块内查找关键码的平为在块内查找关键码的平均查找长度，则分块查找的平均查找长度为：均查找长度，则分块

10、查找的平均查找长度为： ASL=Lb + Lw 若采用顺序查找对索引表进行查找，则分块查若采用顺序查找对索引表进行查找，则分块查找的平均查找长度为：找的平均查找长度为： 9.2 线性索引技术线性索引技术分块索引分块索引ASL=Lb + Lw=1)(212) 1(2) 1(ttmtm当当 t 取取 时，时，ASL取最小值取最小值 +1。nn数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.2 线性索引技术线性索引技术多重表多重表稠密索引、分块索引稠密索引、分块索引对主关键码建立索引对主关键码建立索引为文件建立索引的目的是什么为文件建立索引的目的是什么?对主关键码进行查

11、找对主关键码进行查找对次关键码进行查找对次关键码进行查找对次关键码建立索引对次关键码建立索引多重表、倒排表多重表、倒排表数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.2 线性索引技术线性索引技术多重表多重表多重表除了为文件建立一个主索引外，还为每个多重表除了为文件建立一个主索引外，还为每个需要查找的次关键码建立一个索引。需要查找的次关键码建立一个索引。在文件中，为建立索引的次关键码分别增设一个在文件中，为建立索引的次关键码分别增设一个指针域，用于将次关键码相同的记录链结在一起指针域，用于将次关键码相同的记录链结在一起（稠密索引），或将在同一块中的记录链结在一（稠

12、密索引），或将在同一块中的记录链结在一起（分块索引）。起（分块索引）。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术关键码关键码 指针指针 0001 0002 0003 0004 0005 0006主索引主索引9.2 线性索引技术线性索引技术多重表多重表次关键码次关键码头指针头指针长度长度男男013女女033“性别性别”次索引次索引次关键码次关键码头指针头指针长度长度24260232730013“年龄年龄”次索引次索引24男男王东王东000630女女李爽李爽0005062505女女齐梅齐梅0004052704女女刘楠刘楠0003042506男男张亮张亮0002033

13、002男男王刚王刚0001年年 龄龄性性 别别姓姓 名名职工号职工号文件文件 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术关键码关键码 指针指针 0001 0002 0003 0004 0005 0006主索引主索引9.2 线性索引技术线性索引技术倒排表倒排表“年龄年龄”倒排倒排表表 次关键码次关键码 记录号表记录号表 2426 02, 04, 06 2730 01, 03, 05“性别性别”倒排倒排表表 次关键码次关键码 记录号表记录号表 男男 01, 02, 06 女女 03, 04, 0524男男王东王东000630女女李爽李爽000525女女齐梅齐梅000

14、427女女刘楠刘楠000325男男张亮张亮000230男男王刚王刚0001年龄年龄性别性别姓名姓名职工号职工号文件文件 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.3 树形索引树形索引2 3 树树2- -3树：是具有下列特性的树：树：是具有下列特性的树： 一个结点包含一个结点包含1个或者个或者2个关键码。个关键码。每个内部结点有每个内部结点有2个子女（包含一个关键码）或者个子女（包含一个关键码）或者3个子女（包含两个关键码）。个子女（包含两个关键码）。 所有叶子结点都在树的同一层。所有叶子结点都在树的同一层。数据结构（数据结构（C+版）版）清华大学出版社清华大

15、学出版社第9章索引技术9.3 树形索引树形索引2 3 树示例树示例18 331223 3048101520 21243145 4750 52形状上有什么特性形状上有什么特性?数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.3 树形索引树形索引2 3 树示例树示例包含包含1个或者个或者2个关键码；个关键码；有有2个子女或者个子女或者3个子女；个子女；叶子结点在同一层。叶子结点在同一层。18 331223 3048101520 21243145 4750 52数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.3 树形索引树形索引2 3 树示

16、例树示例结点的值有什么特性结点的值有什么特性?18 331223 3048101520 21243145 4750 52数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.3 树形索引树形索引2 3 树示例树示例左子树中所有结点的值均小于第一个关键码的值；左子树中所有结点的值均小于第一个关键码的值；中间子树中所有结点的值均大于第一个关键码的值，中间子树中所有结点的值均大于第一个关键码的值，且小于第二个关键码的值；且小于第二个关键码的值；右子树中所有结点的值均大于第二个关键码的值。右子树中所有结点的值均大于第二个关键码的值。18 331223 3048101520 21

17、243145 4750 52数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术18 331223 3048101520 21243145 4750 529.3 树形索引树形索引2 3 树树查找操作查找操作211821332123比较次数不超过树的深度。比较次数不超过树的深度。由于由于2-3树是树高平衡的，而且每一个内部结点至少树是树高平衡的，而且每一个内部结点至少有有2个子女，所以树的最大深度是个子女，所以树的最大深度是 。 1log2 n数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.3 树形索引树形索引2 3 树树插入操作插入操作新记录

18、将插入到相应的叶子结点中。新记录将插入到相应的叶子结点中。18 331223 3048101520 21243145 4750 52叶子结点只包含叶子结点只包含1个记录个记录插入新记录插入新记录 14数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.3 树形索引树形索引2 3 树树插入操作插入操作新记录将插入到相应的叶子结点中。新记录将插入到相应的叶子结点中。叶子结点只包含叶子结点只包含1个记录个记录插入新记录插入新记录 18 331223 30481520 21243145 4750 5210 14数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章

19、索引技术9.3 树形索引树形索引2 3 树树插入操作插入操作新记录将插入到相应的叶子结点中。新记录将插入到相应的叶子结点中。18 331223 3048101520 21243145 4750 52叶子结点只包含叶子结点只包含2个记录个记录插入新记录，分裂提升插入新记录，分裂提升 55数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.3 树形索引树形索引2 3 树树插入操作插入操作新记录将插入到相应的叶子结点中。新记录将插入到相应的叶子结点中。18 331223 3048101520 21243145 4750 52 55叶子结点只包含叶子结点只包含2个记录个记录插

20、入新记录，分裂提升插入新记录，分裂提升 插入插入数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.3 树形索引树形索引2 3 树树插入操作插入操作新记录将插入到相应的叶子结点中。新记录将插入到相应的叶子结点中。18 331223 3048101520 21243145 47叶子结点只包含叶子结点只包含2个记录个记录插入新记录，分裂提升插入新记录，分裂提升 分裂分裂505552数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.3 树形索引树形索引2 3 树树插入操作插入操作新记录将插入到相应的叶子结点中。新记录将插入到相应的叶子结点中。18

21、 331223 30101520 21243145 47叶子结点只包含叶子结点只包含2个记录个记录插入新记录，分裂提升插入新记录，分裂提升 提升提升505548 52数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术18 331223 3048101520 21243145 4750 529.3 树形索引树形索引2 3 树树删除操作删除操作情况情况1：从包含：从包含2个记录的叶子结点删除个记录的叶子结点删除1个记录。个记录。 解决方法：直接删除这个记录。解决方法：直接删除这个记录。 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术18 3312

22、23 30481015243145 4750 529.3 树形索引树形索引2 3 树树删除操作删除操作情况情况1：从包含：从包含2个记录的叶子结点删除个记录的叶子结点删除1个记录。个记录。 解决方法：直接删除这个记录。解决方法：直接删除这个记录。 21数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术18 331223 3048101520 21243145 4750 529.3 树形索引树形索引2 3 树树删除操作删除操作情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。 解决方法：向兄弟结点借一个记录，同时修改双亲解决方法：

23、向兄弟结点借一个记录，同时修改双亲结点的记录。结点的记录。 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术18 331221 3048101520233145 4750 529.3 树形索引树形索引2 3 树树删除操作删除操作情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。 解决方法：向兄弟结点借一个记录，同时修改双亲解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。结点的记录。 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术18 331221 3048101520233145 4750

24、529.3 树形索引树形索引2 3 树树删除操作删除操作情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。并影响双亲结点。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术18 331220 21481015303145 4750 529.3 树形索引树形索引2 3 树树删除操作删除操作情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，解

25、决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。并影响双亲结点。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术18 331220 21481015303145 4750 529.3 树形索引树形索引2 3 树树删除操作删除操作情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。并影响双亲结点。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术20 2148333145 4750 529.3

26、 树形索引树形索引2 3 树树删除操作删除操作情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。 10 1218 30解决方法：兄弟结点不够借，需要合并相邻结点，解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。并影响双亲结点。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术48333045 4750 529.3 树形索引树形索引2 3 树树删除操作删除操作情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，解决方法：兄弟结点不够借

27、，需要合并相邻结点，并影响双亲结点，这可能减少树的高度。并影响双亲结点，这可能减少树的高度。2520数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.3 树形索引树形索引2 3 树树删除操作删除操作情况情况2：从包含：从包含1个记录的叶子结点中删除这个记录。个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点，这可能减少树的高度。并影响双亲结点，这可能减少树的高度。45 4750 5233 4820 252-3树的优点：能够以相对较低的代价保持树高平衡。树的优点：能够以相对较低的代价

28、保持树高平衡。 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.3 树形索引树形索引2 3 树树删除操作删除操作情况情况3：从内部结点删除一个记录。：从内部结点删除一个记录。 解决方法：将被删除记录用右边子树中的最小关键码解决方法：将被删除记录用右边子树中的最小关键码Y代替（代替（ Y一定在某个叶子结点中），然后再删除一定在某个叶子结点中），然后再删除Y。18 331223 3048101520 21243145 4750 52数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术9.3 树形索引树形索引2 3 树树删除操作删除操作情况情况3：从内部结点删除一个记录。：从内部结点删除一个记录。 解决方法：将被删除记录用右边子树中的最小关键码解决方法：将被删除记录用右边子树中的最小关键码Y代替（代替（ Y一定在某个叶子结点中），然后再删除一定在某个叶子结点中），然后再删除Y。20 331223 3048101521243145 4750 52数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第9章索引技术B树树9.3 树形索引树形索引m阶阶B树：是满足下列特性的树：树：是满足下列特性的树：