




已阅读5页,还剩39页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第九章索引技术 本章的基本内容是 索引的基本概念线性索引技术树形索引 9 1索引的基本概念 数据结构的最终目的是提高数据的处理速度 索引是为了加快查找速度而设计的一种数据结构 索引技术是组织大型数据库以及磁盘文件的一种重要技术 在索引问题以及数据库中 常常将数据元素称为记录 文件 通常指存储在外存上的记录集合 索引 把一个关键码与它对应的记录相关联的过程 索引由若干索引项构成 索引项至少应包含关键码和关键码对应的记录在存储器中的位置等信息 静态索引 索引结构在文件创建时生成 一旦生成就固定下来 只有当文件再组织时才允许改变 动态索引 在文件创建时生成索引结构 在文件执行插入 删除等操作时 索引结构本身也随之发生改变 9 1索引的基本概念 索引的基本概念 线性索引 若将索引项组织为线性结构 则称其为线性索引或索引表 树形索引 若将索引项组织为树结构 则称其为树形索引 多级索引 对索引再建立一个索引 就构成了多级索引 9 1索引的基本概念 索引的基本概念 对一些大型文件 其索引本身可能也很大 在这种情况下 可以建立多级索引 稠密索引 在线性索引中 若文件中的每个记录对应一个索引项 则这种索引称为稠密索引 在稠密索引中 无论文件是否按关键码有序 索引项总是按关键码顺序排列 只要内存空间允许 通常把稠密索引存储在内存中 从而大大提高记录的查找速度 稠密索引 9 2线性索引技术 稠密索引主要适用于静态索引 稠密索引示例 9 2线性索引技术 有序 无序或有序 优点 实现对数据库记录有效的查找 采用折半查找技术 和随机访问 按记录号访问 缺点 如果文件中包含的记录太多 索引表本身可能会因为太大而无法在内存中存储 文件中插入或删除记录 必须更新稠密索引 而稠密索引的插入和删除操作代价很高 9 2线性索引技术 稠密索引 文件 外存 稠密索引 内存 分块索引 9 2线性索引技术 稠密索引空间代价很大 分块索引 分块索引需要将文件划分为若干块 且要求分块有序 多级索引 9 2线性索引技术 分块索引 有序 9 2线性索引技术 分块索引 在分块索引表中进行的查找称为分块查找 也称为索引顺序查找 分两步进行 在索引表中确定待查关键码所在的块 在相应块中查找待查关键码 块内查找 顺序查找 设有n个记录的文件分为m个块 每个块均为t个记录 则n m t 设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 18 21 33 21 23 9 3树形索引 2 3树 插入操作 新记录将插入到相应的叶子结点中 1833 9 3树形索引 2 3树 插入操作 新记录将插入到相应的叶子结点中 9 3树形索引 2 3树 插入操作 新记录将插入到相应的叶子结点中 9 3树形索引 2 3树 插入操作 新记录将插入到相应的叶子结点中 1833 12 2330 48 10 15 2021 24 31 4547 505255 插入 9 3树形索引 2 3树 插入操作 新记录将插入到相应的叶子结点中 1833 12 2330 48 10 15 2021 24 31 4547 分裂 50 55 52 9 3树形索引 2 3树 插入操作 新记录将插入到相应的叶子结点中 1833 12 2330 10 15 2021 24 31 4547 提升 50 55 4852 9 3树形索引 2 3树 删除操作 情况1 从包含2个记录的叶子结点删除1个记录 解决方法 直接删除这个记录 1833 12 2330 48 10 15 24 31 4547 5052 9 3树形索引 2 3树 删除操作 情况1 从包含2个记录的叶子结点删除1个记录 解决方法 直接删除这个记录 21 9 3树形索引 2 3树 删除操作 情况2 从包含1个记录的叶子结点中删除这个记录 解决方法 向兄弟结点借一个记录 同时修改双亲结点的记录 1833 12 2130 48 10 15 20 23 31 4547 5052 9 3树形索引 2 3树 删除操作 情况2 从包含1个记录的叶子结点中删除这个记录 解决方法 向兄弟结点借一个记录 同时修改双亲结点的记录 1833 12 2130 48 10 15 20 23 31 4547 5052 9 3树形索引 2 3树 删除操作 情况2 从包含1个记录的叶子结点中删除这个记录 解决方法 兄弟结点不够借 需要合并相邻结点 并影响双亲结点 1833 12 2021 48 10 15 30 31 4547 5052 9 3树形索引 2 3树 删除操作 情况2 从包含1个记录的叶子结点中删除这个记录 解决方法 兄弟结点不够借 需要合并相邻结点 并影响双亲结点 1833 12 2021 48 10 15 30 31 4547 5052 9 3树形索引 2 3树 删除操作 情况2 从包含1个记录的叶子结点中删除这个记录 解决方法 兄弟结点不够借 需要合并相邻结点 并影响双亲结点 2021 48 33 31 4547 5052 9 3树形索引 2 3树 删除操作 情况2 从包含1个记录的叶子结点中删除这个记录 1012 1830 解决方法 兄弟结点不够借 需要合并相邻结点 并影响双亲结点 48 33 30 4547 5052 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 2033 12 2330 48 10 15 21 24 31 4547 5052 B 树 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 m 1 为关键码的个数 Ki 1 i n 为关键码 且Ki Ki 1 1 i n 1 Ai 0 i n 为指向子树根结点的指针 且指针Ai所指子树中所有结点的关键码均小于Ki 1大于Ki B 树 9 3树形索引 118 111 127 139 3475364 199 F F F F F F F F F F F F 24378 135 9 3树形索引 B 树示例 B 树 m阶B 树 是满足下列特性的
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年横琴低空经济产业发展趋势与挑战分析报告
- 2025年无人机黑飞行为识别与电子围栏技术应用案例分析报告
- 低空经济2025年无人机动力系统研发团队激励机制创新报告
- 2025年辅警招聘考试试题库带答案
- 安徽2025年住房和城乡建设领域现场专业人员培训考试(设备安装施工员专业基础知识)题库及答案
- 2025年海南省人民警察司晋督培训考试(综合类)复习题及答案
- 2025年江西省鹰潭市公安招聘留置看护勤务辅警法律基础综合训练题库及答案
- 2025年安全生产考试题含答案库(消防安全应急处置)实战演练试题含答案
- 2025年海南交通协警员招聘考试(道路交通安全法规)模拟题及答案
- 短信平台服务合同范本6篇
- 气象科研课题申报书
- 人工智能+开放共享城市安全监控数据共享分析报告
- 2023年中级统计师《统计工作实务》试题真题及答案
- 新疆质量安全总监培训课件
- 灌溉水源保障与应急供水预案方案
- 心理健康指导手册方案
- 电厂安全学习培训课件
- 电信安装人员安全培训课件
- 滑动轴承合金课件
- 2025秋新教材统编版(2024)八年级上册道德与法治全册教案
- 2025年液冷数据中心项目投资可行性研究报告
评论
0/150
提交评论