索引与哈希-1.ppt

数据库系统专题AdvancedTopicsonDatabaseSystems 第一章索引与哈希 数据库专题讲义 第一章索引与哈希 1 1索引的基本概念1 2树结构索引ISAM索引B 树索引1 3基于哈希的索引静态哈希可扩展哈希线性哈希 1 4其他索引技术倒排索引多维索引高维索引 数据库专题讲义 1 1索引的基本概念 一个索引是用来提高基于查找关键字的查找速度 查找关键字不同于关键字的概念 一般索引由的集合组成索引性能评价指标访问类型 值查找与范围查找时间开销 查找时间 插入时间 删除时间空间开销 索引所占的磁盘空间 数据库专题讲义 3 索引分类 主索引与辅助索引 主索引 如果数据文件是按某个索引的查找关键字来排序的话则称该索引是主索引 主索引的记录排序与数据文件相同辅助索引 如果数据文件的排序关键字与某个索引的查找关键字不同的话则称该索引为辅助索引 辅助索引的记录排序与数据文件不同顺序文件 一个主索引文件 在查找关键字上排序的数据文件 数据库专题讲义 3 索引分类 聚簇与非聚簇索引 数据库专题讲义 3 索引分类 稠密索引和稀疏索引 稠密索引 在数据文件中对于每个查找关键字的值都对应一个索引记录或索引入口稀疏索引 在数据文件中某些 而不是所有 查找关键字的值在索引文件中存在索引记录 数据库专题讲义 1 2树结构索引 ISAM 索引顺序存取方法 ISAM ISAM索引结构如下图所示索引入口 当索引文件本身变得很大时 可以形成索引文件的索引 这样就形成一个树形结构 数据库专题讲义 1 2树结构索引 ISAM 根据记录的数量关键字的值分布 ISAM 静态索引 数据库专题讲义 ISAM树示例 假定一个节点可以存放2个入口项 数据库专题讲义 插入23 48 41 42 数据库专题讲义 删除42 51 97 数据库专题讲义 ISAM树 查找cost logFN F 索引页中入口项数 N 叶子页面数插入 找到适当的叶子数据入口进行插入删除 找到适当的叶子数据入口进行插入ISAM 静态树结构索引的性能随着数据库的动态变化而降低 必要时需要重构索引 数据库专题讲义 1 2树结构索引 B 树 B 树示例 数据库专题讲义 B 树 8K页 36字节关键字 4字节指针 索引页中入口项数 200平均填充率 0 67 平均fanout 200 0 67 133索引能力h 3 1333 2 352 637 个记录 h 4 1334 312 900 700 个记录 索引大小h 1 1页 8Kh 2 133页 1Mh 3 1332 17 689页 133M 数据库专题讲义 B 树上的操作 查找 略 Cost logFN插入找到适当的叶子节点L向L插入数据入口项若L有空闲入口项 则插入分裂L L和L2均匀分配入口项将指向L2的索引入口插入到L的父节点中可能会引起递归分裂Cost logFN 数据库专题讲义 向示例B 树中插入8 最左边的叶子节点分裂5入口项向上插入到根节点 根节点插入入口项5后引起根节点的递归分裂 L L2 数据库专题讲义 插入8 后的B 树 数据库专题讲义 B 树上的删除 找到适当的叶子节点L删除入口项如果L中的填充率 0 5 删除完毕否则重分布L和L的一个兄弟 同父节点 节点入口项若失败则合并这2个节点如果合并发生则从L的父节点中删除指向L或其兄弟节点的入口项这种合并可能回向上递归发生 数据库专题讲义 删除19 和20 后的B 树 数据库专题讲义 删除24 后 数据库专题讲义 练习 插入值37 下列B 树将如何变化 数据库专题讲义 练习 删除14和16之后下面的B 输将如何变化 数据库专题讲义 1 3基于哈希的索引 树结构索引能够支持等查找和范围查找基于哈希的索引仅能支持等查找哈希桶 是哈希索引组织中的存储单位 可包含一个或多个索引记录 典型地一个桶可以是一个磁盘块从逻辑上看 对于给定的一个查找关键字k 通过计算一个哈希函数f k 即可得到包含该关键字k的哈希桶的物理地址 数据库专题讲义 哈希函数 一个好的哈希函数应该将数据记录均匀地散列到哈希桶中使得各个桶中的记录数相同均匀分布随机分布倾斜分布正太分布Zipf分布适用于不同的数据类型 数据库专题讲义 静态哈希 较长的溢出链会导致性能下降可扩展哈希和线性哈希可解决这一问题 数据库专题讲义 可扩展哈希 选择一个哈希函数 该函数的哈希结果为b位的二进制的数 一般b 32并不为每个哈希值建立一个哈希桶 只有当数据记录被插入到数据库文件中 才为这些数据记录建立相应的哈希桶 数据库专题讲义 可扩展哈希 在初始时 使用哈希值的i位而不是整个b位 0 i b 用作桶地址表的偏移 i值随数据库大小的变化而变大和减小 i称为全局深度 globaldepth 几个连续的表入口可以指向同一哈希桶 这些桶具有公共的哈希后缀 桶的公共哈希后缀的长度 i 若哈希桶j的公共哈希后缀的长度为 ij 则指向该桶的哈希地址表的入口数为 2 i ij 数据库专题讲义 可扩展哈希 插入20后 数据库专题讲义 可扩展哈希 插入20后 目录增长与缩减 数据库专题讲义 可扩展哈希 4 000000000000010012 000000000000110032 000000000010000016 0000000000010000 数据库专题讲义 可扩展哈希 1 00000000000000015 000000000000010121 000000000001010113 0000000000001101 数据库专题讲义 可扩展哈希 10 000000000000101015 00000000000011117 000000000000011119 0000000000010011 数据库专题讲义 练习 假设我们使用可扩展哈希方法来索引一个数据文件 该数据文件包含下列查找关键字值 2 3 5 7 11 19 23 29 31 若采用的哈希函数为h x xmod8 且每个桶能包含3个记录 试画出其可扩展哈希结构 数据库专题讲义 练习 当数据库发生下列变化时 给出每一步的可扩展哈希索引结构 1 Delete11 2 Delete31 3 Insert1 4 Insert15 数据库专题讲义 1 4其他索引技术 倒排索引 倒排索引是一种全文索引 用来索引各类文档网页 Word PDF PS PPT等文档与面向记录的索引相比记录 文档记录查找 文档检索查找键 文档中的词基本思想为每个检索词建立索引桶桶的指针指向检索词所出现的文档 数据库专题讲义 1 4其他索引技术 倒排索引 数据库专题讲义 1 4其他索引技术 倒排索引 扩充倒排索引的桶以包含更多信息 数据库专题讲义 1 4其他索引技术 多维索引 多维索引是对一维的树形索引的一种多维扩展 用来索引各种空间对象 有时也称为空间索引空间数据库 移动数据库 数据仓库等与一维索引相比记录 多维对象基于关键字的记录查找 范围查找 近邻查找一维查找关键字 多维查找关键字典型代表R tree R tree R tree X tree SS tree SR treeGrid file k d tree Quard tree等 数据库专题讲义 1 4其他索引技术 多维索引R tree 索引的基本思想 使用MBR来表示空间对象MBR 使用左下角和右上角来表示 L1 L2 O1 O2 O3 O4 O1 MBR O1 对象O1 L1 L2 数据库专题讲义 1 4其他索引技术 多维索引R tree 索引的基本思想 形成多级索引 A B C D E F G H G H A B C D E F 索引入口项 L1 L2 指针 数据库专题讲义 1 4其他索引技术 多维索引R tree 索引的基本思想 一个实际的例子 数据库专题讲义 1 4