一维索引组织结构PPT课件

2020 4 20 1 高级数据库课程 第2章 一维索引组织结构 第一部分数据库系统基础第二部分数据库的数据存储管理第三部分数据库查询处理 2020 4 20 2 引言 整个关系在储存中如何存储与表示 以及怎样才能有效检索与定位 比如 如何回答象SELECT FROMR这样一个简单查询 2020 4 20 3 引言 我们可能不得不检索辅存中的与数据库文件对应的每个存储块 且还得依赖块首部中存在足够得信息来表明该块记录从什么地方开始 块中记录属于什么关系 有效的解决方案 采用索引结构 2020 4 20 4 索引 索引是一种数据结构 它以记录的特征 通常是一个或多个字段的值 为输入 并能 快速地 找出具有该特征的记录 2020 4 20 5 引言 查找键 建立索引的字段索引方法 1 顺序文件上的简单索引 2 非排序文件上的辅助索引 3 B树 一种可以在任何文件上建立索引的常用方法 4 散列表 2020 4 20 6 2 1顺序文件上的索引 相关概念 数据文件存放一个关系所有元组数据的文件 顺序文件按关系中指定的一个或多个字段组合值 键 排序的数据文件 索引文件为方便检索数据文件中元组 而建立的一个独立的辅助文件或辅助关系 索引项或索引记录通常包含两个字段 键和指针 索引表通常很小 按索引项 记录或元组 与关系中元组的对应方式 可将索引分为稠密索引和稀疏索引两类 2020 4 20 7 2 1顺序文件上的索引 稠密索引 稠密索引的数据结构组织形式稠密索引文件的特点使用稠密索引文件的好处 索引文件 数据文件 元组按主键排序每个存储块只存放两个记录 2020 4 20 8 2 1顺序文件上的索引 稠密索引 稠密索引的数据结构组织形式稠密索引文件的特点是一个独立文件 占用系列存储块 块中仅存放记录键和指向记录的指针 每个索引项对应相应数据文件中的一条记录 通常其大小要明显小于数据文件 稠密索引的查找使用稠密索引文件的好处 2020 4 20 9 2 1顺序文件上的索引 稠密索引 稠密索引的数据结构组织形式稠密索引文件的特点稠密索引的查找支持按给定键值查找相应记录的查询给定一个键值K 1 现在索引块中查找K 2 找到K后 按照K所对应的指针到数据文件中寻找相应的记录使用稠密索引文件的好处 2020 4 20 10 2 1顺序文件上的索引 稠密索引 稠密索引的数据结构组织形式稠密索引文件的特点稠密索引的查找使用稠密索引文件的好处索引数据块通常比数据块少 I 0次数少 如果索引足够小 甚至可以将整个索引放在内存缓冲区中 则只需一次性读入索引的I O 就可以定位任意的记录 由于索引文件中键被排序 可用二分法快速查找 若有n个索引项 最多只需要查log2n个块 2020 4 20 11 2 1顺序文件上的索引 稀疏索引 稀疏索引的数据结构组织形式稀疏索引文件的特点 2020 4 20 12 2 1顺序文件上的索引 稀疏索引 稀疏索引的数据结构组织形式稀疏索引文件的特点为每个存储块设一个键 指针对键值是每个数据块中第一个记录的对应值稀疏索引的查找与稠密索引比较 2020 4 20 13 2 1顺序文件上的索引 稀疏索引 稀疏索引的数据结构组织形式稀疏索引文件的特点稀疏索引的查找找出键值为K的记录 1 在索引中查找键值小于或等于K的最大键值 2 根据指针找到相应数据块 3 搜索数据块以找到键值为K的记录与稠密索引比较 2020 4 20 14 2 1顺序文件上的索引 稀疏索引 稀疏索引的数据结构组织形式稀疏索引文件的特点稀疏索引的查找与稠密索引比较 1 节省了存储空间 2 查找给定值的记录需要更多时间例 查询 是否存在键值为K的记录 稠密索引只需考虑键K在索引中的存在稀疏索引要执行I O操作去检索可能存在键值为K的记录的块 2020 4 20 15 2 1顺序文件上的索引 多级索引 在索引的基础上 再建索引 2020 4 20 16 2 1顺序文件上的索引 多级索引 如对主索引再建立一级稀疏索引 即对每个索引块建立一个索引记录 就形成了二级索引 此时外层索引块可常驻内存 在查找记录时内层索引块只要读1次就行 如果外层索引块的数目太多 不能全部进内存 那么可对最外层索引再外建一层索引 这就形成了多级索引技术 二级以上索引肯定是稀疏索引 一级索引通常是稠密的 多级索引的性能及管理的方便性不如B树结构 2020 4 20 17 2 2辅助索引 应用背景 在实际的DB应用中 经常需要进行针对非主属性的查询 为了加快查询的速度 也可以对非主属性建立索引 SELECTname addressFROMmovieStarWHEREbirthDate DATE 1995 01 01 可在属性上建立索引 CREATEINDEXi birthDateONmovieStar birthDate 相对与主键索引 我们称之为辅助索引 2020 4 20 18 2 2辅助索引 基本特点与设计 辅助索引的特点可能存在重复键 数据文件一般不按辅助索引键排序 辅助索引设计必须是稠密的索引结构 索引文件中索引项按键值排序 可根据需要建立二级或多级索引存在空间浪费 如某个键在数据文件中出现n次 那么这个键值将在索引文件中出现n次 2020 4 20 19 2 2辅助索引 基本特点与设计 如果查找键的值的顺序与主文件的顺序不一致 那么这种索引称为辅助索引 或非聚集索引 辅助索引总是稠密索引 通常有重复值辅助索引的索引项按键值排序辅助索引的指针不是指向一个或几个连续存储块 而是指向很多不同的块 例 k 20要查找两个索引块 还要访问指针指向的三个不同的数据块 2020 4 20 20 2 2辅助索引 应用 堆文件 1 最基本最简单的文件结构 2 记录不以任何顺序存放 3 记录可能放在不邻接的块上聚簇文件 1 RDB单关系上的聚簇 将记录按某个字段顺序排列在块中 2 RDB多关系上的聚簇 一个块中存储不同类型的记录 两个或多个关系的元组被混在一起 2020 4 20 21 2 2辅助索引 应用 顺序文件建立附加索引堆结构的主索引文件聚簇文件 2020 4 20 22 2 2辅助索引 应用 聚簇文件例 Movie title year length studioname Studio name address president SELECTpresidentFROMMovie StudioWHEREtitle Star ANDMovie studioname Studio name为了使此种连接效率更高 采用聚簇文件结构 关系Movie的元组和Studio的元组存放在相同的一系列块中 每个Studio元组后面存放关系Movie中该制片厂的所有电影元组 2020 4 20 23 2 2辅助索引 应用间接索引层 桶 2020 4 20 24 2 2辅助索引 应用间接索引层 桶 索引结构组织间接层的桶中只存放指针 只要键值的总长度大于指针 就可以较好克服一般辅助索引中的空间浪费现象 可以在不访问数据文件记录的前提下 利用桶指针帮助问题以下一些问题 当查询有多个条件 且每个条件都有可用的索引时 可以通过在主存中对指针集合求交集 来找出满足所有条件的记录 然后 只需检索交集中指针指向的记录 从而节省了不必要的I O 2020 4 20 25 2 2辅助索引 应用间接索引层 桶 辅助索引可以采用上面的方法实现 仍然为每个查找键值建立一个索引记录 内容包括查找键值和一个指针 但这个指针不指向主文件中的记录 而是指向一个桶 桶内存放指向具有同一查找键值的主记录的指针 如上图所示 辅助索引的指针并不直接指向文件 而是每个指针指向一个包含文件指针的存储桶 存储桶中的每个指针都指向文件中的记录 使用桶介于辅助索引和数据文件之间 节约空间 避免键值重复 2020 4 20 26 2 2辅助索引 应用间接索引层 桶 可以通过在主存中对指针集合求交来找到满足所有条件的指针 只需要检索交集中指针指向的记录 SELECTtitleFROMMovieWHEREstudioname Disney ANDyear 1995 2020 4 20 27 2 3数据文件修改期间的索引维护 索引文件是顺序文件 到目前为止 我们都假设数据文件和索引文件由一些连续的 装满某种类型记录的存储块组成 由于在实际应用中 总是需要不断地对数据进行插入 删除 修改 这势必会导致顺序文件这样的组织发生变化和调整 2020 4 20 28 2 3数据文件修改期间的索引维护 当数据文件变化后 通常必须对索引文件进行相应的调整 以适应数据文件的变化 索引文件的调整可借鉴数据文件中所用的一些策略 2020 4 20 29 2 4基于B树的索引 B树的结构特点 B树结构 B树查询 B树插入 B树删除 B树效率 应用方式 2020 4 20 30 2 4基于B树的索引 B树的结构特点 m阶B树节点的子节点数约束最大约束 每个节点至多有m个子节点 最少约束根节点 最少要有两个子节点叶节点 可以没有子节点 内节点 至少有 m 2 子节点所有的叶节点都在同一层 非叶节点的键与指针有j个键的非叶节点 恰好包括j 1个子节点指针节点的形式 P0 K0 P1 K1 P2 K2 Pj 1 Kj 1 Pj将B树扩展为B 树 使之适合于DB索引应用每个叶节点至少有 m 1 2 个指针指向数据记录 最后一个指针指向它右边的下一个右节点 最后1个叶节点的最后1个指针可为空 B树 2020 4 20 31 2 4基于B树的索引 B树的结构特点 B树 2020 4 20 32 2 4 2基于B树的索引 B树的查找 归纳查找基础 若已经处于叶节点 则只需在结点内搜索 归纳 若处于某内部节点 且它的键值为K1 K2 Kj 1 如k k1 第一个子节点 k1 k k2第2个节点 例 查找k 41的记录 范围查找只要先找到下限起点 然后顺着找下去 直到找到一个大于上限的键为止 例 查找范围 10 25 B树 2020 4 20 33 2 4 3基于B树的索引 B树的插入 定位合适的叶节点 令为N 如有空 插入即可结束如无空 在N右边创建一个新的节点M 并按下面步骤进行调整安排 重排插入新键后N中的键序 共 n 1 个前 n 1 2 个键 指针对留在N中 其它移入M中 至少有 n 1 2 个 M和N中键 指针对个数肯定都能满足约束条件 转下一步 调整N M的上层父节点 调整N M的上层父节点 NP MP 递归调整NP MP的上层节点 直到完成 必要时可能还要增加树的层数 B树 2020 4 20 34 2 4 3基于B树的索引 B树的插入 调整M N的上层节点在原N的父节点NP中插入一个新的键 值指针对 重排NP键值重调整NP的所有子结点指针 如键值数不超限 插入结束 否则转下一步分裂NP 分裂NP为 NP MP MP是新的紧靠NP右边的兄弟节点 前 n 1 2 指针留在NP中 后 n 1 2 指针移入MP中 前 n 2 个键保留在节点NP中 后 n 2 个键移到节点MP中 中间的键K会被结点NP和MP的父结点用来划分在这两个结点之间的查找重计算NP MP中的键值 必要时调整NP MP的父节点 N的祖父节点 以正确划分NP MP中的键 递归调整NP MP的上层节点 直到完成 必要时可能还需增加树的层数 举例 在图4 23中插入键值40 B树 2020 4 20 35 2 4 4基于B树的索引 B树的删除 删除首先是查找定位 找到所在叶节点 令为N 后删除键 指针对 如删除后违反树约束 则需要进行相应调整若N有1键 指针对个数超过最小数的兄弟节点 则直接从中借用一个 但会导致上层父节点需要调整 若无兄弟节点可借 则可合并N到它的一个兄弟节点 这样 也可能会导致上层违反约束 则可能要从远亲借一个近邻的表兄弟节点 整个节点 沿树递归地删除 举例 在图4 23中分别删除7和11 教材P120 121 B树 2020 4 20 36 2 4 5B树的特点与效率 能自动保持与数据文件大小相适应的索引层次 能对所使用的空间进行管理 使得每个块的充满度在半满与全满之间 索引不需要溢出块读有B树索引的数据块的I O次数 B树的层数 1当B树阶数m很大时 插入 删除引起的调整大多限在叶子节点层 基本上可忽略B数重组带来的I O开销 可让B数的根结点永久驻留内存 把B数的第二层节点保存在主存缓冲区也是合理的 B树 2020 4 20 37 2 4 6B树的应用方式 查找键是主键 索引是稠密的 文件主键排序 B树稀疏索引 每个数据块对应B树叶节点的一个指针 用于非主键属性 且有重复键的情形 需修改内部节点的部分含义 引入最小新键的概念 叶节点中为数据文件里出现的每个属性值K设有一个键 指针对 其中指针指向排序键值为K的记录中的第一个 B树 2020 4 20 38 2 5基于散列的索引2 5 1散列 hash 的数据结构 散列函数及其选择原则要求 随机分布好 易计算 散列键 散列函数的参数 与散列值 散列函数结果值 维数为B的桶数组 0 B 1 被散列对象将根据其键值 计算散列值 然后保存到相应的桶中 桶内对象 按链连接起来 构成对象链 2020 4 20 39 2 5 1散列 hash 的数据结构 key h key 可以是记录或指向记录的指针 h k 散列函数 以查找键为参数并计算出一个介于0 B 1的整数 k是整数 k B的余数K是字符串 每个字符看成整数累加 B的余数 2020 4 20 40 2 5 1辅存散列表 静态散列表 桶数组为一组存储块 散列的插入 空间不够 桶溢出 可增加溢出链块 散列删除 删除后如某溢出块空 则应删除相应的溢出块 辅存散列的效率理想情况只需一次I O 非理想情况可能需要多次I O 存在对象链 溢出块链 2020 4 20 41 2 5 1辅存散列表 静态散列表 例 假定每个存储块只能存放2个记录B 4散列函数h的返回值0 3之间键值为a fh d 0h c h e 1h b 2h a h f 3则记录在块中的分布如图所示 0 1 2 3 d ceb af 链接溢出块 2020 4 20 42 2 5 1辅存散列表 静态散列表 散列表的插入查找键为k的记录需要被插入 1 计算h k 2 如果桶号为h k 的桶还有空间 把记录存放到此桶的存储块中 3 存储块没有空间时存储到块链上的某个溢出块中 4 如果桶的所有存储块都没有空间 增加一个新溢出块到该桶的链上 并把新记录存入该块例 增加一个键值为g的记录 且h g 1把记录加到1号桶增加一个新块 链到桶1的第1块上键值为g的记录插入到这一块中 0 1 2 3 d ceb af g 2020 4 20 43 2 5 1辅存散列表 静态散列表 散列表索引的效率理想情况是存储器有足够多的桶 使绝大多数桶都只由一个块组成 这样查询1次I O 比稀疏索引 稠密索引 B 树好得多 所以应设法减少每个桶的块数静态散列表 通的数目B不变动态散列表 允许B改变 使B近似于 记录总数 块中容纳记录数目的 每个桶大约有一个存储块 2020 4 20 44 2 5 2可扩展的散列表 引入一个间接层做桶 桶中仅保存指针 指针桶数组能增长 它的长度为2n 每次增长n n 1 桶数组长度扩一倍 多个连续的桶可共享 共同指向 一个数据块 每个数据块中有一个小凸块标记资格位数 j 散列的结果值 为K位二进制数 K可达到32位 足够 实际用的桶编号位数i k 用K的前 左边 i位i值作为结构一部分被保存 相对静态散列表的增强 2020 4 20 45 2 5 2可扩展的散列表 i 1 01 0001 1001 1100 1 1 例 1 假定k 4 即h产生4位二进制序列 2 使用位i 1 所以桶数组项 21 2项 0 1 3 桶数组的项指向二个块 第一块存放当前所有查找键被散列成以0开头的二进制序列的记录第二块存放所有查找键被散列成以1开头的二进制序列的记录 4 为方便 显示的记录键是散列函数将这些键转换成的二进制位序列 5 每个存储块的 小凸块 显示1 表明由散列函数得到的位序列中有多少位用于确定记录在该块中的成员资格 j 2020 4 20 46 2 5 2可扩展的散列表 插入 计算h k 并取结果 散列值 的前i位 根据它找到桶及对应的存储块 如存储块中有空间 插入即可 如无空间 按如下的两种情形处理 1 资格位数j i分裂存储块 然后根据散列值从左边算起的第j 1位的值 划分记录到分裂后的两个块中 1放在在新块中 0放在原块中 分裂后的两个块资格位j均增加1 调整桶数组中的指针 针对新块 2 资格位数j ii i 1 将桶数组扩大1倍 新桶数组W0 W1指向原W指向的块 按步骤 1 处理 2020 4 20 47 2 5 2可扩展的散列表 操作示例 2020 4 20 48 2 5 2可扩展的散列表 操作示例 2020 4 20 49 2 5 2可扩展的散列表 操作步骤 上例插入1010 1 第1位是1 属于第2个块 2 该块已满需要分裂 3 j i 1将桶数组加位i 2 4 根据第2位 为0 记录1001 1010划分到原块 为1 记录1100划分到新块 5 分裂后的两个块成员资格位j均增加1变为2 6 调整桶数组中的指针 针对新块 2020 4 20 50 2 5 2可扩展的散列表 操作示例 插入键值分别为0000和0111的记录 因为j 1i 2j I所以不用调整桶数组 2020 4 20 51 2 5 2可扩展的散列表 应用 优点好处 查找非常直接 查桶数组 记录所在数据块内查找 桶数组通常驻留内存 实际只需1次I O 存在问题当桶数组翻倍时 要做大量的工作 翻倍后 主存可能放不下 会导致系统性能骤然下降 虽然记录不多 但因某些桶记录过分集中 可能导致桶编号位数 i 很大 空桶过多 例 i 20j 20 j 3 j 10记录总数远远小于220 2020 4 20 52 2 5 3线性散列 结构特点 结构参数 桶数n 桶编号位数i 记录总数r桶数n 2n 桶编号位数 log2n i 且从散列值的右边 低位 取相应位 桶数n增加缓慢 每插入一个记录 检查记录总数r与桶数n的比值r n是否超过设定的上限 如超过则增加一个桶 n增加后 检查编号位i是否需要加大 如增加则原有桶编号高位用0补齐 存储块并不总是可分裂 只有在增加一个桶时 才会引起一次块分裂 因此 可增加溢出块 结构参数与索引数据一同保存 2020 4 20 53 2 5 3线性散列 结构特点 例1 图中二个桶 0 1每个桶包含一个存储块散列值以0结尾的在0号桶散列值以1结尾的在1号桶i 当前被使用的散列函数值的位数n 当前的桶数r 当前散列表中的记录总数规则 数据文件中的记录的个数r 1 7n 桶的平均充满度不会超过存储块容量的85 r 2n 85 2020 4 20 54 2 5 3线性散列 插入记录 计算h k 并取散列值的后i位 令为aiai 1 a1 计算该数的二进制值为m 如m指定上限 增加一个桶 令桶号为ai 1ai a1值 并将该桶原先寄存在0ai a1桶中的记录取回本桶 如n 2i i i 1 所有原桶编号前补0 2020 4 20 55 2 5 3线性散列 插入记录举例 例2 插入键值散列为0101的记录 1 位序列以1结尾 记录属于第二个桶 2 r n 4 2 1 7n提高为3 2020 4 20 56 2 5 3线性散列 插入记录举例 3 2 所以桶 00 01 10 4 分裂桶000000在0桶1010在10桶 2020 4 20 57 2 5 3线性散列 插入记录举例 例3 增加键值散列为0001的记录 1 最后2位为 01 且01桶存在 把记录放在01桶中 2 该桶块已满 增加一个溢出块 3 三个记录按散列键的数值顺序保存 4 r n 5 3 1 5 1 7不需要创建新桶 2020 4 20 58 2 5 3线性散列 插入记录举例 例4插入键值散列为0111的记录 1 最后2位为11 但桶11不存在 2 把记录改为存入01桶 新记录存入该桶溢出块中 3 r n 6 3 2 1 7创建1个编号为11的新桶 4 分裂01桶的4个记录 01桶 0001 0101 11桶 0111 1111 5 删除01桶溢出块 0000 0001 0101 1010 0111 1111 00 01 10 i 2 n 3 r 6 2020 4 20 59 2 5 3线性散列 查询记录举例 例5查找散列键值为1010的记录 1 i 2查后2位10 看成二进制整数m 2 2 m n则编号为10的桶存在 到该桶中查找 3 检查记录的整个键来确定是否所需记录