[理学]北京信息科技大学数据机构课件第9章 索引技术.ppt

倒排表： 倒排表（reverse list）是对次关键字建立的一种索引表，在倒排表中，索引项包括次关键字的值和具有该值的各记录的地址，其结构如下： 18 33 12 21 30 48 10 15 20 23 31 45 47 50 52 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：向兄弟结点借一个记录，同时修改双亲结点的记录。 9.6 树形索引——2-3树 18 33 12 21 30 48 10 15 20 23 31 45 47 50 52 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。 9.6 树形索引——2-3树 18 33 12 20 21 48 10 15 30 31 45 47 50 52 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。 9.6 树形索引——2-3树 18 33 12 20 21 48 10 15 30 31 45 47 50 52 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。 9.6 树形索引——2-3树 20 21 48 33 31 45 47 50 52 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 10 12 18 30 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点。 9.6 树形索引——2-3树 48 33 30 45 47 50 52 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点，这可能减少树的高度。 25 20 9.6 树形索引——2-3树 2 – 3 树——删除操作 情况2：从包含1个记录的叶子结点中删除这个记录。 解决方法：兄弟结点不够借，需要合并相邻结点，并影响双亲结点，这可能减少树的高度。 45 47 50 52 33 48 20 25 2-3树的优点：能够以相对较低的代价保持树高平衡。 9.6 树形索引——2-3树 2 – 3 树——删除操作 情况3：从内部结点删除一个记录。 解决方法：将被删除记录用右边子树中的最小关键码Y代替（ Y一定在某个叶子结点中），然后再删除Y。 18 33 12 23 30 48 10 15 20 21 24 31 45 47 50 52 9.6 树形索引——2-3树 2 – 3 树——删除操作 情况3：从内部结点删除一个记录。 解决方法：将被删除记录用右边子树中的最小关键码Y代替（ Y一定在某个叶子结点中），然后再删除Y。 20 33 12 23 30 48 10 15 21 24 31 45 47 50 52 9.6 树形索引——2-3树 1. B－树的定义 9.6 树形索引——B_树 m阶B－树：是满足下列特性的树： ⑴ 所有叶子结点都在同一层上，并且不带信息，叶子的双亲称为终端结点。 ⑵ 树中每个结点至多有m棵子树； ⑶ 若根结点不是终端结点，则至少有两棵子树； ⑷ 除根结点外，其他非终端结点至少有?m/2? 棵子树； B－树是2－3树的推广，2-3树是一个3阶B－树 。 * 数据结构（C版） 清华大学出版社 第九章 查找与索引技术 本章的基本内容是： 9.4 索引的基本概念 9.5 线性索引技术 9.6 树形索引 9.4 索引的基本概念 数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构，索引技术是组织大型数据库以及磁盘文件的一种重要技术。 在索引问题以及数据库中，常常将数据元素称为记录。 文件：通常指存储在外存上的记录集合。 索引：把一个关键码与它对应的记录相关联的过程。索引由若干索引项构成，索引项至少应包含关键码和关键码对应的记录在存储器中的位置等信息。 静态索引：索引结构在文件创建时生成，一旦生成就固定下来，只有当文件再组织时才允许改变。 动态索引：在文件创建时生成索引结构，在文件执行插入/删除等操作时，索引结构本身也随之发生改变。 9.4 索引的基本概念 索引的基本概念 线性索引：若将索引项组织为线性结构，则称其为线性索引或索引表； 树形索引：若将索引项组织为树结构，则称其为树形索引。 多级索引：对索引再建立一个索引，就构成了多级索引。 9.4 索引的基本概念 索引的基本概念 对一些大型文件，其索引本身可能也很大，在这