数据库的物理组织.pdf

本讲 第六章 简要说明本讲 第六章 简要说明 授课目的与要求授课目的与要求 掌握无序文件 顺序文 件 掌握无序文件 顺序文 件 HASH文件的文件组织方法 文件的文件组织方法 授课难点授课难点 支持文件空间动态变化的 支持文件空间动态变化的 HASH技术 技术 作业安排作业安排 p 206 1 2 5 9 系统定义 需求收集与分析 数据库与应用程序设计 定义数据库 编写程序 装入数据 测试 运行 系统定义 需求收集与分析 数据库与应用程序设计 定义数据库 编写程序 装入数据 测试 运行 范围和边界 范围和边界 用户视图 用户视图 为每个主要的用户视图收集以下信息 对使用或产生的数据的描述 数据如何使用和产生的细节 数据库应用程序的额外需求 为每个主要的用户视图收集以下信息 对使用或产生的数据的描述 数据如何使用和产生的细节 数据库应用程序的额外需求 概念数据库设计 概念数据库设计 ER 逻辑数据库设计 模式 逻辑数据库设计 模式 物理数据库设计 约束 物理数据库设计 约束 文件组织 文件组织 安全保密措施 安全保密措施 设计界面和各功能模块等设计界面和各功能模块等 数据库规划数据库规划 任务描述 任务描述 任务目标 任务目标 文件组织和存储结构文件组织和存储结构 为数据库存储模式设计提供多种可供选 择的 为数据库存储模式设计提供多种可供选 择的文件组织文件组织方法是本讲要解决的问题 按一定的逻辑结构 如顺序 树 组织 关联的数据记录 逻辑文件 并用体现逻 辑结构的物理存储形式存到物理设备上 方法是本讲要解决的问题 按一定的逻辑结构 如顺序 树 组织 关联的数据记录 逻辑文件 并用体现逻 辑结构的物理存储形式存到物理设备上 目标 目标 根据用户和系统设计要求 组织根据用户和系统设计要求 组织时空 综合性能 时空 综合性能最佳 易于最佳 易于维护维护的文件 为数据库 提供方便 灵活的 的文件 为数据库 提供方便 灵活的文件访问文件访问 Optical Disk TAPE CPU CACHE MAIN MEMORY MAGNETIC DISK Primary storage Secondary storage Tertiary storage 硬盘 第二级存储 是连机存储数据 程序 的主要存储设备 掉电 后 数据不丢失 硬盘 第二级存储 是连机存储数据 程序 的主要存储设备 掉电 后 数据不丢失 非易 失 非易 失 是一种直接存取 存储设备 硬盘被逻辑 分 是一种直接存取 存储设备 硬盘被逻辑 分块 块 block 块大小为块大小为 4KB 56KB 容量容量为几十为几十GB 几百几百 GB 磁盘 磁盘I O 访问速度访问速度 在毫秒级在毫秒级10 2 磁盘阵 列 磁盘阵 列 是近年来用于提高 数据库性能和可靠性的 一种技术 是近年来用于提高 数据库性能和可靠性的 一种技术 主存储器 常为动态随机 访问存储器 主存储器 常为动态随机 访问存储器 DRAM 它 为 它 为CPU提供保存程序和数 据的工作区 数据库系统 只用它存储从外存调入主 存需要处理的那部分数 据 掉电后 主存中的数 据丢失 易失 容量为 几百 提供保存程序和数 据的工作区 数据库系统 只用它存储从外存调入主 存需要处理的那部分数 据 掉电后 主存中的数 据丢失 易失 容量为 几百MB 几几GB 访问速 度为 访问速 度为10 8 10 7秒 是主存数据库 实际用 的是虚存 的主要存储介 质 秒 是主存数据库 实际用 的是虚存 的主要存储介 质 CPU寄存器 寄存器 CPU缓存 存储器 高速缓存存储 器 它们一般用来存放将 要执行的机器指令和有关 操作数据 缓存 存储器 高速缓存存储 器 它们一般用来存放将 要执行的机器指令和有关 操作数据 容量容量为为 128KB 512KB 访问速度 为纳秒级 访问速度 为纳秒级 10 9 10 8秒 由操作系统使用和管理 数据库管理系统不考虑它 们 秒 由操作系统使用和管理 数据库管理系统不考虑它 们 磁带 第三级存储 是顺序存取设备 常脱 机作为数据归档的存储 设备 磁带 第三级存储 是顺序存取设备 常脱 机作为数据归档的存储 设备 访问速度访问速度约为几 秒 约为几 秒 几分 几分 容量容量为为GB TB 光盘 有只读和可擦写 光盘 光盘 有只读和可擦写 光盘 CPU不能对辅存中的数 据进行操作 必须首先 把数据复制到主存 不能对辅存中的数 据进行操作 必须首先 把数据复制到主存 Flash Memory 闪存是使用电可擦写可编 程只读存储器技术的设 备 优点是速度快 非易 失 容量从数 闪存是使用电可擦写可编 程只读存储器技术的设 备 优点是速度快 非易 失 容量从数M到数到数G 缺点是必须整块擦除或写 入 缺点是必须整块擦除或写 入 6 1数据的物理存储数据的物理存储 6 1 1存储介质存储介质 Storage Size 10 910 610 310 0103 access time sec 1015 1013 1011 109 107 105 103 cache electronic main electronic secondary magnetic optical disks online tape nearline tape zhanghua wuyi 2 记录长度指示器 3 记录位置表 Microsoft Office Access将存储在表中的数据划分 成大小为2 K的数据页 每个页面包含了一个或多个 记录 但记录不能跨越页面 Microsoft Office Access将存储在表中的数据划分 成大小为2 K的数据页 每个页面包含了一个或多个 记录 但记录不能跨越页面 Access采用可变长记录作为标准存储方法 并且可 以通过主关键字来对记录进行排序 因为长度可 变 所以每个记录都只占据了存储它的实际数据所 需的空间 Access采用可变长记录作为标准存储方法 并且可 以通过主关键字来对记录进行排序 因为长度可 变 所以每个记录都只占据了存储它的实际数据所 需的空间 每个页都包含一个头指针 用以创建数据页链表 头指针中包含了两个指针 一个指向它的前驱页 面 另一个指向它的后续页面 每个页都包含一个头指针 用以创建数据页链表 头指针中包含了两个指针 一个指向它的前驱页 面 另一个指向它的后续页面 新的数据将被添加到表的最后一页 这个页面被填 满后 则再增加一个页面 新的数据将被添加到表的最后一页 这个页面被填 满后 则再增加一个页面 Memo和OLE Object字段在页中可以跟记录中的其余 部分分开存储 Memo和OLE Object字段在页中可以跟记录中的其余 部分分开存储 6 2 文件的组织方式 无序文件 顺序文件 散列文件 一 无序文件无序文件 1 结构结构 按数据记录到达文件的 时间顺序依次存储数据 按数据记录到达文件的 时间顺序依次存储数据 2 查找查找 顺序扫描 顺序扫描 插入插入 新纪录从未用空间始 地开始存放 新纪录从未用空间始 地开始存放 删除删除 作删除标记 作删除标记 3 用途用途 日志文件 临时文件 数据装入的初始文件 日志文件 临时文件 数据装入的初始文件 未用 空间 二 顺序文件二 顺序文件 逻辑上按某一关键字 一般为主关键字 顺 序排列的文件 逻辑上按某一关键字 一般为主关键字 顺 序排列的文件 1 物理结构物理结构 1 向量结构 地址连续的空间 地址 顺序实现逻辑顺序 向量结构 地址连续的空间 地址 顺序实现逻辑顺序 2 链结构 指针维持逻辑顺序 链结构 指针维持逻辑顺序 3 块链结构 块中地址顺序表示逻辑 顺序 块间指针链接维持逻辑顺序 块链结构 块中地址顺序表示逻辑 顺序 块间指针链接维持逻辑顺序 2 查找 1 顺序扫描 顺序扫描 向量结构 链结构 块链结构 向量结构 链结构 块链结构 2 分块查找 分块查找 向量结构 块链结构 向量结构 块链结构 3 折半查找 折半查找 向量结构 向量结构 4 探查 探查 向量结构 向量结构 顺序文件 3 维护维护 块中后续记录 前移 块合并 修改指针后续记录上移 删除标记 删除 移动块中后续 记录 块分裂 修改指针移动后续记录 溢出指针 预留空间 插入 块链链向量结构 块中后续记录 前移 块合并 修改指针后续记录上移 删除标记 删除 移动块中后续 记录 块分裂 修改指针移动后续记录 溢出指针 预留空间 插入 块链链向量结构 顺序文件顺序文件 三 HASH文件三 HASH文件 1 基本思想 为 基本思想 为HASH文件准 备的存储空间分为主 数据区 溢出区 主数据区由 文件准 备的存储空间分为主 数据区 溢出区 主数据区由M个桶 组成 编号 个桶 组成 编号 0 1 M 1 利用记录的关键 字 利用记录的关键 字k 计算 该记录应存 储的桶号 计算 该记录应存 储的桶号H k 是一 种关键字变地址的文 件组织方法 是一 种关键字变地址的文 件组织方法 M 1 2 1 0 地址桶号 主数据区 溢出区 HASH文件HASH文件 2 HASH方法的步骤方法的步骤 3 溢出处理溢出处理 开寻址列 分离溢出区 分布溢出区 开寻址列 分离溢出区 分布溢出区 4 溢出分析溢出分析 5 主要主要HASH算法算法 M 1 2 1 0 地址桶号地址桶号 主数据区主数据区溢出区溢出区 6 支持文件空间动态变化的支持文件空间动态变化的HASH技术技术 1 动态 动态HASH 2 可扩展 可扩展HASH 3 线性 线性 HASH HASH文件文件 两个基本点 两个基本点 00110101 a 使用使用b位哈希函数值的高位哈希函数值的高i位 位 b h K use i 随时间增长 随时间增长 b 用目录用目录 h K i to bucket 有两种实现方法有两种实现方法 6 支持文件空间动态变化的支持文件空间动态变化的HASH技术技术 桶号以二进制整数表示 开始时所有 记录放在一个桶中 当一个桶溢出时分裂 为两个桶 桶号最高位为0的放在一个桶 中 桶号最高位为1的放在另一个桶中 当 这些桶中又有某个溢出时 该桶又分裂为 两个桶按次高位为0的放在一个桶中 次高 位为1的放在另一个桶中 桶号以二进制整数表示 开始时所有 记录放在一个桶中 当一个桶溢出时分裂 为两个桶 桶号最高位为0的放在一个桶 中 桶号最高位为1的放在另一个桶中 当 这些桶中又有某个溢出时 该桶又分裂为 两个桶按次高位为0的放在一个桶中 次高 位为1的放在另一个桶中 1 动态 动态HASH 目录数据桶 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 1 1 1 6 支持文件空间动态变化的支持文件空间动态变化的HASH技术技术 2 可扩展 可扩展HASH 其思想与动态HASH差不多 它维持 一个数组目录 相当于动态HASH二叉树 目录的叶结点集合 其思想与动态HASH差不多 它维持 一个数组目录 相当于动态HASH二叉树 目录的叶结点集合 目录局部深度数据桶目录局部深度数据桶 d 3 d 3 d 2 d 3 d 3 d 2 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 全局深度全局深度d 3 6 支持文件空间动态变化的支持文件空间动态变化的HASH技术技术 Example h k is 4 bits 2 keys bucket i 1 1 1 0001 1001 1100 Insert 1010 1 1100 1010 New directory 2 00 01 10 11 i 2 2 1 0001 2 1001 1010 2 1100 Insert 0111 0000 00 01 10 11 2i Example continued 0111 0000 0111 0001 2 2 00 01 10 11 2i 2 1001 1010 2 1100 2 0111 2 0000 0001 Insert 1001 Example continued 1001 1001 1010 000 001 010 011 100 101 110 111 3i 3 3 目录局部深度数据桶目录局部深度数据桶 d 3 d 3 d 2 d 3 d 3 d 2 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 全局深度全局深度d 3 当局部深度d当局部深度d 等于 全局深度d的桶分 裂时 目录的全局 深度d增加1 目录 的项数增加一倍 等于 全局深度d的桶分 裂时 目录的全局 深度d增加1 目录 的项数增加一倍 6 支持文件空间动态变化的支持文件空间动态变化的HASH技术技术 两个基本点两个基本点 a 使用使用b位哈希函数值的低位哈希函数值的低i位位 01110101 grows b i b 文件线性增长文件线性增长 3 线性 HASH Exampleb 4 bits i 2 2 keys bucket 0001 1011 0101 1111 0000 1010 n 01 max used block Future growth buckets If h k i nthen look at bucket h k i else look at bucket h k i 2i 1 Rule 1101 can have overflow chains insert 1101 Exampleb 4 bits i 2 2 keys bucket 0001 1011 0101