存储与文件结构.ppt

第11章: 存储与文件结构 物理存储介质概述 磁盘 RAID 第三级存储器 存储器访问 文件组织 文件中记录组织 数据字典存储 面向对象数据库的存储结构 存储器存取 数据库文件被分割成若干定长的存储器单位(称为块). 块是存储器分配和数据传输的单位. 数据库系统应尽量减少磁盘与内存间的块传输次数. 可以通过将尽可能多的块保持在主存中来减少磁盘存取次数. 缓冲区 – 用于保存读入的磁盘块的主存空间. 缓冲区管理器 – 负责分配缓冲区空间的子系统. 缓冲区管理器 当程序请求某磁盘块时即调用缓冲区管理器. 如果该块已经在缓冲区中, 则程序得到该块在主存中的地址 如果该块不在缓冲区中, 则 缓冲区管理器为该块分配缓冲区空间, 如果有必要需换出其他块来为这个新块腾出空间. 如果被换出的块自从最近一次写回磁盘或从磁盘读入之后做过修改, 则需写回磁盘. 否则直接替换. 一旦在缓冲区中分配了空间, 缓冲区管理器就从磁盘将该块读入缓冲区, 并将该块在主存中的地址传给请求者. 缓冲区替换策略 多数操作系统采用最近未使用(LRU)策略来替换块 LRU背后的想法 – 利用过去的块引用样式来预测将来的引用 查询有良定义的存取样式(如顺序扫描), 数据库系统可利用用户查询中的信息来预测将来的引用 LRU 对某些涉及重复扫描数据的存取样式来说是很差的策略 例如当用嵌套循环算法计算两个关系 r 与s 的连接时 for each tuple tr of r do  for each tuple ts of s do  if the tuples tr and ts match … 由查询优化器提供的带有替换策略指导线索的混合策略更可取 缓冲区替换策略 (续) 受制(Pinned)块 – 不允许写回磁盘的内存块. 立即替换(Toss-immediate)策略 – 一旦块中最后一条元组被处理完就释放被该块所占用的空间 最近使用(MRU) 策略 – 系统必须牵制(pin)当前正被处理的块. 当处理完该块的最后一条元组, 该块被解除牵制(unpinned)并成为最近使用的块. 缓冲区管理器可利用关于某请求会引用特定关系的概率的统计信息 例如, 数据字典被频繁存取. 启示: 将数据字典块保存在缓冲区中 为恢复目的, 缓冲区管理器还支持块的强制输出 (参见第17章) 文件组织 数据库保存为若干文件的集合. 文件是记录的序列. 记录是字段的序列. 一种方法: 记录大小固定 每个文件中只有一种类型的记录 不同文件保存不同关系 这种方法最容易实现. 定长记录 简单方法: 记录i 从字节n ? (i – 1)开始存储, 其中n 是记录大小. 记录存取简单, 但记录可能跨块 变化: 不允许记录跨越块边界 删除记录i:  可选方法: 将记录 i + 1, . . ., n 前移成 i, . . . , n – 1 将记录n前移成 i 不移动记录, 而是将所有自由 记录链成一条自由链表 自由链表 在文件头中存储第一条被删记录的地址. 在第一条被删记录中存储第二条被删记录的地址, 等等 这些存储的地址可视为指针, 因为它们 “指向”记录的位置. 是更有效利用空间的表示法: 重新利用自由记录的正常字段空间来存储指针. (使用中的记录则不存储指针) 变长记录 数据库系统中在多种情况下需要变长记录: 一个文件中存储多种记录类型 允许一个或多个变长字段的记录类型 允许重复字段的记录类型 (用于某些老式数据模型). 字节串表示法 在每条记录末尾附加控制字符end-of-record (?) 难以删除 难以增长 变长记录的字节串表示法 变长记录: Slotted Page 结构 Slotted page 页头包含: 记录登记项数目 块中自由空间末端 每条记录的位置和大小 记录可以在页内移动以便保持记录间的连续存储; 页头中的登记项必须更新. 指针不能直接指向记录 — 而是应该指向该记录在页头中的登记项. 变长记录 (续) 定长表示法: 预留空间法 指针法 预留空间法 – 利用具有已知最大长度的定长记录; 较小记录中的未用空间用null或 end-of-record 符号填充. 指针法 指针法 变长记录用若干通过指针链在一起的定长记录表示. 即使最大记录长度未知也可用 指针法 (续) 指针结构的缺点: 除了链中首记录, 其他所有记录中都有浪费空间. 解决方法是文件中采用两种块: 锚块 – 包含链中的首记录 溢出块 – 包含链中其他记录. 文件中的记录组织 堆 – 记录可置于文件中的任何有空间的地方 顺序 – 记录按顺序存储, 基于每条记录在有哪些信誉好的足球投注网站键上的值 散列 – 对记录的某属性计算散列函数; 计算结果决定该记录应该置于文件的哪个块中 每个关系的记录可存储