索引与哈希-1.ppt

数据库系统专题Advanced Topics on Database Systems 第一章 索引与哈希 第一章 索引与哈希 1.1 索引的基本概念 1.2 树结构索引 ISAM索引 B+树索引 1.3 基于哈希的索引 静态哈希 可扩展哈希 线性哈希 1.1 索引的基本概念 一个索引是用来提高基于查找关键字的查找速度，查找关键字不同于关键字的概念，一般索引由查找关键字值,记录指针的集合组成 索引性能评价指标 访问类型：值查找与范围查找 时间开销：查找时间、插入时间、删除时间 空间开销：索引所占的磁盘空间 (3) 索引分类 -- 主索引与辅助索引 主索引：如果数据文件是按某个索引的查找关键字来排序的话则称该索引是主索引，主索引的记录排序与数据文件相同 辅助索引：如果数据文件的排序关键字与某个索引的查找关键字不同的话则称该索引为辅助索引，辅助索引的记录排序与数据文件不同 顺序文件：一个主索引文件+在查找关键字上排序的数据文件 (3) 索引分类 -- 聚簇与非聚簇索引 (3) 索引分类 -- 稠密索引和稀疏索引 稠密索引：在数据文件中对于每个查找关键字的值都对应一个索引记录或索引入口 稀疏索引：在数据文件中某些（而不是所有）查找关键字的值在索引文件中存在索引记录 1.2 树结构索引 -- ISAM 索引顺序存取方法(ISAM) ISAM索引结构如下图所示 索引入口：查找关键字值, pid 当索引文件本身变得很大时，可以形成索引文件的索引，这样就形成一个树形结构 1.2 树结构索引 -- 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页=8K h=2：133页=1M h=3：1332=17,689页=133M B+树上的操作 查找(略)：Cost = logFN 插入 找到适当的叶子节点L 向L插入数据入口项 若L有空闲入口项，则插入 分裂L==L和L2 均匀分配入口项 将指向L2的索引入口插入到L的父节点中 可能会引起递归分裂 Cost = logFN 向示例B+树中插入8* 最左边的叶子节点分裂 5入口项向上插入到根节点 插入8*后的B+树 B+树上的删除 找到适当的叶子节点L 删除入口项 如果L中的填充率?0.5，删除完毕 否则 重分布L和L的一个兄弟(同父节点)节点入口项 若失败则合并这2个节点 如果合并发生则从L的父节点中删除指向L或其兄弟节点的入口项 这种合并可能回向上递归发生 删除19*和20*后的B+树 删除24*后 练习 练习 1.3 基于哈希的索引 树结构索引能够支持等查找和范围查找 基于哈希的索引仅能支持等查找 哈希桶：是哈希索引组织中的存储单位，可包含一个或多个索引记录，典型地一个桶可以是一个磁盘块 从逻辑上看，对于给定的一个查找关键字k，通过计算一个哈希函数f(k)即可得到包含该关键字k的哈希桶的物理地址 哈希函数 一个好的哈希函数应该将数据记录均匀地散列到哈希桶中使得各个桶中的记录数相同 均匀分布 随机分布 倾斜分布 正太分布 Zipf分布 适用于不同的数据类型 静态哈希 较长的溢出链会导致性能下降 可扩展哈希和线性哈希可解决这一问题 可扩展哈希 选择一个哈希函数，该函数的哈希结果为b位的二进制的数，一般b=32 并不为每个哈希值建立一个哈希桶，只有当数据记录被插入到数据库文件中，才为这些数据记录建立相应的哈希桶。 可扩展哈希 在初始时，使用哈希值的i位而不是整个b位(0 i b)用作桶地址表的偏移，i值随数据库大小的变化而变大和减小 -- i称为全局深度(global depth) 几个连续的表入口可以指向同一哈希桶，这些桶具有公共的哈希后缀，桶的公共哈希后缀的长度〈= i。若哈希桶 j的公共哈希后缀的长度为：ij , 则指向该桶的哈希地址表的入口数为: 2(i-ij) 可扩展哈希 可扩展哈希 可扩展哈希 4： 0000 0000 0000 0100 12：0000 0000 0000 1100 32：0000 0000 0010 0000 16：0000 000