北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.数据存储与数据管理
? 前面重点讲数据库的逻辑模式,本章介绍
数据库物理模式设计中的数据存储技术
和保证数据库正常运行的安全性, 完整
性控制和数据库恢复技术 。
2.1数据存储
2.2数据管理
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1数据存储
? 数据存储技术的重要目标就是尽可能减
少读写数据所需的磁盘访问 (I/O操作 )次
数, 尽可能使数据驻留在内存中 。
均衡负载,提高效率 ！
2.1.1数据的磁盘存储
2.1.2索引
2.1.3聚簇索引与非聚簇索引
2.1.4散列 (HASH)簇存储
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1 数据的磁盘存储
2.1.1.1磁盘访问是面向页面 (数据块 )的
2.1.1.2ORACLE的磁盘资源分配
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.1磁盘访问是面向页面 (数据块 )的
? 基本表中的行和索引是存储在磁盘上的 。 磁盘
由若干盘片组成, 盘片有磁道, 扇区, 若干盘
片的磁道组成柱面 。
? 一次磁盘页面访问包括：
寻道时间：磁盘臂移动到指定柱面的时间；
旋转延时：磁盘旋转到指定扇区的时间；
传输时间：读写磁盘页面数据的时间 。
磁盘访问时间主要是移动磁盘臂到指定位置所
需时间 。
? 如果两个要连续读取的数据块在磁盘上紧挨着,
则寻到时间很短,如果两数据在同一柱面上,那
末寻到时间为零 。
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.1磁盘访问是面向页面 (数据块 )的
? 在读写磁盘的一个页面的时间里, 可以执行百
万条的程序指令与内存交换数据 。 相对于内存
而言, 磁盘访问速度是很慢的, 我们要尽量减
少磁盘访问的次数 。
? 磁盘访问基本都是, 面向页面的,, 磁盘页面
也称数据块 。 磁盘页面的页面地址可以是连续
的整数, 也可以由设备号, 柱面号, 磁盘表面
号和开始扇区地址组成 。
? ORACLE一个页面 (块 )为 2KB,DB2 UDB标准页面
为 4KB（ DB2 UDB还支持 8KB,16KB和 32KB） 。
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.1磁盘访问是面向页面 (数据块 )的
? 数据库系统按照给定的磁盘页面 (块 )地址读取
磁盘页面, 把数据放到内存的缓冲区 (缓冲区
是在数据库系统初始化时候建立的 )中 。 每读
入一个页面都在散列后备表中记录该页面在缓
冲区中位置, 每一次读取页面时, 首先在散列
后备表中查询该页面是否已在缓冲区中, 如果
在缓冲区则忽略磁盘访问 。
? 缓冲区采用最少使用算法 (LRU)管理可用空间,
当缓冲区需要自由空间时,最少使用的页面将
被移出,最频繁使用的数据被保存在缓冲区中 。
? 为了提高效率,扩大内存的同时,有必要对访问
进行组织 (表的磁盘空间分配 ),以使所需信息
都在同一个页面上 。
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? 不同商业数据库系统的磁盘空间分配体系结构不
大相同,以下说明 ORACLE中的磁盘资源分配 。
? CREATE TABLESPACE tsname
DATAFILE dfname1[,dfname2…]
[DEFAULT STORAGE storage]
[ONLINE|OFFLINE];
? 表空间是 ORACLE数据库基本的分配介质,所有请
求磁盘空间的表, 索引和其它对象都在表空间中
有对应的磁盘空间 。 表空间对应于一个或多个操
作系统文件, 可跨越磁盘设备 。
? 所有数据库产品都有类似于表空间的结构来隔离
用户和操作系统, 它代表一块可以使用的磁盘空
间 。 DB2称为表空间, INFORMIX称为数据库空间 。
联机 |脱机 (立刻能不能用 )
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? ORACLE数据库应包含多个表空间,SYSTEM表空间
是在 Create Database时自动创建的,SYSTEM表
空间包含数据字典,也可包含用户对象,但 DBA应
创建几个表空间分别存储相应的对象,
? 当 CREATE TABLE时可使用子句 TABLESPACE指定
表空间,
? 创建表和索引时,其表空间分配是以数据段对象
和索引段对象标识的,
? 创建数据段和索引段时,将从表空间中分配一个
初始的磁盘空间,称为初始区域 (缺省 10KB).当
写满该区域后,再分配一块区域,称为下一区域,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? 每一块区域都在一个文件上,一个段可以由来
自多个文件的区域组成,每一块区域大小都是
块大小的整数倍 。
CAP数据库
tsname1 system
dfile1 dfile2 dfile3
customers agents products orders ordindx …
DATA DATA DATA DATA INDEX …
数据库存储结构示意图
库
表空间
文件
表
段
区间
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? 表空间由一个或多个在 DATAFILE子句中指定的
操作系统文件组成,
DATAFILE dfname [SIZE n [K|M]][REUSE]
[AUTOEXTEND OFF|
AUTOEXTEND ON [NEXT n [K|M]
[MAXSIZE UNLINITED|n [K|M]]]]
[,dfname …]
没有 SIZE且数据文件存在,ORACLE使用该文件 ;
有 SIZE,ORACLE创建一新文件 (以前有则覆盖 );
有 SIZE且有 REUSE,ORACLE重用旧文件,
AUTOEXTEND子句决定可否自动扩展文件大小 ;
NEXT定每次申请区域大小,MAXSIZE定最大尺寸,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? DEFAULT STORAGE指定该表空间上的段的缺省磁
盘分配区域方案, 所包含段可以不使用该方案
而自行确定,
DEFAULT STORAGE([INITIAL [K|M]][NEXT n [K|M]]
[MINEXTENTS n][MAXEXTENTS [n|UNLIMITED]]
[PCTINCREASE n])
INITIAL初始区域 (缺省为 10KB);NEXT下一区域大
小 (缺省为 10KB);PCTINCREASE后续区域比前一
区域大的百分比,0为不增长,缺省为 50.
MINEXTENTS,MAXEXTENTS最大最小区域数,
? 区域大小是一个数据块中字节数的整数倍 (最小
为 2048B,最大为 4095MB).
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? 创建了表并分配了区域,记录总是一个接一个地
插在第一个区域的第一个块里,直到第一个区域
用完,系统再分配一个新的区域,
? 每一个行是由包含了列值的连续字节组成,在块
中的布局如下图,
块头包含块地址段类型等,行目录有行在块中位
置,可用空间留在中间,
? 行可用块地址及行目录唯一标识,此为行指针,。
ORACLE中称 ROWID,DB2中称 RID.
块头信息 行目录 可用空间 数据行1 2 … n 行 n 行 n-1 … 行 1
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? ORACLE中 ROWID有两种形式 (限制的 /扩展的 ):
BBBBBBBB.RRRR.FFFF(块号,行号,文件号 )
OOOOOOFFFBBBBBRRR(段号文件号块号行号 )
? ROWID可以查看表中行是怎样存储在磁盘上的 ;
通过 ROWID访问某一行是最快的方法,
? DB2中行是不能超过一个页面的 (4KB页面最大行
长度 4005字节 ),ORACLE中行允许跨越块存放,如
果块中无法放下一行时,该行被切成片段,
? ORACLE中 CREATE TABLE的 PCTFREE子句可以减少
出现行片段的概率,
? 减少片段是进行数据库重组织的原因之一,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? CREATE TABLE tablename (……)
[TABLESPACE tsname][STORAGE(……)]
[PCTFREE n][PCTUSED n]
STORAGE子句,针对该表不用表空间的区域分配
方案,而专门由该 STORAGE存储子句指定,
PCTFREE决定每个块上可以有多少空间用于行的
插入 (缺省 10,n为 0到 99):当块中有 (100-n)%的
空间使用后,新的插入被停止 ;留出的空间以备
Varchar类型用或 Alter table时插新列,
PCTUSED决定当已用空间降到 n%时,新的行可继
续插入 (缺省 40,n为 1到 99).
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
ORACLE磁盘分配总结：
? 表空间包含一系列数据库对象 (表, 索引等 )，
对应若干操作系统文件,多个表空间可以让不同
磁盘设备起不同作用,减少 I/O冲突,另外数据备
份可在表空间一级进行,
? 表对应表空间中数据段,可以自行定义自己的磁
盘存储方案,也可用所在表空间的存储方案,
? 段包含一系列区域,区域是块的整数倍,段的存
储方案主要由初始区域, 下一个区域和区域增
长率最大最小区域数决定,
? 块是基本的 I/O操作单元,尽可能将相临数据存
放在一个块中,避免碎片的产生是好的存储模式
的评判标准,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2 索引
? 数据库索引与驻留内存的数据结构有相似之处,
但数据库索引包含数据量大,它是存放在磁盘上
的,只有访问时才调入内存,
? 索引由一系列存储在磁盘上的索引项组成,索引
项第一列是索引键 (keyval),第二列是行指针
(ROWID).索引项按索引键排序,当数据发生更新
时,索引也更新,索引键和表的主键不是一回事,
? 数据库索引设计的重要目标是减少读数据所需
的磁盘访问次数,
? B树是当今数据库中使用最广泛的索引结构,它
是 DB2唯一的索引结构 ;ORACLE的主要索引结
构,ORACLE还有散列聚簇 (Hash Cluster).
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2 索引
2.1.2.1 B树 (B+树 )结构
2.1.2.2 索引节点布局和可用空间
2.1.2.3 ORACLE和 DB2 UDB的 Create Index
2.1.2.4 ORACLE位图索引
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.1 B树 (B+树 )结构
? 例,假设表中有一百万条记录要建索引,假设索
引项占 8个字节 (ROWID占 4个字节,键值占 4个字
节 ),一个 2KB的块可存放 2048/8=256个索引项,
共需 1000000/256=3907个数据块,
二分法查找, 3907个数据块顺序存放,第一次读入
第 3907/2=1954块数据,检查 keyval,第二次读入
1954块数据中的第 1954/2=977块数据,检查
keyval,……,第 12次的 I/O操作才能将包含所找键
值的数据块调入内存,再根据 ROWID去提取数据,
再加一次 I/O操作,
二分法查找不停地 I/O操作,挺费劲 !
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.1 B树 (B+树 )结构
B树结构,np为指向下层节点块的指针,sepkeyval
为分隔符键值,假定目录项所需空间与叶子相同,
Keyval,ROWID
np,sepkeyval
np,sepkeyval
np,sepkeyval np,sepkeyval
Keyval,ROWID Keyval,ROWID
根节点,1块
2层目录,16块
叶节点,3907块
B树结构存储索引,一百万个索引项建起了三层的
B树 (叶节点的层号称为 B树的深度 ),第一次调入
根块,比较后第二次调入 2层目录的某一块第 3次
I/O操作即可找到键值数据块,当然根据 ROWID去
提取数据,还得再加一次 I/O操作,
B树结构存储索引使查找变得,好多啦 !
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.1 B树 (B+树 )结构
? B树 (B+树结构 )是从根到叶多个扇出的树形结构,
具有下列属性,
1)每一节点和磁盘块大小一致,存放在磁盘上,
2)目录层包含目录项 (有 n-1个分隔符键值和 n个
指向下一层 B树节点的磁盘指针 ).
3)叶节点包含形式为 (keyval,ROWID)的项,
4)根节点以下节点不能是满的 (备插入用 )但至少
是半满的 (删除后合并节点 ).
5)根节点至少有两个项 (只有一行记录时除外 ).
B树结构随数据的增加而增长,随数据减少而降低,这一过程
由系统自动完成,但不同系统采用不同的策略,
许多数据库产品提供对 B树进行重组织的实用程序,整理数据
更新后的 B树索引结构,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.2 索引节点布局和可用空间
? B树节点的块结构为,
块头信息 项目录 可用空间 B树项1 2 … n keyval rid … keyval rid
块头信息 ………keyval RID
唯一键值的 B树叶节点块结构
重复键值时 DB2的叶节点块结构
因为 B树的生长过程中可能会发生分裂,所以其节点
可以在半满到满之间变化,我们可以指定其初始可用
空间的百分比,
块中块头信息也要占用空间,实际使用空间不是满
块大小,
RID RID
(ORACLE有专门的 BITMAP)
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.2 索引节点布局和可用空间
? B树的深度就近似于要访问到叶节点的 I/O操作
次数, B树的深度和行的数目是对数关系,
K=CEIL(log n(M))
K 为 B 树 的 层 数,M为行数,n为 每 层 的 扇 出
数,CEIL(s)函数返回大于等于 s的最小整数,
? 一般经常使用的 B树的上面层都是放在内存缓冲
区中,以减少磁盘访问次数,提高效率,
? 建索引过程是首先取出索引项,然后按键值排序,
最后顺序加到 B树叶子层中,实际使用中应当先
装数据,再建索引,这样才能保证数据是连续分
布的,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.3 ORACLE和 DB2 UDB的 Create Index
? CREATE [UNIQUE|BITMAP] INDEX indexname
ON tablename (col[ASC|DESC][,col…])
[TABLESPACE tsname][STORAGE(…)]
[PCTFREE n] [NOSORT];
以上为 ORACLE创建索引的语句,
PCTFREE决定索引第一次创建时 B树节点块将不
被填充的百分比,用于插入新行时的索引项,其
缺省值为 10,对以后不更新的表索引可以设为 0.
NOSORT表明表中的行已经按索引键值排序并按
此顺序存放在磁盘上 (建索引省时间 ).如果有此
子句但表中行没有排序将报错,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.3 ORACLE和 DB2 UDB的 Create Index
? CREATE [UNIQUE] INDEX indexname
ON tablename(col[ASC|DESC][,col…])
[INCLUDE(col[ASC|DESC][,col…])
[CLUSTER]
[PCTFREE n] [MINPCTUSED n]
[ALLOW REVERSE SCANS];
DB2中索引的表空间与表的表空间一样,
INCLUDE指定索引中存储的其他非索引列,
MINPCTUSED设置一个阈值,删除行达到该阈值后,
块自动合并,
ALLOW REVERSE SCANS创建双向叶子指针 (快 ).
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.4 ORACLE位图索引
? 如果有重复键值,ORACLE中可以使用位图索引
(bit map index).
? 位图索引的思想,在块中不存放重复键的 ROWID,
而存放 ROWID转换成的位图 (表中有 n条记录则使
用 n位的 0和 1序列,第 k条记录在 n位位图的第 k位
置为 1).例如,5个职员,键值 ‘ 男 ’ 的位图 01001
说明第 2个和第 5个职员为男性,
? 位图索引有很好的 I/O性能,压缩后的位图占空
间少 ;位图索引在 WHERE后有多个谓词时很有效,
? 当频繁的更新时,位图须先解压,再修改,使得更
新费时,频繁更新时,不要使用位图索引,
想想 DB2中重复键值的块结构
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.3 聚簇索引与非聚簇索引
? 根据索引键值把记录行存放在磁盘上称为聚簇
(clustering),所引用的行和键值顺序一样的索
引称为聚簇索引 (clustered index).
? B树中,如果叶子节点上直接存放行的信息而不
是行的 ROWID,则称索引为主索引 (primary
index).如果叶子节点上存放行的 ROWID,则称索
引为辅助索引 (secondary index).显然 B树主索
引就是聚簇索引,
? 当所查询行彼此很靠近时使用聚簇索引很有效,
非聚簇索引则不能节省 I/O操作,
? 一张表只能有一个聚簇索引,DBA和程序员商量
决定应该如何使用聚簇索引,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.3 聚簇索引与非聚簇索引
? CREATE [UNIQUE] INDEX indexname ON tab…
[CLUSTER][PCTFREE n][MINPCTUSED n];
DB2 UDB创建索引时用 CLUSTER子句说明该索引
为聚簇索引,(一张表只能有一个聚簇索引 )
? CREATE TABLE tablename (…)
[ORGANIZATION HEAP|ORGANIZATION INDEX]
ORACLE用 ORGANIZATION INDEX创建 B树主索引,
但 B树键值必须为表的主键 (primary key);
ORGANIZATION HEAP为缺省值,表示行可随便放,
不一定是 B树主索引,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.3 聚簇索引与非聚簇索引
? ORACLE中的聚簇是包含了在某些特定列上进行
连接的多张表中的行的结构,进行连接的列称为
聚簇键,两张表中具有相同聚簇键值的行在磁盘
上是存放在一起的,
? CREATE CLUSTER clustername
(colname datatype [,col…])
[PCTFREE n][PCTUSED n][STORAGE(…)]
[SIZE n [K|M]][TABLESPACE tsname]
[INDEX|
[SINGLE TABLE]HASHKEYS n[HASH IS exp]];
SIZE为聚簇键值对应行的空间大小 (缺省为 1块 ).
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.3 聚簇索引与非聚簇索引
? 聚簇创建好后,可以在该聚簇上建表,例,
create cluster deptemp (deptno int) size 2000;
create table emps(empno int primary key,
ename varchar(10),deptno int)
cluster deptemp(deptno);
create table depts (deptno int primary key,
dname varchar(9)) cluster deptemp(deptno);
? 聚簇上还要创建索引,这样即可按聚簇索引键访
问行了,索引聚簇使相同列只存储一次节约空间 ;
索引聚簇使连接运算更加快捷 ;聚簇上的索引适
用于其中各个表减少开销,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.4 散列 (HASH)簇存储
? HASH与聚簇都是把若干有共用列的表聚簇在一
起,但聚簇建立专用索引,用索引确定各聚簇键
对应行的存储位置 ;HASH不建索引,通过 HASH函
数生成 HASH值,由 HASH值确定键值对应行的存储
位置,一步到位,
? CREATE CLUSTER clustername …
(colname datatype [,col…]) SIZE n
[SINGLE TABLE]HASHKEYS n [HASH IS expr];
SINGLE TABLE表示只供一张表优化用,
HASHKEYS说明该散列簇至少包含的键数 (应该
INITIAL的值大于 SIZE*HASHKEYS,从而使初始区
域放下该散列簇,避免碎片 ).
HASH关键字
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.4 散列 (HASH)簇存储
? expr是计算数字值的表达式,称为 HASH函数,
HASH函数负责键值与空间存储位置的转换,
HASH函数的优劣决定散列存储方式的成败,
HASH函数有两种表达方式,
1)缺省方式 (没有 HASH IS子句 ):系统自动转换,
2)expr可以为,函数 (列名,…).函数应保证得到
唯一性较好的 HASH值,
例,create cluster deptemp (deptno int) size 2000
hashkeys 10000 hash is mod(deptno,10003);
? 大型应用中,表的长度稳定,磁盘空间需求可以
把握,查询一般为 ‘ 关键字 =…’时,利用散列簇优
势十分明显,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
作业：
1.ORACLE中执行,
create table customers(cid… )
storage (initial 20480,next 20480,maxextents 8,minextents3,pctincrease 0);
该文件第一次创建时,会分配多少字节的磁盘空间?
该表最大可以容纳多大的空间?
2.职工表 emp中有 200000行,每行长度 100字节,
create table emp (eid int not null… ) pctfree 25;
设块中可使用 2000个字节,估算 emp中行所需的块的个数,
create unique index on emp (eid) pctfree 20;
ROWID占 6个字节,eid占 4个字节,每个键的列附加一个字节,估算 B树索
引中每一块的索引项个数,叶子层块数?假设目录层目录项
(sepkeyval,np)与叶子层中的项相等,估算每一目录层的块数?eid的
值从 1到 200000连续,每秒可进行 80块磁盘操作,估算在没有聚簇和有
聚簇情况执行下列查询所需时间?
select * from emp where eid between 10000 and 20000;
3.解释散列簇,
,数据库设计与开发, 讲义
2.数据存储与数据管理
? 前面重点讲数据库的逻辑模式,本章介绍
数据库物理模式设计中的数据存储技术
和保证数据库正常运行的安全性, 完整
性控制和数据库恢复技术 。
2.1数据存储
2.2数据管理
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1数据存储
? 数据存储技术的重要目标就是尽可能减
少读写数据所需的磁盘访问 (I/O操作 )次
数, 尽可能使数据驻留在内存中 。
均衡负载,提高效率 ！
2.1.1数据的磁盘存储
2.1.2索引
2.1.3聚簇索引与非聚簇索引
2.1.4散列 (HASH)簇存储
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1 数据的磁盘存储
2.1.1.1磁盘访问是面向页面 (数据块 )的
2.1.1.2ORACLE的磁盘资源分配
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.1磁盘访问是面向页面 (数据块 )的
? 基本表中的行和索引是存储在磁盘上的 。 磁盘
由若干盘片组成, 盘片有磁道, 扇区, 若干盘
片的磁道组成柱面 。
? 一次磁盘页面访问包括：
寻道时间：磁盘臂移动到指定柱面的时间；
旋转延时：磁盘旋转到指定扇区的时间；
传输时间：读写磁盘页面数据的时间 。
磁盘访问时间主要是移动磁盘臂到指定位置所
需时间 。
? 如果两个要连续读取的数据块在磁盘上紧挨着,
则寻到时间很短,如果两数据在同一柱面上,那
末寻到时间为零 。
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.1磁盘访问是面向页面 (数据块 )的
? 在读写磁盘的一个页面的时间里, 可以执行百
万条的程序指令与内存交换数据 。 相对于内存
而言, 磁盘访问速度是很慢的, 我们要尽量减
少磁盘访问的次数 。
? 磁盘访问基本都是, 面向页面的,, 磁盘页面
也称数据块 。 磁盘页面的页面地址可以是连续
的整数, 也可以由设备号, 柱面号, 磁盘表面
号和开始扇区地址组成 。
? ORACLE一个页面 (块 )为 2KB,DB2 UDB标准页面
为 4KB（ DB2 UDB还支持 8KB,16KB和 32KB） 。
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.1磁盘访问是面向页面 (数据块 )的
? 数据库系统按照给定的磁盘页面 (块 )地址读取
磁盘页面, 把数据放到内存的缓冲区 (缓冲区
是在数据库系统初始化时候建立的 )中 。 每读
入一个页面都在散列后备表中记录该页面在缓
冲区中位置, 每一次读取页面时, 首先在散列
后备表中查询该页面是否已在缓冲区中, 如果
在缓冲区则忽略磁盘访问 。
? 缓冲区采用最少使用算法 (LRU)管理可用空间,
当缓冲区需要自由空间时,最少使用的页面将
被移出,最频繁使用的数据被保存在缓冲区中 。
? 为了提高效率,扩大内存的同时,有必要对访问
进行组织 (表的磁盘空间分配 ),以使所需信息
都在同一个页面上 。
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? 不同商业数据库系统的磁盘空间分配体系结构不
大相同,以下说明 ORACLE中的磁盘资源分配 。
? CREATE TABLESPACE tsname
DATAFILE dfname1[,dfname2…]
[DEFAULT STORAGE storage]
[ONLINE|OFFLINE];
? 表空间是 ORACLE数据库基本的分配介质,所有请
求磁盘空间的表, 索引和其它对象都在表空间中
有对应的磁盘空间 。 表空间对应于一个或多个操
作系统文件, 可跨越磁盘设备 。
? 所有数据库产品都有类似于表空间的结构来隔离
用户和操作系统, 它代表一块可以使用的磁盘空
间 。 DB2称为表空间, INFORMIX称为数据库空间 。
联机 |脱机 (立刻能不能用 )
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? ORACLE数据库应包含多个表空间,SYSTEM表空间
是在 Create Database时自动创建的,SYSTEM表
空间包含数据字典,也可包含用户对象,但 DBA应
创建几个表空间分别存储相应的对象,
? 当 CREATE TABLE时可使用子句 TABLESPACE指定
表空间,
? 创建表和索引时,其表空间分配是以数据段对象
和索引段对象标识的,
? 创建数据段和索引段时,将从表空间中分配一个
初始的磁盘空间,称为初始区域 (缺省 10KB).当
写满该区域后,再分配一块区域,称为下一区域,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? 每一块区域都在一个文件上,一个段可以由来
自多个文件的区域组成,每一块区域大小都是
块大小的整数倍 。
CAP数据库
tsname1 system
dfile1 dfile2 dfile3
customers agents products orders ordindx …
DATA DATA DATA DATA INDEX …
数据库存储结构示意图
库
表空间
文件
表
段
区间
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? 表空间由一个或多个在 DATAFILE子句中指定的
操作系统文件组成,
DATAFILE dfname [SIZE n [K|M]][REUSE]
[AUTOEXTEND OFF|
AUTOEXTEND ON [NEXT n [K|M]
[MAXSIZE UNLINITED|n [K|M]]]]
[,dfname …]
没有 SIZE且数据文件存在,ORACLE使用该文件 ;
有 SIZE,ORACLE创建一新文件 (以前有则覆盖 );
有 SIZE且有 REUSE,ORACLE重用旧文件,
AUTOEXTEND子句决定可否自动扩展文件大小 ;
NEXT定每次申请区域大小,MAXSIZE定最大尺寸,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? DEFAULT STORAGE指定该表空间上的段的缺省磁
盘分配区域方案, 所包含段可以不使用该方案
而自行确定,
DEFAULT STORAGE([INITIAL [K|M]][NEXT n [K|M]]
[MINEXTENTS n][MAXEXTENTS [n|UNLIMITED]]
[PCTINCREASE n])
INITIAL初始区域 (缺省为 10KB);NEXT下一区域大
小 (缺省为 10KB);PCTINCREASE后续区域比前一
区域大的百分比,0为不增长,缺省为 50.
MINEXTENTS,MAXEXTENTS最大最小区域数,
? 区域大小是一个数据块中字节数的整数倍 (最小
为 2048B,最大为 4095MB).
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? 创建了表并分配了区域,记录总是一个接一个地
插在第一个区域的第一个块里,直到第一个区域
用完,系统再分配一个新的区域,
? 每一个行是由包含了列值的连续字节组成,在块
中的布局如下图,
块头包含块地址段类型等,行目录有行在块中位
置,可用空间留在中间,
? 行可用块地址及行目录唯一标识,此为行指针,。
ORACLE中称 ROWID,DB2中称 RID.
块头信息 行目录 可用空间 数据行1 2 … n 行 n 行 n-1 … 行 1
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? ORACLE中 ROWID有两种形式 (限制的 /扩展的 ):
BBBBBBBB.RRRR.FFFF(块号,行号,文件号 )
OOOOOOFFFBBBBBRRR(段号文件号块号行号 )
? ROWID可以查看表中行是怎样存储在磁盘上的 ;
通过 ROWID访问某一行是最快的方法,
? DB2中行是不能超过一个页面的 (4KB页面最大行
长度 4005字节 ),ORACLE中行允许跨越块存放,如
果块中无法放下一行时,该行被切成片段,
? ORACLE中 CREATE TABLE的 PCTFREE子句可以减少
出现行片段的概率,
? 减少片段是进行数据库重组织的原因之一,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
? CREATE TABLE tablename (……)
[TABLESPACE tsname][STORAGE(……)]
[PCTFREE n][PCTUSED n]
STORAGE子句,针对该表不用表空间的区域分配
方案,而专门由该 STORAGE存储子句指定,
PCTFREE决定每个块上可以有多少空间用于行的
插入 (缺省 10,n为 0到 99):当块中有 (100-n)%的
空间使用后,新的插入被停止 ;留出的空间以备
Varchar类型用或 Alter table时插新列,
PCTUSED决定当已用空间降到 n%时,新的行可继
续插入 (缺省 40,n为 1到 99).
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.1.2 ORACLE的磁盘资源分配
ORACLE磁盘分配总结：
? 表空间包含一系列数据库对象 (表, 索引等 )，
对应若干操作系统文件,多个表空间可以让不同
磁盘设备起不同作用,减少 I/O冲突,另外数据备
份可在表空间一级进行,
? 表对应表空间中数据段,可以自行定义自己的磁
盘存储方案,也可用所在表空间的存储方案,
? 段包含一系列区域,区域是块的整数倍,段的存
储方案主要由初始区域, 下一个区域和区域增
长率最大最小区域数决定,
? 块是基本的 I/O操作单元,尽可能将相临数据存
放在一个块中,避免碎片的产生是好的存储模式
的评判标准,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2 索引
? 数据库索引与驻留内存的数据结构有相似之处,
但数据库索引包含数据量大,它是存放在磁盘上
的,只有访问时才调入内存,
? 索引由一系列存储在磁盘上的索引项组成,索引
项第一列是索引键 (keyval),第二列是行指针
(ROWID).索引项按索引键排序,当数据发生更新
时,索引也更新,索引键和表的主键不是一回事,
? 数据库索引设计的重要目标是减少读数据所需
的磁盘访问次数,
? B树是当今数据库中使用最广泛的索引结构,它
是 DB2唯一的索引结构 ;ORACLE的主要索引结
构,ORACLE还有散列聚簇 (Hash Cluster).
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2 索引
2.1.2.1 B树 (B+树 )结构
2.1.2.2 索引节点布局和可用空间
2.1.2.3 ORACLE和 DB2 UDB的 Create Index
2.1.2.4 ORACLE位图索引
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.1 B树 (B+树 )结构
? 例,假设表中有一百万条记录要建索引,假设索
引项占 8个字节 (ROWID占 4个字节,键值占 4个字
节 ),一个 2KB的块可存放 2048/8=256个索引项,
共需 1000000/256=3907个数据块,
二分法查找, 3907个数据块顺序存放,第一次读入
第 3907/2=1954块数据,检查 keyval,第二次读入
1954块数据中的第 1954/2=977块数据,检查
keyval,……,第 12次的 I/O操作才能将包含所找键
值的数据块调入内存,再根据 ROWID去提取数据,
再加一次 I/O操作,
二分法查找不停地 I/O操作,挺费劲 !
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.1 B树 (B+树 )结构
B树结构,np为指向下层节点块的指针,sepkeyval
为分隔符键值,假定目录项所需空间与叶子相同,
Keyval,ROWID
np,sepkeyval
np,sepkeyval
np,sepkeyval np,sepkeyval
Keyval,ROWID Keyval,ROWID
根节点,1块
2层目录,16块
叶节点,3907块
B树结构存储索引,一百万个索引项建起了三层的
B树 (叶节点的层号称为 B树的深度 ),第一次调入
根块,比较后第二次调入 2层目录的某一块第 3次
I/O操作即可找到键值数据块,当然根据 ROWID去
提取数据,还得再加一次 I/O操作,
B树结构存储索引使查找变得,好多啦 !
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.1 B树 (B+树 )结构
? B树 (B+树结构 )是从根到叶多个扇出的树形结构,
具有下列属性,
1)每一节点和磁盘块大小一致,存放在磁盘上,
2)目录层包含目录项 (有 n-1个分隔符键值和 n个
指向下一层 B树节点的磁盘指针 ).
3)叶节点包含形式为 (keyval,ROWID)的项,
4)根节点以下节点不能是满的 (备插入用 )但至少
是半满的 (删除后合并节点 ).
5)根节点至少有两个项 (只有一行记录时除外 ).
B树结构随数据的增加而增长,随数据减少而降低,这一过程
由系统自动完成,但不同系统采用不同的策略,
许多数据库产品提供对 B树进行重组织的实用程序,整理数据
更新后的 B树索引结构,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.2 索引节点布局和可用空间
? B树节点的块结构为,
块头信息 项目录 可用空间 B树项1 2 … n keyval rid … keyval rid
块头信息 ………keyval RID
唯一键值的 B树叶节点块结构
重复键值时 DB2的叶节点块结构
因为 B树的生长过程中可能会发生分裂,所以其节点
可以在半满到满之间变化,我们可以指定其初始可用
空间的百分比,
块中块头信息也要占用空间,实际使用空间不是满
块大小,
RID RID
(ORACLE有专门的 BITMAP)
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.2 索引节点布局和可用空间
? B树的深度就近似于要访问到叶节点的 I/O操作
次数, B树的深度和行的数目是对数关系,
K=CEIL(log n(M))
K 为 B 树 的 层 数,M为行数,n为 每 层 的 扇 出
数,CEIL(s)函数返回大于等于 s的最小整数,
? 一般经常使用的 B树的上面层都是放在内存缓冲
区中,以减少磁盘访问次数,提高效率,
? 建索引过程是首先取出索引项,然后按键值排序,
最后顺序加到 B树叶子层中,实际使用中应当先
装数据,再建索引,这样才能保证数据是连续分
布的,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.3 ORACLE和 DB2 UDB的 Create Index
? CREATE [UNIQUE|BITMAP] INDEX indexname
ON tablename (col[ASC|DESC][,col…])
[TABLESPACE tsname][STORAGE(…)]
[PCTFREE n] [NOSORT];
以上为 ORACLE创建索引的语句,
PCTFREE决定索引第一次创建时 B树节点块将不
被填充的百分比,用于插入新行时的索引项,其
缺省值为 10,对以后不更新的表索引可以设为 0.
NOSORT表明表中的行已经按索引键值排序并按
此顺序存放在磁盘上 (建索引省时间 ).如果有此
子句但表中行没有排序将报错,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.3 ORACLE和 DB2 UDB的 Create Index
? CREATE [UNIQUE] INDEX indexname
ON tablename(col[ASC|DESC][,col…])
[INCLUDE(col[ASC|DESC][,col…])
[CLUSTER]
[PCTFREE n] [MINPCTUSED n]
[ALLOW REVERSE SCANS];
DB2中索引的表空间与表的表空间一样,
INCLUDE指定索引中存储的其他非索引列,
MINPCTUSED设置一个阈值,删除行达到该阈值后,
块自动合并,
ALLOW REVERSE SCANS创建双向叶子指针 (快 ).
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.2.4 ORACLE位图索引
? 如果有重复键值,ORACLE中可以使用位图索引
(bit map index).
? 位图索引的思想,在块中不存放重复键的 ROWID,
而存放 ROWID转换成的位图 (表中有 n条记录则使
用 n位的 0和 1序列,第 k条记录在 n位位图的第 k位
置为 1).例如,5个职员,键值 ‘ 男 ’ 的位图 01001
说明第 2个和第 5个职员为男性,
? 位图索引有很好的 I/O性能,压缩后的位图占空
间少 ;位图索引在 WHERE后有多个谓词时很有效,
? 当频繁的更新时,位图须先解压,再修改,使得更
新费时,频繁更新时,不要使用位图索引,
想想 DB2中重复键值的块结构
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.3 聚簇索引与非聚簇索引
? 根据索引键值把记录行存放在磁盘上称为聚簇
(clustering),所引用的行和键值顺序一样的索
引称为聚簇索引 (clustered index).
? B树中,如果叶子节点上直接存放行的信息而不
是行的 ROWID,则称索引为主索引 (primary
index).如果叶子节点上存放行的 ROWID,则称索
引为辅助索引 (secondary index).显然 B树主索
引就是聚簇索引,
? 当所查询行彼此很靠近时使用聚簇索引很有效,
非聚簇索引则不能节省 I/O操作,
? 一张表只能有一个聚簇索引,DBA和程序员商量
决定应该如何使用聚簇索引,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.3 聚簇索引与非聚簇索引
? CREATE [UNIQUE] INDEX indexname ON tab…
[CLUSTER][PCTFREE n][MINPCTUSED n];
DB2 UDB创建索引时用 CLUSTER子句说明该索引
为聚簇索引,(一张表只能有一个聚簇索引 )
? CREATE TABLE tablename (…)
[ORGANIZATION HEAP|ORGANIZATION INDEX]
ORACLE用 ORGANIZATION INDEX创建 B树主索引,
但 B树键值必须为表的主键 (primary key);
ORGANIZATION HEAP为缺省值,表示行可随便放,
不一定是 B树主索引,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.3 聚簇索引与非聚簇索引
? ORACLE中的聚簇是包含了在某些特定列上进行
连接的多张表中的行的结构,进行连接的列称为
聚簇键,两张表中具有相同聚簇键值的行在磁盘
上是存放在一起的,
? CREATE CLUSTER clustername
(colname datatype [,col…])
[PCTFREE n][PCTUSED n][STORAGE(…)]
[SIZE n [K|M]][TABLESPACE tsname]
[INDEX|
[SINGLE TABLE]HASHKEYS n[HASH IS exp]];
SIZE为聚簇键值对应行的空间大小 (缺省为 1块 ).
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.3 聚簇索引与非聚簇索引
? 聚簇创建好后,可以在该聚簇上建表,例,
create cluster deptemp (deptno int) size 2000;
create table emps(empno int primary key,
ename varchar(10),deptno int)
cluster deptemp(deptno);
create table depts (deptno int primary key,
dname varchar(9)) cluster deptemp(deptno);
? 聚簇上还要创建索引,这样即可按聚簇索引键访
问行了,索引聚簇使相同列只存储一次节约空间 ;
索引聚簇使连接运算更加快捷 ;聚簇上的索引适
用于其中各个表减少开销,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.4 散列 (HASH)簇存储
? HASH与聚簇都是把若干有共用列的表聚簇在一
起,但聚簇建立专用索引,用索引确定各聚簇键
对应行的存储位置 ;HASH不建索引,通过 HASH函
数生成 HASH值,由 HASH值确定键值对应行的存储
位置,一步到位,
? CREATE CLUSTER clustername …
(colname datatype [,col…]) SIZE n
[SINGLE TABLE]HASHKEYS n [HASH IS expr];
SINGLE TABLE表示只供一张表优化用,
HASHKEYS说明该散列簇至少包含的键数 (应该
INITIAL的值大于 SIZE*HASHKEYS,从而使初始区
域放下该散列簇,避免碎片 ).
HASH关键字
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
2.1.4 散列 (HASH)簇存储
? expr是计算数字值的表达式,称为 HASH函数,
HASH函数负责键值与空间存储位置的转换,
HASH函数的优劣决定散列存储方式的成败,
HASH函数有两种表达方式,
1)缺省方式 (没有 HASH IS子句 ):系统自动转换,
2)expr可以为,函数 (列名,…).函数应保证得到
唯一性较好的 HASH值,
例,create cluster deptemp (deptno int) size 2000
hashkeys 10000 hash is mod(deptno,10003);
? 大型应用中,表的长度稳定,磁盘空间需求可以
把握,查询一般为 ‘ 关键字 =…’时,利用散列簇优
势十分明显,
北京邮电大学软件学院 郭文明 2003.06
,数据库设计与开发, 讲义
作业：
1.ORACLE中执行,
create table customers(cid… )
storage (initial 20480,next 20480,maxextents 8,minextents3,pctincrease 0);
该文件第一次创建时,会分配多少字节的磁盘空间?
该表最大可以容纳多大的空间?
2.职工表 emp中有 200000行,每行长度 100字节,
create table emp (eid int not null… ) pctfree 25;
设块中可使用 2000个字节,估算 emp中行所需的块的个数,
create unique index on emp (eid) pctfree 20;
ROWID占 6个字节,eid占 4个字节,每个键的列附加一个字节,估算 B树索
引中每一块的索引项个数,叶子层块数?假设目录层目录项
(sepkeyval,np)与叶子层中的项相等,估算每一目录层的块数?eid的
值从 1到 200000连续,每秒可进行 80块磁盘操作,估算在没有聚簇和有
聚簇情况执行下列查询所需时间?
select * from emp where eid between 10000 and 20000;
3.解释散列簇,
