第五章 数据库的存储结构
5.1 数据库存储介质的特点
● 内存
容量低（一般只有几百M，最多一两个G），价格高，速度快，数据易丢失（掉电、当机等）。
一般做DBMS（或CPU）和DB之间的数据缓冲区。
实时/内存数据库系统中使用内存存放实时数据。
变压器油泵● 硬盘
lncrna引物设计
容量高（一般有几十G，多到一两百G），价格中，速度较快，数据不易丢失（除非物理性损坏）。
一般做用来存放DB。
实时/内存数据库系统中使用硬盘存放历史数据库。
● 移动硬盘（USB接口）
容量高（一般有几十G），价格中，速度较快，数据不易丢失（除非物理性损坏）。
一般做用来做备份。
● 光盘
android退出应用容量低（一般650M/片，但光盘可在线更换，海量），价格低，速度中，数据不易丢失（除非物理性损坏）。
一般做用来做备份。
● 磁盘（软盘）
容量低（一般有几M，优盘多到一两百M），价格中，速度较慢，数据不易丢失（除非物理性损坏）。
一般数据库不使用磁盘。
● 磁带
容量低（但可在线更换，海量），价格低，速度最慢，且要按顺序存取，数据不易丢失（除非物理性损坏）。
一般做用来做备份。
按速度从高到低：
内存、硬盘、USB盘（移动硬盘和优盘）、光盘、软盘、磁带。
按在线容量从大到小：
硬盘、移动硬盘、内存、光盘、磁带、优盘、软盘。
物理块：512byte/1K/2K/4K/8K
原因：
(1) 减少I/O的次数；
(2) 减少间隙的数目，提高硬盘空间的利用率。
ORACLE逻辑块与物理块（a中db_block_size定义逻辑块大小）
缓冲块和缓冲区（即SGA中的Data Buffer Cache）
延迟写(delayed write)技术/预取(Prefetching)技术（ORACLE中由DBWR进程完成数据的读写）
5.2.1 记录的物理表示
1． Positional Technique
2． Relational Technique
3． Counting Technique
5.2.2 记录在物理块上的分配
不跨块组织(unspanned organization)
跨块组织(spanned organization)
5.2.3 物理块在磁盘上的分配
1． 连续分配法(continuous allocation)
2． 链接分配法(linked allocation)
3． 簇集分配法（Clustered Allocation）
4． 索引分配法（Indexed Allocation）
5.2.4 数据压缩技术
1． 消零或空格符法（null suppression）
如：#5表示5个空格，@6表示6个零等。
2． 串型代替法（pattern substitution）
3． 索引法（indexing）
5.3 文件结构和存取路径
5.3.1 访问文件的方式
1． 查询文件的全部或相当多的记录
2． 查询某一特定记录
3． 查询某些记录
4． 范围查询
5． 记录的更新
5.3.2 数据库对文件的要求
5.3.3 文件的基本类型
1． 堆文件(heap file)
方便（快）：插入
不方便（慢）：查、删除
2． 直接文件（direct file）
方便（快）：按散列键访问
不方便（慢）：其它访问方式
人脸识别考勤
3． 索引文件（indexed file）
方便（快）：按索引键访问
不方便（慢）：其它访问方式，特别是更新时要进行索引维护。
● 索引项=<索引键，地址>
● primary index and secondary index
● nondense index and dense index
● 预查功能
设要查询年龄为20岁或2l岁的四年级学生，如果学生文件在年龄和年级属性上建有索引，则可查出年龄为20岁的学生记录的集合S20，年龄为2l岁的学生记录的集合S21运动地垫，四年级学生记录的集合Ss，于是，所需的学生记录的集合S应为：
S=(S20∪S21) ∩Ss
● clustering index
● B tree index
动态平衡多叉（分）树
有B+树、B*树等，数据库管理系统中常用B+树实现索引。
B+树结构：
B+树动态平衡特性：
(1) 每个结点最多有2k个键值；
(2) 根结点至少有—个键值，其他结点至少有k个键值；
(3) 除叶结点(即顺序集结点)无子女外，对于其他结点，若有J个键值，则有J+1个子女；
(4) 所有叶结点都处于树的同一级上，即树始终保持平衡。
k值一般根据块的大小确定，使得B+树的结点最大不超过一个块，即一个结点占一个块（block）。
优点：所有记录都具有相同的访问I/O次数（即树的高度+记录本身访问的I/O次数），（若k=20，树的高度为11，则至少可表示2010=1024X1010个记录）。
缺点：索引维护需要代价，当记录更新引起索引变化时，最差的情况可能从底层一直影响到根结点，即整个树的变动。
第六章
查询处理和优化
6.1 Introduction
1． 代数优化
2． 物理优化
3． 规则优化
4． 代价估算优化
6.2 代数优化
例1 设有S（供应商），P(零件)，SP(供应关系)三个关系，关系模式如下： S（SNUM，SNAME，CITY）
P（PNUM，PNAME，WEIGHT，SIZE）
SP（SNUM，PNUM，DEPT，QUAN）
设有查询Q：
SELECT SNAME
FROM S，P，SP
WHERE S.SNUM=SP.SNUM
AND SP.PNUM=P.PNUM
AND S.CITY=‘NANJING’
AND P.PNAME=‘BOLT’
AND SP.QUAN>10000；
代数优化的大致过程：
1． 以SELECT子句对应投影操作，以FROM子句对应笛卡儿乘积，以WHERE子句对应选 择操作，生成原始查询树。
2． 应用变换原则(2)、(6)、(7)、(9)，尽可能将选择条件移向树叶方向。 3． 真空装应用连接、笛卡儿乘积的结合律，按照小关系先做的原则，重新安排连接(笛卡儿乘积)的次序。 4． 如果笛卡儿乘积后还须按连接条件进行选择操作，可将两者组合成连接操作。
5． 对每个叶结点添加必要的投影操作，以消除对查询无用的属性。
6.3 依赖于存取路径的规则优化
6.3.1 选择操作的实现和优化
1． 相关因素
● 选择条件
● 可用的存取路径
● 选取的元组数在整个关系中所占的比例有关
2． 实现方法
(1) 对于小关系，不必考虑其他存取路径，直接用顺序扫描。例如对于六个物理块大小的关系，如果顺序搜索，则平均的I/O次数为3，不值得采用其他存取路径。
(2) 如果无索引或散列等存取路径可用，或估计中选的元组数在关系中占有较大的比例(例如大于20％)且有关属性上无族集索引，则用顺序扫描。
(3) 对于主键的等值条件，最多只有一个元组可以满足此条件，应优先采用主键上的索引或散列。
(4) 对于非主键的等值条件，要估计中选的元组数在关系中所占的比例。如果比例较小(例如小于20％)，可以用无序索引，否则只能用簇集索引或顺序扫描。
(5) 对于范围条件，一般先通过索引到范围的边界，再通过索引的顺序集沿相应方向按索，例如对于条件Sage＞20，可先到Sage＝20的顺序集结点，再沿顺序集向右搜索。
若中选的元组数在关系中所占比例较大，且无有关属性的簇集索引，则宜采用顺序扫描。例如对于条件Sage＞15，因为大学生绝大部分是大于15岁的。
(6) 对于用AND连接的合取选择条件。若有相应的多属性索引，则优先采用多属性索引。否则，可检查诸合取条件中有无多个可用二次索引的，若有，则用预查法处理。即通过二次索引出满足各合取条件的tid集合，再求这些tid集合的交集。然后取出交集中tid所对应的元组．并在取这些元组的同时，用合取条件中的其余条件检查。凡能满足所有其余条件的元组，即为所选择的元组。如果上述途径都不可行，但合取条件中有个别条件具有规则(3)、(4)、(5)中所述的存取路径，则可用此存取路径选择满足此条件的元组，再将这些元组用合取条件中的其他条件筛选。若在诸合取的条件中，没有一个具有合适的存取路径．那只有用顺序扫描。
(7) 对于用OR连接的析取选择条件，尚无好的优化方法，只能按其中各个条件分别选出一个元组集，再求这些元组集的并。众所周知，并是开销大的操作，而且在OR连接的诸条件中，只要有一个条件无合适的存取路径，就不得不采用顺序扫描来处理这种查询。因此，在查询语句中，应尽量避免采用析取选择条件。
(8) 有些选择操作只要访问索引就可得到结果，例如查询索引属性的最大值、最小值、平均值等。在此情况下，应优先利用索引、避免访问数据。
6.3.2 连接操作的实现和优化
1. 嵌套循环(nested loop)法
R R.A=S.B S
外关系(outer relation)
内关系(inner relation)
2. 利用索引或散列寻匹配元组法
3. 排序归并(sort-merge)法
下面是选用连接方法的启发式规则。
(1) 如果两个关系都已按连接属性排序，则优先用排序归并法。如果两个关系中已有一个关系按连接属性排序，另一个关系很小，也可考虑对此未排序的关系按连接属性排序，再用排序归并法连接。
(2) 如果两个关系中有一个关系在连接属性上有索引(特别是簇集索引)或散列，则可令另一关系为外关系，顺序扫描，并利用内关系上的索引或散列寻其匹配元组，以代替多遍扫描。
(3) 如果应用上述两规则的条件都不具备，且两个关系都比较小，可以应用嵌套循环法。
(4) 如果(1)、(2)、(3)规则都不适用，可用散列连接法。
6.3.3 投影操作的实现
6.3.4 集合操作的实现
6.3.5 组合操作
