​ 数据库系统5——物理存储结构。

物理存储结构

数据库存储设备

高速缓冲存储器（Cache）：最快价格昂贵的存储介质，由计算机的硬件管理

主存储器：存放可处理数据，快、贵、数据易丢失

快闪存储器：断电故障可保存，相对价低，读速几乎与贮存想要，写稍慢，擦除更慢——固态硬盘

磁盘存储器：长期存储，进行操作时需先读入主存、慢

• 多个磁盘组装成磁盘组，每个磁盘表面由多个磁道组成（数据存储在磁道上），每个磁道分为多个扇区（磁盘块），在磁盘组上所有磁盘面具有相同直径的磁道的集合称为一个柱面。
• 磁盘存储器由磁盘和驱动器构成，磁头和磁臂。分类：固定头磁盘存储器和活动头磁盘存储器
• 寻址方式：柱面号+面号+扇区号
• 代价：寻找使劲按+旋转延迟+传输时间
• 磁盘缓冲区理技术：最近最少使用、立即丢弃、最近最多使用
• 磁盘扫描策略：先来先服务、近者优先、全程移动、移动扫描、分组扫描、间歇式全程扫描
• 磁盘容错技术——基于磁盘冗余技术的策略（独立磁盘冗余阵列）
  • RAID1：一对一
  • RAID4：一个冗余盘完成n个的奇偶校验。所有磁盘同一位置1的个数是偶数则为0，否则1。 问题：冗余盘读写次数太多
  • RAID5：每个磁盘作为某些磁盘的冗余磁盘

光学存储器：比磁盘慢很多

磁带存储器：顺序存储访问、十分慢、十分便宜（磁带驱动器贵）

磁盘文件

数据项——属性值

文件记录——元组

文件块——记录集合、一个磁盘块

文件——一个关系

• 种类：无需文件、有序文件、索引文件、Hash文件

• 文件的存储方法：

  • 连续存储方法：按文件块顺序把文件存储到连续的磁盘块上

    • 存取整个文件的效率高，但扩充困难

  • 链接存储方法

    • 增加指向像一个文件块所在的磁盘块的地址指针
    • 便于扩充，但整个读取慢

  • 索引存储方法

    • 在磁盘上存储一个或多个索引块，每个索引块包含指向文件块的指针
    • 查询处理高效

Hash文件

简单HASH

• 桶溢出（文件记录在Hash属性上分布不均匀）
• 解决：多重Hash（设置溢出处理Hash函数）、链接法（每个桶设置一个磁盘块链表，用于超出部分存储）
• 缺点：只能有效地支持在Hash码上具有相等比较的数据操作；文件记录少时浪费大量存储空间；磁盘块链过长时影响记录存取效率。

动态Hash

• Hash桶与磁盘块一一对应
• Hash桶数量不固定，不断分裂
• 二叉树表示：内节点左0右1，叶节点存储指针
  • 分裂&合并
• 优点：查找记录时只需查找一个存储块
• 缺点：同增长速度快，可能内存放不下，影响其他数据，波动较大

索引文件

索引时一种数据结构，通常是有序文件

索引也是文件——索引文件

• 索引文件的记录称为索引记录（项）
• 索引记录包括两个域：搜索码&指针

• 索引文件一般远小于数据文件

• 多级索引

• 按结构分类：

  • 稀疏索引：所有记录按关键字值分组（管理方便但更新代价高）
    • 主索引常常是稀疏索引
  • 稠密索引：每个记录一个索引项（有序操作方便但复杂）

• 按索引域特点分：

  • 主索引（常常是聚集索引）
  • 辅助索引（一定是稠密索引）

B+树和B树文件索引

略

本章重点：掌握文件、文件记录；掌握索引文件（主索引、聚集索引、辅助索引、多级索引）、数据字典、B+树的索引结构。