第9章索引技术

第9章索引技术本章的基本内容是：索引的基本概念线性索引技术树形索引9.1索引的基本概念数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构，索引技术是组织大型数据库以及磁盘文件的一种重要技术。在索引问题以及数据库中，常常将数据元素称为记录。文件：通常指存储在外存上的记录集合。索引：把一个关键码与它对应的记录相关联的过程称为索引。索引由若干索引项构成。

索引项至少应包含关键码和关键码对应的记录在存储器中的位置等信息。静态索引：索引结构在文件创建时生成，一旦生成就固定下来，只有当文件再组织时才允许改变。动态索引：在文件创建时生成索引结构，在文件执行插入/删除操作时，索引结构本身也随之发生改变。9.1索引的基本概念索引的基本概念线性索引：若将索引项组织为线性结构，则称其为线性索引或索引表；树形索引：若将索引项组织为树结构，则称其为树形索引。多级索引：对索引再建立一个索引，就构成了多级索引。9.1索引的基本概念索引的基本概念对一些大型文件，其索引本身可能也很大，在这种情况下，可以建立多级索引。稠密索引：在线性索引中，若文件中的每个记录对应一个索引项，则这种索引称为稠密索引。在稠密索引中，无论文件是否按关键码有序，索引项总是按关键码顺序排列。只要内存空间允许，通常把稠密索引存储在内存中，从而大大提高记录的查找速度。稠密索引9.2线性索引技术稠密索引主要适用于静态索引。稠密索引示例9.2线性索引技术

8…20…52…35…40…61…56…关键码其它数据项文件r1r2r3r4r5r6r7

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

9.2线性索引技术稠密索引文件外存稠密索引内存分块索引9.2线性索引技术稠密索引空间代价很大减少索引项的个数分块索引分块索引需要将文件划分为若干块，且要求分块有序。块内无序：每一块内不要求有序块间有序：块与块之间有序分块有序多级索引每块建立一个索引项9.2线性索引技术分块索引35…20…8…52…40…61…65…88…76…第1块文件关键码其他数据项第2块第3块353613883索引表最大值块长块首地址有序9.2线性索引技术分块索引在分块索引表中进行的查找称为分块查找（也称为索引顺序查找），分两步进行：⑴在索引表中确定待查关键码所在的块；⑵在相应块中查找待查关键码。索引表查找顺序查找折半查找块内查找——顺序查找设有n个记录的文件分为m个块，每个块均为t个记录，则n=m×t。设Lb为查找索引表确定关键码所在块的平均查找长度，Lw为在块内查找关键码的平均查找长度，则分块查找的平均查找长度为：

ASL=Lb+Lw若采用顺序查找对索引表进行查找，则分块查找的平均查找长度为：

9.2线性索引技术分块索引

ASL=Lb+Lw=当t取时，ASL取最小值+1。nn9.2线性索引技术多重表稠密索引、分块索引对主关键码建立索引为文件建立索引的目的是什么?对主关键码进行查找对次关键码进行查找对次关键码建立索引多重表、倒排表9.2线性索引技术多重表多重表除了为文件建立一个主索引外，还为每个需要查找的次关键码建立一个索引。在文件中，为建立索引的次关键码分别增设一个指针域，用于将次关键码相同的记录链结在一起（稠密索引），或将在同一块中的记录链结在一起（分块索引）。关键码指针000100020003000400050006主索引9.2线性索引技术多重表次关键码头指针长度男013女033“性别”次索引次关键码头指针长度24~2602327~30013“年龄”次索引∧24∧男王东0006∧30∧女李爽0005062505女齐梅0004052704女刘楠0003042506男张亮0002033002男王刚0001年

龄性

别姓

名职工号文件关键码指针000100020003000400050006主索引9.2线性索引技术倒排表“年龄”倒排表

次关键码记录号表

24～2602,04,06

27～30

01,03,05“性别”倒排表

次关键码记录号表男01,02,06女03,04,0524男王东000630女李爽000525女齐梅000427女刘楠000325男张亮000230男王刚0001年龄性别姓名职工号文件9.3树形索引2–3树2-3树：是具有下列特性的树：⑴一个结点包含1个或者2个关键码。⑵每个内部结点有2个子女（包含一个关键码）或者3个子女（包含两个关键码）。⑶

所有叶子结点都在树的同一层。9.3树形索引2–3树示例18331223304810152021243145475052形状上有什么特性?9.3树形索引2–3树示例包含1个或者2个关键码；有2个子女或者3个子女；叶子结点在同一层。183312233048101520212431454750529.3树形索引2–3树示例结点的值有什么特性?183312233048101520212431454750529.3树形索引2–3树示例左子树中所有结点的值均小于第一个关键码的值；中间子树中所有结点的值均大于第一个关键码的值，且小于第二个关键码的值；右子树中所有结点的值均大于第二个关键码的值。18331223304810152021243145475052183312233048101520212431454750529.3树形索引2–3树——查找操作2118<21<3321<23比较次数不超过树的深度。由于2-3树是树高平衡的，而且每一个内部结点至少有2个子女，所以树的最大深度是。ëû1log2+n9.3树形索引2–3树——插入操作新记录将插入到相应的叶子结点中。18331223304810152021243145475052叶子结点只包含1个记录插入新记录

149.3树形索引2–3树——插入操作新记录将插入到相应的叶子结点中。叶子结点只包含1个记录插入新记录

18331223304815202124314547505210149.3树形索引2–3树——插入操作新记录将插入到相应的叶子结点中。18331223304810152021243145475052叶子结点只包含2个记录插入新记录，分裂－提升

559.3树形索引2–3树——插入操作新记录将插入到相应的叶子结点中。1833122330481015202124314547505255叶子结点只包含2个记录插入新记录，分裂－提升

插入9.3树形索引2–3树——插入操作新记录将插入到相应的叶子结点中。1833122330481015202124314547叶子结点只包含2个记录插入新记录，分裂－提升

分裂5055529.3树形索引2–3树——插入操作新记录将插入到相应的叶子结点中。18331223301015202124314547叶子结点只包含2个记录插入新记录，分裂－提升

提升50554852183312233048101520212431454750529.3树形索引2–3树——删除操作情况1：从包含2个记录的叶子结点删除1个记录。解决方法：直接删除这个记录。18331223304810152431454750529.3树形索引2–3树——删除操作情况1：从包含2个记录的叶子结点删除1个记录。解决方法：直接删除这个记录。21183312233048101520212431454750529.3树形索引2–3树——删除操作情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。1833122130481015202331454750529.3树形索引2–3树——删除操作情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。1833122130481015202331454750529.3树形索引2–3树——删除操作情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。18331220214810153031454750529.3树形索引2–3树——删除操作情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。18331220214810153031454750529.3树形索引2–3树——删除操作情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。2021483331454750529.3树形索引2–3树——删除操作情况2：从包含1个记录的叶子结点中删除这个记录。10121830解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。483330454750529.3树形索引2–3树——删除操作情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点，这可能减少树的高度。25209.3树形索引2–3树——删除操作情况2：从包含1个记录的叶子结点中删除这个记录。解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点，这可能减少树的高度。45475052334820252-3树的优点：能够以相对较低的代价保持树高平衡。9.3树形索引2–3树——删除操作情况3：从内部结点删除一个记录。解决方法：将被删除记录用右边子树中的最小关键码Y代替（Y一定在某个叶子结点中），然后再删除Y。183312233048101520212431454750529.3树形索引2–3树——删除操作情况3：从内部结点删除一个记录。解决方法：将被删除记录用右边子树中的最小关键码Y代替（Y一定在某个叶子结点中），然后再删除Y。203312233048101521243145475052B树9.3树形索引m阶B树：是满足下列特性的树：⑴所有叶子结点都在同一层上，并且不带信息，叶子的双亲称为终端结点。⑵树中每个结点至多有m棵子树；⑶若根结点不是终端结点，则至少有两棵子树；⑷除根结点外，其他非终端结点至少有m/2

棵子树；B－树是2－3树的推广，2-3树是一个3阶B－树

。所有非终端结点都包含以下数据：（n，A0，K1，A1，K2，…，Kn，An）其中，n（m/2

1≤n