数据库的存储结构

《数据库的存储结构》由会员分享，可在线阅读，更多相关《数据库的存储结构（55页珍藏版）》请在装配图网上搜索。

1、第 五 章 数 据 库 的 存 储 结 构 数 据 库 是 大 量 、 持 久 数 据 的 集 合 ， 在 现 阶 段用 内 存 作 为 数 据 库 的 存 储 介 质 是 不 合 适 的 。 n 活 动 头 磁 盘 的 存 取 时 间 由 三 部 分 组 成 ： 寻 道时 间 、 等 待 时 间 以 及 传 输 时 间 。n 磁 盘 上 的 数 据 划 分 为 大 小 相 等 的 物 理 块 。 磁盘 与 内 存 间 的 数 据 交 换 以 物 理 块 为 单 位 。 n 一 般 ， 在 磁 盘 和 内 存 之 间 设 立 缓 冲 区 以 解 决二 者 的 速 度 不 匹 配 问 题 。 由

2、 于 有 多 个 缓 冲 块 可 供 申 请 使 用 ， 磁 盘 的 读 写操 作 和 读 写 数 据 的 处 理 可 以 重 叠 进 行 。读 出 ： i块 缓 冲 块 A处 理 ： 处 理 A中 i块i+1块 缓 冲 块 B i+2块 缓 冲 块 A处 理 B中 i+1块 n 记 录 是 目 前 商 用 数 据 库 的 基 本 数 据 单 元 ， 有 定长 和 变 长 之 分 。n 记 录 的 存 储 结 构LIbbb MINGbbb MALEbb 19675 12 18 LI? MING? MALE? 1967#问 题 ： 字 段 中 也 需 要 用 到 这 些 分 隔 符 时 ， 如

3、何 进 行表 示 ？ 02LI04MING04MALE041967问 题 ： 计 数 法 对 字 段 的 实 际 长 度 有 什 么 要 求 ？ 5.2.2 记 录 在 物 理 块 上 的 分 配 设 为 物 理 块 的 有 效 空 间 大 小 ， 为 固 定 长 记录 的 大 小 ， 若 ， 则 每 个 物 理 块 可 容 纳 的 记 录数 为 ：p=B/R p称 为 块 因 子 （ Blocking Factor） 。 记 录 一 般 不 会 刚 好 填 满 物 理 块 ， 会 留 下 不 用 的 零 头空 间 ：Bp RR 为 了 利 用 这 部 分 空 间 ， 可 以 利 用 记 录

4、的 跨 块 存 储 组织 (spanned organization)。记 录 1 记 录 2 记 录 3 记 录 4 记 录 1 记 录 2 记 录 3 记 录 4块 i 记 录 4(剩 余 部分 ) 记 录 5 记 录 6 记 录 7块 i+1 记 录 1 记 录 2 记 录 3块 i 记 录 3(剩余 部 分 ) 记 录 4 记 录 5块 i+1 5.2.3 物 理 块 在 磁 盘 上 的 分 配 1、 连 续 分 配 法 （ contiguous allocation） 将 一 个 文 件 的 块 分 配 在 磁 盘 的 连 续 空 间 上 ，块 的 次 序 就 是 其 存 储 的 次

5、 序 ， 有 利 于 顺 序 存 取多 块 文 件 ， 不 利 于 文 件 的 扩 充 。 每 个 文 件 有 一 个 逻 辑 块 号 与 其 物 理 块 地 址 对照 的 索 引 。 IBM PC/XT 0000 #原 始 数 据IBM PC/XT 00001IBM PC/XT 00002 压 缩 数 据#1#2 索 引 法 示 例 ： BeijingNanjingShanghaiCITY表SHOP# CITY0001 Nanjing0002 Nanjing0003 Nanjing0004 Shanghai原 始 数 据0005 Shanghai SHOP# CITY000100020003

6、0004压 缩 数 据0005 不 同 类 型 的 访 问 各 有 其 使 用 的 文 件 结 构 和存 取 路 径 。 DBMS通 常 提 供 多 种 文 件 结 构 ， 供 数据 库 设 计 者 选 用 。1.堆 文 件 （ heap file）2.直 接 文 件 （ direct file）3.索 引 文 件 （ indexed file） 堆文件 记 录 1记 录 6记 录 2记 录 1记 录 2记 录 3记 录 5记 录 6记 录 4 堆文件 记 录 1记 录 3记 录 5记 录 6记 录 4记 录 7记 录 8记 录 2 假 设 ， 要 删 除 右 图 堆 文 件 中的 第 2，

7、4， 6条 数 据 记 录 。 直 接 删 除 这 三 条 记 录 的 情 况如 右 图 所 示 。 带 来 什 么 问 题 ？ 作 删 除标 记堆文件 记 录 1记 录 2记 录 3记 录 5记 录 6记 录 4记 录 7记 录 8 堆文件 记 录 1记 录 3记 录 5记 录 6记 录 4记 录 7记 录 8记 录 2 堆文件 记 录 1记 录 3记 录 5记 录 7记 录 8集 中 删 除记 录 ， 并进 行 记 录重 排 解 决 方 法 Student(SNO,SNAME,SEX,BIRTHDATE,DEPT)散 列 函 数 H(SNO)=Address900412 李 林 计 算 机

8、 系 H(900412)=addr addr 存 储 空 间900412 李 林 计 算 机 系 索 引 相 当 于 一 个 映 射 机 构 ， 把 关 系 中 相 应 记 录的 某 个 （ 些 ） 属 性 的 键 值 转 换 为 该 记 录 的 存 储 地址 （ 或 地 址 集 ） 。addr1addr2addr3 SNO Address学 生 表 的 索 引 文 件900412 addr2900417 addr1900418 addr3存 储 空 间900418 周 力 计 算 机 系900412 李 林 计 算 机 系900417 陈 燕 计 算 机 系 针 对 非 散 列 键 和 非

9、索 引 属 性 的 访 问 ， 都 不 能 有 效 发 挥 直接 文 件 或 索 引 文 件 的 优 势 。 散 列 或 索 引 失 效 时 ， 两 者 谁 的 访问 代 价 更 大 ？ n 非 稠 密 索 引 与 稠 密 索 引1.不 为 每 个 键 值 设 立 索 引 项 的 索 引 非 稠 密 索 引2.可 以 节 省 索 引 的 存 储 空 间 ， 代 价 是 文 件 要 按 索 引键 排 序3.对 一 个 文 件 ， 只 能 为 一 个 索 引 键 （ 一 般 为 主 键 ）建 立 非 稠 密 索 引 （ 为 什 么 ？ ） 示 例 查 找 索 引 键 为 211的 记 录 的 存

10、储 地 址211 7 211 稠 密 索 引 （ dense index） 从 数 据 结 构 角 度 看 ： 静 态 索 引 是 个 多 分 树 ； 动 态 索引 是 一 种 平 衡 多 分 树 （ 即 B-树 ） ， 常 用 B+树 。 B+树 的 限 制 和 规 定 ：q 每 个 节 点 最 多 有 2k个 键 值 ， k称 为 B+树 的 秩(Order);q 根 节 点 至 少 有 一 个 键 值 ， 其 它 节 点 至 少 有 k个 键 值 ,节 点 内 ， 键 值 有 序 存 放 ;q 除 叶 节 点 无 子 女 外 ， 其 它 节 点 若 有 J个 键 值 ， 则 有J+1个

11、子 女 ;q 所 有 叶 节 点 都 处 于 树 的 同 一 层 ， 即 树 始 终 保 持 平 衡 。 10 2015 从 根 向 叶 搜 索 ， 直 至 相 应叶 节 点 ， 若 该 叶 节 点 不 满 ， 则将 键 值 插 入 叶 节 点 中 ； 如 叶 节点 已 满 （ 即 已 经 有 2K个 键 值 ）， 则 将 此 叶 节 点 分 裂 为 二 ， 叶节 点 分 裂 后 ， 其 双 亲 节 点 也 必须 增 加 一 个 键 值 ， 若 双 亲 节 点不 满 ， 插 入 过 程 结 束 ； 否 则 双亲 节 点 继 续 分 裂 为 两 个 节 点 ，如 此 继 续 直 到 插 入 过

12、程 中 止 。插 入 算 法 ： (K=1): 10， 15， 20， 25， 30， 35， 40， 5010 15 10, 15 202520,25 30 10 15 20 30252010 15,25 3015 25 3510 20 30 40,50 先 从 根 节 点 出 发 ， 找 到待 删 除 键 值 所 在 叶 节 点 ； 若删 除 该 键 值 后 ， 叶 节 点 中 键值 数 减 为 K-1个 ， 则 向 其 左右 兄 弟 叶 节 点 借 一 个 键 值 ，以 保 持 每 个 叶 节 点 存 放 键 值不 少 于 K个 ； 若 其 左 右 叶 节点 都 只 有 K个 键 值 ，

13、 则 可 将该 叶 节 点 与 其 左 （ 或 右 ） 叶节 点 合 并 成 包 含 2K-1个 键 值的 叶 节 点 ， 合 并 后 ， 其 双 亲节 点 要 减 少 一 个 键 值 ， 有 可能 导 致 双 亲 节 点 的 合 并 。删 除 算 法 ： 15 25 3510 20 30 40,5010,15 3525,3510,15 30 40,50 SH ST索 引 集顺 序 集 节 点 类 型 块 中 索 引 键 数 0P 0K 1P 1K 1nK nP索 引 集 节点 0K 0tid 1K 1tid nK ntid顺 序 集 节点注 ：1.节 点 一 般 是 一 个 物 理 块 。2

14、.元 组 标 识 符 tid， 实 际 上 是 记 录 的 地 址 ， 由 块 号 和 记 录 在 块 中的 指 针 号 组 成 （ 使 用 记 录 在 块 中 的 指 针 号 表 示 记 录 在 块 中 的 位 置 ，好 于 直 接 用 记 录 在 块 中 的 地 址 ， 方 便 记 录 在 块 内 移 动 ） 。 P0 K0 Ki-1 Pi Ki Kn-1 PnKx KxKx 注 意 ： 索 引 集 节 点 中 的 键 值 不 一 定 是 文 件 中当 前 存 在 的 键 值 （ 仅 起 “ 导 航 路 标 ” 的 作用 ） 。 在 搜 索 过 程 中 ， 即 使 发 现 索 引 集 节

15、点中 的 键 值 等 于 要 找 的 键 值 ， 查 找 仍 要 按 上 述规 则 进 行 下 去 。问 题 ： 若 在 某 个 索 引 集 结 点 中 找 到 了 待 查 找记 录 相 应 的 索 引 键 值 ， 是 否 还 要 继 续 遍 历 B+树 ， 为 什 么 ？ 0P 0K iP1iK iK nP1nK 0sK 0tid sjK jtid )1( nsK 1ntid顺 序 集 节 点 中 的 键 值 要 满 足 如 下 关 系 ：如 果 Pi=P0， 则 Ks0Ks1Ks1Ks0Kn-1;否 则 ： Ki-1Ks0Ks1Ks(n-1)Ki . n B+树 实 现 的 主 索 引 稍

16、 加 修 改 后 也 可 用 于 次 索 引 （ 把 顺序 集 结 点 的 tid换 成 指 针 ， 因 为 一 个 键 值 可 能 对 应 多 个tid） 。n B+树 实 现 的 各 种 索 引 都 是 稠 密 索 引 （ 非 稠 密 索 引 的 概念 源 于 静 态 索 引 ） ， 提 供 了 顺 序 搜 索 的 功 能 ， 这 是 它的 优 点 。 设 索 引 属 性 不 同 键 值 的 数 目 为 N， 若 索 引 键 不是 候 选 键 ， 则 记 录 数 通 常 大 于 N。 B+树 的 级 数 决 定 于 N， 而 不 是 记 录 数 ！ 假 设 B+树 索 引 部 分 共 有 L级 ， 其 秩 为 k， 则 各 级的 最 小 结 点 数 依 次 为 ： 1， 2， 2(k+1)， ， 2(k+1)L-2 L决 定 了 找 到 所 需 顺 序 集 结 点 所 需 的 I/O次 数 （ 访问 数 据 还 要 额 外 的 I/O） ， 例 如 k=99， N=2,000,000，有 L5， 即 至 多 经 过 4次 I/O就 可 以 找 到 相 应 的 顺 序 集结 点 。顺 序 集 至 少 有 2(k+1)L-2个 结 点 。得 出 ：N2(k+1)L-2 kL2+log(k+1)(N/2k)1+ log(k+1)(N/2)