请使用支持现代 CSS 与 JavaScript 的浏览器播放课件
DBPA · 9.1

数据组织与基础索引

用文件、块和记录解释数据定位

VER. 2608.2 Built with impress.js
DBPA | CH09 | 9.1

学习目标

一次查询可以沿逻辑表、文件、块和记录逐层定位数据

  1. 01画出一次查询从逻辑表到文件、块和记录的访问路径
  2. 02说明定长、长度标记、偏移量和字段分离记录的取舍
  3. 03比较堆、顺序、多表聚簇、B+ 树和哈希存储
  4. 04解释索引减少 I/O 的机制及其空间、更新代价
  5. 05区分稠密、稀疏、多级和辅助索引的前提与路径
  6. 06根据访问与更新模式选择基础组织或索引
2/15
LEARNING OBJECTIVES
DBPA | CH09 | 9.1 | 9.1

关系表背后是文件、块与记录

逻辑层次与物理层次共同支撑数据访问

关系表向记录、块、文件和索引访问路径的物理展开
Takeaway

表空间、段、分区是常见的管理层次示意；具体名称和落盘方式随 DBMS 变化，索引路径是表组织之外的附加访问结构

Takeaway

块是存储分配和 I/O 处理的基本单位

3/15
STORAGE LAYERS
DBPA | CH09 | 9.1 | 9.1

记录表示有不同的长度与定位机制

记录格式会影响读取、修改、删除和迁移

记录方式优势代价
定长记录位置计算简单，字段访问直接可能需要填充或预留空间
长度标记读取时先知道记录／字段长度需要解释长度信息
偏移量用字段起止位置定位变长内容修改后需要维护偏移量
字段分离定长字段与变长字段分开存储访问路径和管理更复杂
4/15
RECORD FORMAT
DBPA | CH09 | 9.1 | 9.1

块内组织：定位记录并回收空闲空间

块头、偏移量表和空闲空间共同决定记录如何被找到

块头、偏移量和空闲空间如何组织定长与变长记录

插入

插入记录时，先分配空闲空间并更新定位信息

删除

删除记录时，标记空闲或压缩空间，并更新偏移量表

变长更新

变长记录原位置不足时，要迁移记录并同步相关定位信息

5/15
BLOCK ORGANIZATION
DBPA | CH09 | 9.1 | 9.1

关系表的组织方式决定常见访问路径

同一份数据可以为不同事务选择不同物理形态

组织方式适合的访问主要代价
堆无序插入和不固定条件查询可能需要全表扫描
顺序按排序属性查找或范围访问插入、修改可能迁移记录
多表聚簇经常连接的相关记录其他查询可能更分散
B+ 树存储按键查找和范围访问需要维护树结构
哈希存储等值条件快速定位范围访问和溢出处理较弱
Takeaway

不等于。B+ 树／哈希表组织负责数据存放，B+ 树／哈希索引是表外的访问结构

6/15
TABLE ORGANIZATION
DBPA | CH09 | 9.1 | 9.1

多表聚簇像预连接，也可能分散其他查询

物理邻近只对特定访问路径有利

任务聚簇后的物理变化查询或维护结果
按 Sno 查学生选课Student ⋈ SC 的相关记录按 Sno 相邻连接查询可能少读跨块 I/O
按专业和性别筛选学生学生记录按学号聚簇，不保证同类记录相邻可能读取更多数据块
新学期增加 SC 记录为保持相邻关系而迁移或重新安排记录更新和空间维护成本增加
Takeaway

聚簇键示意为 Sno；同一物理邻近关系会让不同工作负载得到不同结果

7/15
CLUSTER TRADEOFF
DBPA | CH09 | 9.1 | 9.1

索引是表之外的快速入口

索引通常用较小的结构定位少量目标记录，但并非所有结果规模都适合索引访问

Takeaway

索引减少扫描但增加空间、建立和更新维护成本

Takeaway

选择性较高、返回记录较少时索引更有利；若条件命中大多数记录，顺序扫描可能更便宜

8/15
INDEX MOTIVATION
DBPA | CH09 | 9.1 | 9.1

稠密主索引：每条记录都有入口

基本表按 Sno 有序；查 20180012 时先查索引，再读数据块

稠密索引通过索引块和数据块定位目标记录，并与直接扫描比较 I/O
路径索引项访问结果
稠密索引每条记录一个值和指针本例约 3 次 I/O
直接扫描没有附加入口本例约 6 次 I/O
代价索引本身占空间增删改时同步维护
Takeaway

本例的 3 次与 6 次 I/O 依赖块容量和记录分布，不是所有 DBMS 或工作负载的固定性能承诺

9/15
DENSE INDEX
DBPA | CH09 | 9.1 | 9.1

稀疏索引要求基本表按索引属性有序

通常每个物理块保留一个入口，定位后还要在目标块内顺序搜索

Takeaway

例如查找 Sno = 20180012，先选不超过目标值的最大入口，再在对应块内顺序搜索；若目标块和后续块的首键都已超过目标值，可判定不存在

Takeaway

只要不影响块首记录，部分块内更新可以不改稀疏入口；稀疏索引因此比稠密索引更小

10/15
SPARSE INDEX
DBPA | CH09 | 9.1 | 9.1

多级索引把大索引继续分层

从高层逐级下降到记录；分层可缩小大索引的查找范围

  1. 01高层：通常用稀疏入口定位下一层索引块
  2. 02一级：可以是稠密或稀疏索引，定位基本表入口项
  3. 03数据块：沿记录指针找到目标记录
Takeaway

多级查找按层向下；第一级的稠密或稀疏选择取决于基本表和索引组织

11/15
MULTILEVEL INDEX
DBPA | CH09 | 9.1 | 9.1

辅助索引服务于非排序属性

重复值通过指针桶连接到多条记录

辅助索引通过指针桶定位重复值记录，并可对两个指针集合求交
特征辅助索引的做法设计意义
非排序属性通常建立稠密入口多个访问路径
重复取值引入指针桶管理多条记录指针
多条件查询多个指针集合求交组合筛选
表更新同步维护指针额外写入代价
Takeaway

指针最终要定位基本表记录；当返回记录很多时，顺序扫描可能比辅助索引更便宜

12/15
SECONDARY INDEX
DBPA | CH09 | 9.1

用组织和索引降低块访问代价

数据组织和索引共同降低块访问代价，同时引入空间和维护成本

组织

记录表示、块内空间和表组织决定数据如何存放

入口

顺序表上的主索引提供稠密、稀疏和多级查找入口

取舍

辅助索引的选择取决于选择性和更新维护代价

Takeaway

逻辑／物理组织、顺序表索引和辅助索引构成基础；B+ 树、哈希和位图索引还需结合具体索引结构分析

13/15
RECAP
DBPA | CH09 | 9.1

本节知识地图

14/15
KNOWLEDGE MAP
DBPA | CH09 | 9.1

本节问题

  1. 01查询如何从逻辑表经过文件和块定位到记录？哪些层次会随 DBMS 变化？
  2. 02定长、长度标记、偏移量和字段分离记录分别承担什么空间与定位代价？
  3. 03用 Student ⋈ SC、Sno、专业／性别查询解释多表聚簇为何可能增加或减少 I/O？
  4. 04在按 Sno 有序的表上，20180012 的稠密、稀疏和多级查找路径分别怎样走？
  5. 05Smajor 重复时辅助索引和指针桶怎样工作？多条件如何求交？何时扫描更便宜，增删改需要维护哪些索引？
15/15
CHECK YOUR UNDERSTANDING