数据库系统教程DBS：第六章 数据库的存储结构

第六章数据库的存储结构

6.1文件组织

6.3文件结构

6.3索引技术第六章数据库的存储结构6.1文件组织在外存，数据库以文件形式组织，文件由记录组成。记录是数据库的基本数据单位记录由若干字段组成文件组织有两种方式：

定长记录：每个记录占固定长度的字节数变长记录：记录的长度可变记录在物理块上的分配：不跨块：每个记录完整地存在一个物理块中

跨块：一个记录可以分开存储在不同物理块中第六章数据库的存储结构6.2文件组织◆删除记录的三种处理方式

（1）把被删除的记录依次移上来。（2）把文件中最后的记录填补到删除记录的位置。（3）把被删除的结点用指针链接起来

6.1.1定长记录的处理

第六章数据库的存储结构6.3文件结构变长记录的字节串表示形式（1）每条记录尾部添加“记录尾标识符”（2）记录开始添加记录长度字段分槽式页结构（以块为单位进行存储）

块首部：记录数目、指向自由空间尾部的指针，每个记录的开始位置和大小

自由空间：从后往前使用空间（pp.图6.6）6.1.2变长记录处理

◆文件结构能适应数据的动态变化，提供快速访问路径◆共享→文件结构能提供多种访问路径、方便并发控制、恢复、安全控制

◆文件结构能适应数据量的增长◆

4种文件结构： 堆文件（HeapFile） 顺序文件(SequentialFile) 散列文件(HashingFile) 聚集文件(ClusteringFile)

6.2、文件结构

第六章数据库的存储结构6.3文件结构三、文件的基本类型记录的存放：记录按其插入的先后次序存放存取路径：顺序搜索－－按记录的自然次序，顺序查找所需记录特点：适用于查询所有或相当多的记录的访问类型适于做小文件的文件结构其它场合下查询效率低，I/O和CPU的开销大记录的插入方便，删除困难

1.堆文件(HeapFile)

第六章数据库的存储结构6.3文件结构记录的存放：根据查找键的值的顺序存储记录的文件存取路径：如果是查找键，顺序查找或者二分查找；如果非查找键则顺序查找。特点：在顺序文件初始建立时，可以保持物理顺序和查找键值的顺序一致，但经过多次插入或删除操作后，就很难维持这种一致状态。2.顺序文件(SequentialFile)第六章数据库的存储结构6.3文件结构记录的存放：将记录的某一属性（一般为PK）即散列键用散列函数直接映射成记录的地址，记录按此地址存放存取路径：按散列键访问特点：只对散列键到记录的访问有效在需要快速查找的特殊场合(数据目录和锁表查询)有效散列键映射的地址空间(桶)固定，文件大了溢出，小了浪费不便处理变长记录好的散列函数难找分成静态散列和动态散列（PP.201散列技术）3.散列文件(hashingfile)第六章数据库的存储结构6.3文件结构3.聚集文件(clusteringfile)定义－－个文件存储多个关系的记录，不同关系中有联系的记录存于一个物理块或相邻区域也适用于经常进行连接操作的多个关系

S1WANG20MS2LIU21FS3CHEN22M例：关系S关系SCS1C180S1C270S3C190S3C285S3C395S1WANG20MS1C180S1C270S3C190S3C285S3C395S2LIU21FS3CHEN22M聚集文件：第六章数据库的存储结构6.3文件结构

6.1文件组织

6.2文件结构

6.3索引技术第六章数据库的存储结构第六章数据库的存储结构6.4索引技术索引：为了加快对记录的查找而建立的外存文件结构。一个索引文件由两个部分：主文件和索引，主文件即原始文件，我们考虑主文件是顺序文件的情况，对应同一主文件可以建立几套不同的索引。根据索引中查找键值的顺序和主文件的顺序对应关系可以分成主索引和辅助索引。主索引：如果索引中查找键值的顺序与主文件的顺序一致，这种索引成为主索引。辅助索引项：如果索引中查找键值的顺序与主文件的顺序不一致，这种索引成为辅助索引。索引记录：索引文件由索引记录组成，每个索引记录主要包括索引键和指针。6.3索引技术◆每个原始文件只有一个主索引◆两种常见实现方法： 对于主文件的每一个查找键建立一个索引记录－－稠密索引（PP.191图6.13） 对于主文件的若干个查找键建立一个索引记录－－稀疏索引（PP.191图6.14）性能分析：稠密索引查找较快，稀疏索引查找较慢；稠密索引消耗空间大，稀疏索引消耗空间少；多级索引：形成树形结构（顶层稀疏索引+底层稠密索引）一、主索引第六章数据库的存储结构6.4索引技术◆索引文件的实现方式二、辅助索引◆为每个查找键值建立一个索引项，内容包括一个查找键值和一个指针，但这个指针不是指向主文件中的记录，而是指向一个桶，桶内存放指向同一个查找键值的主记录的指针（图6.16）。一般是在非主键的属性上建立的索引。第六章数据库的存储结构6.4索引技术三、多级索引结构→平衡树(balancedtree)B+树1.B＋树实现的主索引(1)文件结构非叶结点

…

…

…

…

…

……

…

……叶结点STSH结点(物理块)结点(物理块)根结点叶结点第六章数据库的存储结构6.4索引技术非叶结点K0…Kn-1→索引健值,K0<K1<…<

Kn-1不一定是实际键值P0…Pn

→指针

P0

P1……

PnK0K1

PiKn-1

Ki◆

结点结构：◆

级间关系：每个键值都大于其左侧指针指向的下级结点中存储的键值都小于或等于其右侧指针指向的下级结点中存储的键值非叶结点

叶结点STSH第六章数据库的存储结构6.4索引技术

设要找索引键值Kx所对应的记录◆

搜索方法：从根结点开始，依以下规则自上而下地搜索：若Kx<K0则沿P0所指的结点向下搜索若Kx≥Kn-1则沿Pn

所指的结点向下搜索若Ki-1≤Kx<Ki

则沿Pi所指的结点向下搜索第六章数据库的存储结构6.4索引技术非叶结点

叶结点STSH

P0

P1……

PnK0K1

PiKn-1

Ki前、后向指针用于双向连接叶结点tid(元组标识符)→指向记录的指针＝块号＋记录在块中的指针号K0…Kn-1→索引健值：K0<K1<…<

Kn-1

是文件中实际存在的键值，升序叶结点◆

处于树的同一级上

前向指针

后向指针…

tidn-1K0Kn-1

tid0◆结点结构：◆

搜索方法：从SH开始从ST开始从非叶结点检索到的某一键值开始，向左右搜索

STSH第六章数据库的存储结构6.4索引技术设：为m叉树，通常每个物理块存储一个结点则：

m＝物理块大小/索引项长度◆除叶节点外，若节点有J个健值，则有J+1个指针和

J+1颗子树，m为结点的指针数上限◆每个结点最多有(m－1)个键值(m颗子树)◆根结点至少有1个键值(两颗子树)◆其它非叶结点至少有(m－1)/2个键值◆所有叶节点都处在树的同一级上→树始终保持平衡说明：(m－1)/2指大于它的最小整数(2)B＋树的规定第六章数据库的存储结构6.4索引技术(3)B＋树的主要特点-索引项数与树的高度可以动态地随着数据的变化而消长-搜索所需的I/O次数取决于树的高度-I/O次数与m及索引键的不同值数N有关

㏒p(N),P为>=m/2的最小整数第六章数据库的存储结构6.4索引技术(4)B＋保持平衡的算法

插入记录(设此记录的索引键值为KX)：

◆

按前述搜索方法，从根向下搜索至相应的叶结点

(对于主索引，在搜索中若发现与KX值相等的键值则出错)◆若该叶节点未满(少于m－1个键值)：则将键值KX和该记录的tid

插入该叶结点

若被插入的叶节点已满(有m－1个键值)

：将该叶结点分裂为二，分别有m/2个键值向系统再申请一个物理块其父结点也需增加一个键值必要的话父结点也要分裂，直至根结点(树增加一级)第六章数据库的存储结构6.4索引技术例1：引起索引结点分裂的插入操作：第六章数据库的存储结构6.4索引技术插入索引键值“JIANG”3阶B＋树索引第一步：搜索HELIU第二步：分裂叶结点插入JIANG第三步：父结点插入新

结点最小键值

可能分裂第四步：向上至根结点WEN

ZHANGLOULOUHELIU

ZHANGZHOUWENJIANG<WENJIANG<LOUHELIUJIANG

LIULOU删除记录(设此记录的索引键值为KX)：

◆按前述搜索方法，从根向下搜索至相应的叶结点

◆删除对应的索引项

◆若删除后叶节点的索引项数<(m-1)/2：

-若任一相邻叶结点中索引项数>(m-1)/2

移一个索引项到被删除叶结点，以满足≥(m-1)/2条件

-若相邻叶结点中项数都＝(m-1)/2

与任一相邻叶结点合并为一个有m-2项的叶结点,

与此同时父节点中减少一个键值，有可能导致父结点合并，直至根结点(树少一级)第六章数据库的存储结构6.4索引技术例2：引起索引结点合并的删除操作：第六章数据库的存储结构6.4索引技术删除索引键值“LIU”3阶B＋树索引WEN

ZHANGLIULOULOU

ZHANGZHOUWEN

HE

JIANGLIULOU

例2：引起索引结点合并的删除操作：第六章数据库的存储结构6.4索引技术删除索引键值“LIU”图3阶B＋树索引删除索引键值“WEN”WEN

ZHANGLOU

ZHANGZHOUWEN

HE

JIANGLOU第一步：搜索WEN第二步：删除WEN第三步：父结点删除

指针，合并第四步：向上至根结点LOUZHANG

WEN

2.B＋树实现的次索引次索引：一个索引键值可对应多个记录(多个tid)，且数量可变（非聚集)