数据库的存储结构.doc

S00810 数据库原理与设计方法第五章 数据库的存储结构5.1 数据库存储介质的特点l 内存容量低（一般只有几百M，最多一两个G），价格高，速度快，数据易丢失（掉电、当机等）。一般做DBMS（或CPU）和DB之间的数据缓冲区。实时/内存数据库系统中使用内存存放实时数据。l 硬盘容量高（一般有几十G，多到一两百G），价格中，速度较快，数据不易丢失（除非物理性损坏）。一般做用来存放DB。实时/内存数据库系统中使用硬盘存放历史数据库。l 移动硬盘（USB接口）容量高（一般有几十G），价格中，速度较快，数据不易丢失（除非物理性损坏）。一般做用来做备份。l 光盘容量低（一般650M/片，但光盘可在线更换，海量），价格低，速度中，数据不易丢失（除非物理性损坏）。一般做用来做备份。l 磁盘（软盘）容量低（一般有几M，优盘多到一两百M），价格中，速度较慢，数据不易丢失（除非物理性损坏）。一般数据库不使用磁盘。l 磁带容量低（但可在线更换，海量），价格低，速度最慢，且要按顺序存取，数据不易丢失（除非物理性损坏）。一般做用来做备份。按速度从高到低：内存、硬盘、USB盘（移动硬盘和优盘）、光盘、软盘、磁带。按在线容量从大到小：硬盘、移动硬盘、内存、光盘、磁带、优盘、软盘。物理块：512byte/1K/2K/4K/8K原因：(1) 减少I/O的次数；(2) 减少间隙的数目，提高硬盘空间的利用率。ORACLE逻辑块与物理块（init.ora中db_block_size定义逻辑块大小）缓冲块和缓冲区（即SGA中的Data Buffer Cache）延迟写(delayed write)技术/预取(Prefetching)技术（ORACLE中由DBWR进程完成数据的读写）5.2 记录的存储结构5.2.1 记录的物理表示1 Positional Technique2 Relational Technique3 Counting Technique5.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）方便（快）：按索引键访问不方便（慢）：其它访问方式，特别是更新时要进行索引维护。l 索引项=l primary index and secondary indexl nondense index and dense index l 预查找功能设要查询年龄为20岁或2l岁的四年级学生，如果学生文件在年龄和年级属性上建有索引，则可查出年龄为20岁的学生记录的集合S20，年龄为2l岁的学生记录的集合S21，四年级学生记录的集合Ss，于是，所需的学生记录的集合S应为：S=(S20S21) Ssl clustering indexl 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 Introduction1 代数优化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 SNAMEFROM S，P，SPWHERE S.SNUM=SP.SNUMAND SP.PNUM=P.PNUMAND S.CITY=NANJINGAND P.PNAME=BOLTAND SP.QUAN10000；代数优化的大致过程：1 以SELECT子句对应投影操作，以FROM子句对应笛卡儿乘积，以WHERE子句对应选择操作，生成原始查询树。2 应用变换原则(2)、(6)、(7)、(9)，尽可能将选择条件移向树叶方向。3 应用连接、笛卡儿乘积的结合律，按照小关系先做的原则，重新安排连接(笛卡儿乘积)的次序。4 如果笛卡儿乘积后还须按连接条件进行选择操作，可将两者组合成连接操作。5 对每个叶结点添加必要的投影操作，以消除对查询无用的属性。6.3 依赖于存取路径的规则优化6.3.1 选择操作的实现和优化1 相关因素l 选择条件l 可用的存取路径l 选取的元组数在整个关系中所占的比例有关2 实现方法(1) 对于小关系，不必考虑其他存取路径，直接用顺序扫描。例如对于六个物理块大小的关系，如果顺序搜索，则平均的I/O次数为3，不值得采用其他存取路径。(2) 如果无索引或散列等存取路径可用，或估计中选的元组数在关系中占有较大的比例(例如大于20)且有关属性上无族集索引，则用顺序扫描。(3) 对于主键的等值条件，最多只有一个元组可以满足此条件，应优先采用主键上的索引或散列。(4) 对于非主键的等值条件，要估计中选的元组数在关系中所占的比例。如果比例较小(例如小于20)，可以用无序索引，否则只能用簇集索引或顺序扫描。(5) 对于范围条件，一般先通过索引找到范围的边界，再通过索引的顺序集沿相应方向按索，例如对于条件Sage20，可先找到Sage20的顺序集结点，再沿顺序集向右搜索。若中选的元组数在关系中所占比例较大，且无有关属性的簇集索引，则宜采用顺序扫描。例如对于条件Sage15，因为大学生绝大部分是大于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) 如果两个关系中有一个关系