数据库理论 06 存储管理和索引——基于《数据库系统概念》第七版

文件和记录的组织

数据库是以一系列文件的形式存储的。每个文件在逻辑上组织成为记录的一个序列

1. 每个文件分为定长的存储单元，称为块（block）
2. 块是存储分配和数据传输的基本单元，块大小一般为4-8KB

如何在文件（块）中存储一条记录？

定长与变长

定

可能是定长or变长

• 定长

1. 访问
   • 记录i从第$n (i – 1)个字节开始存储, n是每个记录的大小。
   • 访问记录很简单，但是一个记录可能存储于不同块
     • 假设要求：不允许记录跨过块边界，没有记录是部分包含在一个块中变长
2. 删除

• 将记录i + 1, . . ., n 移动到i, . . . , n – 1
• 将记录n移到i
• 不移动记录，在一个空闲列表中将所有空闲记录列出

空闲列表的实现：

• 将第一个删除的记录的地址存储于文件头
• 用这第一个记录来存储第二个被删除记录的地址，以此类推
• 可以直观的把这些存储的地址看成指针

变

变长储存方式
1.

• 多种记录类型存储在一个文件中
• 允许一个或多个字段是变长的记录类型
• 允许可重复字段的记录类型

2. 属性按照顺序存储
3. 以固定大小表示可变长度的属性（偏移量，长度），实际数据存储在所有固定长度的属性后
4. 记录末尾加上记录终止符

分槽页结构

分槽页的块头包含：

• 块中记录条目的个数
• 块中空闲空间的末尾处
• 一个由包含记录位置和大小的记录条目组成的数组

记录可以在页中移动，来保持它们连续存储
记录相互间没有空闲的空间（若删除记录，需移动记录数据）

顺序文件组织

➢ 适用于需要对整个文件进行顺序处理的应用
➢ 文件中的记录按搜索码排列
➢ 删除 – 使用指针链
➢ 插入 – 定位插入的位置

• 如果有空闲空间，那么插入到空闲处
• 如果没有空闲空间，将新记录插入溢出块
• 无论哪种情况，指针链都要更新

➢ 需要不时重组文件

• 使其顺序存放

多表聚簇

能够很好地处理对$department\bowtie instructor$的查询以及涉及一个系和相应教师的查询

只查询一个表效果不好，可以添加指针连连接关系记录

数据字典存储

数据字典：也称系统目录存储元数据

1. 关系信息

• 关系名字
• 属性名字、类型、长度
• 视图名字与定义
• 完整性约束

2. 用户、账户信息（如密码
3. 统计和描述型数据

• 关系中元组数目

4. 物理文件组织信息

• 关系如何存储
• 关系物理位置

5. 索引信息

系统元数据的关系表示

1. 磁盘上关系的表示
2. 为在内存中进行高效访问而设计的特殊数据结构（微型数据库）
   

数据缓冲区

每个文件分成定长的存储单元，称为块。块是存储分配和数据传输的基本单位

数据库系统的一个主要目标就是减少磁盘和存储器之间传输的块数。减少磁盘访问次数的一种方法是在主存储器中保留尽可能多的块

缓冲区：主存储器种用于存储磁盘块的副本的那一部分
缓冲区管理器：负责缓冲区空间分配的子系统

➢ 程序需要磁盘上的块时，可以向缓冲区管理器发出请求

1. 如果这个块已经在缓冲区中，缓冲区管理器将这个块在主存储器中的地址传给请求者
2. 如果这个块不在缓冲区中，缓冲区管理器
   • 在缓冲区中为这个块分配空间
     • 如果需要的话，会把其他块移出主存储器，为这个新块腾出空间
     • 移出的块仅当它自从最近一次写回磁盘后被修改过，才被写回磁盘
   • 把这个块从磁盘读入缓冲区，并将这个块在主存储器中的地址传给请求者

多用最近最少使用策略 (least recently used ，LRU)
当涉及对数据重复扫描的访问模式时，LRU是一个糟糕的策略

如

 当通过嵌套循环来对2个关系r和s进行连接操作
for each tuple tr of r do
	for each tuple ts of s do
		if the tuples tr and ts match …
1
2
3
4

由查询优化器提供的带有提示的混合替换策略是较好的选择

• 被钉住（pinned）的块 – 不允许写回磁盘的块
• 立即丢弃策略 – 一旦块中最后一个元组被处理完毕，就立刻命令缓冲区管理器释放这个块所占用的空间
• 最近最常使用策略（和LRU相反）– 系统要替换最近一直在使用的块。当块中最后一个元组处理完毕后，块将被解除钉住，称为最近最常使用的块被移除

缓冲区管理器可以使用请求访问某个特定关系的统计信息

数据字典被经常访问
-->数据字典的块保留在主存储器的缓存中
1
2

为保证数据可恢复性，缓冲区管理器也支持块的强制写出到磁盘

顺序索引

索引机制用来加速对所需数据的访问

• 例如，图书馆中的作者目录

搜索码 – 用于在文件中查找记录的属性或属性集
一个索引文件包含如下形式的记录 (称为索引项)

1. 搜索码值
2. 记录指针
   索引文件一般小于原文件

两种基本类型索引:

1. 顺序索引: 按搜索码顺序存储索引
2. 散列索引: 使用散列函数将搜索码平均分布到若干散列桶中（一般作为辅助索引

索引技术评价指标：

1. 访问类型

• 具有特定属性值的所有记录
• 属性值在某个范围内的所有记录

2. 访问时间
3. 插入时间
4. 删除时间
5. 空间开销

索引相关概念

1. 顺序索引：按顺序存储搜索码的值，并将每个搜索码与包含该搜索码的记录关联起来
2. 主索引: 顺序文件组织中，索引的搜索码指定了文件中记录的顺序（一个关系只有一个）
   • 也叫聚集索引
   • 主索引的搜索码一般是主码，但不是必须的
3. 辅助索引: 搜索码指定的顺序与文件中记录的物理顺序不同的索引（一个关系可以有多个）
   • 也叫非聚集索引
4. 索引顺序文件: 在搜索码上有聚集索引的文件（若记录按搜索码顺序排列）

稠密索引

文件中的每个搜索码值有一个索引记录

稀疏索引

只为搜索码的某些值建立索引记录

• 在记录按照搜索码顺序排列时适用

寻找有搜索值K的记录

• 找到最大搜索码值小于或等于K的索引项
• 从该索引项指向的记录开始，沿着文件中的指针查找，直到找到所需记录为止

稀疏稠密对比
稀疏：插入、删除开销小，定位记录较慢
一般折中：为每个块建立一个索引项（块起始搜索码）的稀疏索引

多级索引

主索引太大无法放入主存，那么访问的开销就很大

将主索引以顺序文件的形式放于磁盘，并为其建立
一个稀疏索引
具有两级或两级以上的索引称为多级索引

1. 外层索引–主索引的稀疏索引
2. 内层索引–主索引文件

对文件进行插入或删除操作后，所有级别的索引都需要更新

辅助索引

我们希望找到某一特定字段（非主索引的搜索码）符合某些条件的所有记录
关系instructor按照ID顺序存储，我们希望找到某一特 殊领域内的所有教师

索引记录指向包含所有指向具有特定搜索键值的实际记录的指针
辅助索引一定为稠密索引

好处与坏处

1. 索引的更新会给数据库的修改带来额外的开销，每当文件被修改时，这个文件上的每个索引都要更新
2. 使用主索引进行顺序扫描是很高效的，但是使用辅助索引却花费很大。因为：
   • 每次对记录的访问都可能从磁盘获得一个新块
   • 获取新块需要5到10毫秒，而存储器访问只需要100纳秒

多码索引

复合搜索码是指包含不止一个属性的搜索码
✓例如(dept_name, salary)

词典顺序
$(a_1,a_2)<(b_1,b_2)$

1. $a_1<b_1$
2. $a_1=b_1\wedge a_2<b_2$

B+树索引

顺序索引缺点：

1. 文件增长， 性能下降 （溢出块过多）
2. 定期重组文件

B+数索引优势

1. 插入删除只需修改局部即可自动重组
2. 不需要重组整个文件

缺点：额外的插入和删除开销，空间开销

满足如下属性

• 从根到所有叶的路径的长度都是相同的
• 每个非叶节点（除根节点之外）都有$\lceil n/2\rceil 到\lceil n\rceil$ 个子节点
• 一个叶子节点内可包含搜索码的数量在 $\lceil (n-1)/2\rceil 和\lceil n-1\rceil$ 之间

1. 如果根节点是一个非叶节点，则它至少有两个子节点
2. 如果根节点是一个叶子节点，则它可以有0到（n-1）个值(搜索码)
   
   一个节点中的搜索码是按顺序排序的（没有重复值的时候）$k_1<...<k_{n-1}$

叶子节点

• 对于 i = 1, 2, . . ., n–1，指针Pi指向具有搜索键值为Ki的记录
• 如果$L_i,L_j$是叶子节点、且$i<j，L_i$的搜索码值小于或等于$L_j$的搜索码值
• $P_n$按搜索键的顺序指向下一个叶子节点

非叶子节点

非叶节点在叶子节点之上形成了一个多级（稀疏）索引。对于带有m个指针（m称之为扇出，fanout）的非叶节点：

1. P1所在的子树中的所有搜索码都小于K1
2. Pn所在的子树中的所有搜索键的值大于或等于Kn–1
3. $2\le i\le n-1$, $P_i$所在子树搜索码$\ge K_{i-1}且<K_i$

如n = 6

1. 叶子节点搜索码数量在3-5之间
2. 除根节点的非叶节点数量在3-6之间
3. 根至少两个子节点

特性

• B+树形成了一个稀疏索引的层次结构

• 可以用相对较少的层次来表示大量的搜索码

  • 低于根的一个级别子树至少有$2\ast \lceil n/2\rceil$ 个搜索码值
  • 再下一级别则至少有$2\ast \lceil n/2\rceil \ast \lceil n/2\rceil$ 个搜索码值

• 因此，如果索引文件中有K个搜索键值，则树的高度
  （即搜索路径长度）不超过 $\lceil \mathbf{l}\mathbf{o}\mathbf{g}\mathbf{n}/2(\mathbf{K})\rceil$ ，可以利用B+树进行有效地搜索

• 可以有效地处理对主文件的插入和删除。因为B+树索引可以在有限时间内（与树的高度成正比关系）进行有效重构

特定值查找

function find(v)
	1. C=root
	2. while (C is not a leaf node)
		1. Let i be least number s.t. V  Ki
		2. if there is no such number i then 
		3. Set C = last non-null pointer in C
		4. else if (v = C.Ki) Set C = Pi +1 
		5. else set C = C.Pi		//(v < C.Ki	) 
	3. if for some i, Ki = V then return C.Pi
	4. else return null /* no record with search-key value v exists. */
1
2
3
4
5
6
7
8
9
10

范围查询

范围查询可在给定范围内查找具有搜索键值的所有记
录

1. findRange(lb, ub)：先遍历至find(lb)的叶子节点V，再从V开始往后遍历所有小于等于ub的记录
2. 实际的实现通常提供一个迭代器接口（类似于游标）使用next()函数，一次获取一个匹配的记录

查询的性质

典型B+树的节点规模通常与磁盘块的大小相同，通常取值为4KB
因此，n通常取值为100左右（每个索引条目40字节）

1. 对于有100W个搜索码的索引文件，且n=100

• 最多查询$lo{g}_{50}(1,000,000)=4$ 个节点（4个块），即可完成从根到叶子节点的遍历

2. 对比AVL树

• 在一次查找中需要访问大约20个节点
  以上差异是显著的，因为每个节点访问可能需要一个磁盘I/O，成本约为20毫秒

B树

类似于B+树，但B树只允许搜索码出现一次，消除了搜索键的冗余存储

非叶节点中的搜索码在B树中没有其他位置可出现，因此，必须为非叶节点中的每个搜索键包含一个额外的指针字段（需指向文件记录）

优点：

1. 可能比相应的B+树使用更少的节点
2. 有时可以在到达叶节点之前找到搜索码

缺点：

1. 数据库范围查找效率低
2. 在所有搜索码中，只有一小部分被早期找到
3. 非叶节点需存储搜索码的记录指针，所以扇出相应地（fanout）变小了。因此，B树通常比B+树具有更大的深度
4. 插入和删除比B+树更复杂，更难实现

散列索引

桶是能存储一条或多条记录的一个存储单元(一个桶就是一个磁盘块)

散列文件组织中，通过使用散列函数直接从搜索码中获得包含该记录的桶

散列函数h是一个从K到B的函数。K表示所有搜索码值的集合，B表示所有桶地址的集合

散列函数用来为获取、插入和删除操作定位记录（不同搜索码记录可能对应同一个桶，桶内需要顺序搜索

• 一个理想的散列函数是均匀的。
• 理想的散列函数是随机的
• 最坏的可能是散列函数把所有的搜索码值映射到同一桶中；这使得访问时间与文件中的搜索码的数量成正比
• 散列函数依据搜索码字符的二进制码来计算
• 无法支持范围查询

桶溢出

1. 桶不足
2. 偏斜

• 多个记录有相同的搜索码值
• 散列函数造成搜索码的分布不均

可以减少这种情况，但无法消除
溢出桶解决桶溢出问题

溢出链：一个给定桶的所有溢出桶用一个链接列表链接在一起
称为闭散列/闭地址

另一种方法称为开散列, 它的桶集合是固定的，没有溢出链，当一个桶满了后，系统将记录插入到初始桶集合的其他桶中

SQL中的索引定义

create index <索引名字> on <关系名字>
1

直接声明该搜索码是一个候选码。
如果数据库系统支持SQL标准的unique声明，那么这里的
unique特性就是多余的
大多数数据库允许指定索引类型，并声明聚集索引