文件和记录的组织

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

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

记录在文件中是定长或可变长的

定长记录

删除记录，维护记录列表方法：

逐位移动
末尾记录移动到空缺位置
记录空闲列表
- 用链表存储空闲地址

变长记录

出现方式

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

特点

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

分槽的页结构

分槽页块头结构

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

存储特点

记录可以在页中移动，来保持连续存储
记录相互间没有空闲空间，如果删除记录需要移动记录数据

![[images/Pasted image 20260110105108.png]]

文件中记录的组织

堆文件组织：一个记录可以放在文件中的任何地方，只要那个地方有空间存放这条记录
顺序文件组织：记录根据搜索码的值顺序存储
散列文件组织：在每条记录的某些属性上计算散列函数，根据计算结果决定存储的块

通常，每个关系的记录用一个单独文件存储

多表聚簇文件组织：几个不同关系的记录存储在同一文件，可以在同一块中存储相关的记录，降低 IO 开销

顺序文件组织

适用于需要对整个文件进行顺序处理的应用
文件中的记录按搜索码排列
删除：使用指针链表
插入：定位插入位置
- 如果有空闲空间，则插入到空闲处
- 如果没有空闲空间，将新纪录插入溢出块
- 都需要更新指针链
需要不时重组文件，使其顺序存放

多表聚簇文件组织

用多表聚簇文件组织在一个文件中存储几个关系

能够很好地处理连接查询
可以添加指针链来连接某个关系的记录

数据字典存储

数据字典：也称系统目录存储元数据（即关于数据的数据）

关系信息
- 关系名字
- 属性名字、类型、长度
- 视图名字和定义
- 完整性约束
用户、账户信息，密码
统计和描述性数据
- 关系中的元组数目
物理文件组织信息
- 关系如何存储
- 关系的物理位置
索引信息

系统元数据的关系表示

为在内存中进行高效访问而设计的特殊数据结构（微型数据库）

![[images/Pasted image 20260110134222.png]]

数据缓冲区

访问存储

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

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

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

缓冲区管理器

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

如果块已在缓冲区中，缓冲区管理器将该块在主存储器中的地址传给请求者
若不在，缓冲区管理器：
- 在缓冲区中为该块分配空间
  - 可能会将其他块移出主存储器，为新块提供空间
  - 移出的块仅当它自从最近一次写回磁盘后被修改过，才被写回磁盘
- 把这个块从磁盘读入缓冲区，并将这个块在主存储器中的地址传给请求者

缓冲区替换策略

大多数操作系统使用最近最少使用策略（least recently used, LRU）；由查询优化器提供的带有提示的混合替换策略是较好的选择

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

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

如：数据字典被经常访问
因此：将数据字典的块保留在主存储器的缓存中

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

顺序索引

索引

索引机制用来加速对所需数据的访问
搜索码：用于在文件中查找记录的属性或属性集
- 索引是基于某个（或某些）搜索码建立的
索引文件一般比原文件小很多

一个索引文件包含如下形式的记录 (称为索引项)：K-P

![[images/Pasted image 20260110135616.png]]

基本类型索引：

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

评价指标

访问类型：能有效支持的访问类型

具有特定属性值的所有记录（特定值查询）
属性值在某个特定范围内的所有记录（范围查询）

评价因素：

访问时间
插入时间
删除时间
空间开销

顺序索引

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

稠密索引和稀疏索引

稠密索引

稠密索引：文件中每个搜索码值有一个索引记录

![[images/Pasted image 20260110140547.png]]

稀疏索引

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

在记录按照搜索码顺序排列时适用
寻找搜索值 K 的记录
- 找到最大搜索码值小于或等于 K 的索引项
- 从该索引项指向的记录开始，沿着文件中的指针查找，直到找到所需记录为止

对比

稀疏索引插入和删除时所需的空间及维护开销较小
稀疏索引定位一条记录的速度比较慢

折中方案：为每个块建一个索引项（块起始搜索码）的稀疏索引

多级索引

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

解决方法：将主索引以顺序文件的形式放于磁盘，并为其建立一个稀疏索引

具有两级或两级以上的索引称为多级索引

外层索引：主索引的稀疏索引
内层索引：主索引文件

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

![[images/Pasted image 20260110140933.png]]

辅助索引

希望找到某一特定字段（非主索引的搜索码）符合某些条件的所有记录

每个搜索码值都有一个索引记录（稠密索引）
索引记录指向包含所有指向具有特定搜索键值的实际记录的指针
辅助索引必须是稠密的，不可能存在辅助稀疏索引

但是索引的更新会给数据库的修改带来额外的开销，每当文件被修改时，这个文件上的每个索引都要更新

使用辅助索引的花费大于主索引

多码索引

复合搜索码是指包含不止一个属性的搜索码

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

如果 $a_1 < b_1$
或者 $a_1=b_1$ 且 $a_2 < b_2$

B+数索引

B+树被广泛运用于数据库系统索引的数据结构

![[images/Pasted image 20260110145006.png]]

B+树索引文件

使用顺序索引的缺点：

性能随着文件的增长而下降，因为创建了许多溢出块
需要定期重组整个文件

B+树索引文件的优势：

在面对插入和删除时，使用小的局部更改自动重组
不需要重组整个文件来保持查询性能

B+树索引缺点：

额外的插入和删除开销，空间开销（但是影响不大）

B+树

B+树结构

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

特殊情况：

如果根节点是一个非叶节点，则它至少有 2 个子节点
如果根节点是一个叶子节点，则它可以有 $0$ 到 $(n-1)$ 个值（即搜索码）

B+树节点结构

![[images/Pasted image 20260110145235.png]]

$K_i$：搜索码的值
$P_i$：指向子节点（对于非叶节点）或指向记录或记录桶（对于叶节点）的指针

一个节点中的搜索码是按顺序排序的

$$
K_1< K_2< K_3<\dots< K_{n–1}
$$

B+树叶子节点

叶子节点具有如下属性：

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

B+树非叶子节点

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

$P_1$ 所在的子树中的所有搜索码都小于 $K_1$
对于 $2 \leq i \leq n – 1$，$P_i$ 所在子树的所有搜索码的值大于或等于 $K_{i–1}$、且小于 $K_i$
$P_n$ 所在的子树中的所有搜索键的值大于或等于 $K_{n–1}$

![[images/Pasted image 20260110154038.png]]

示例：n=6

![[images/Pasted image 20260110154156.png]]

叶子节点搜索码的数量必须在 3（$\ulcorner (n−1)/2\urcorner$ ）到 5 （$n-1$）个之间
除根以外的非叶节点必须有 3（$\ulcorner n /2\urcorner$ ）到 6（$n$）个子节点
根（非叶节点）必须至少有 2 个子节点

B+树特性

B+树形成了一个稀疏索引的层次结构
B+树可以用相对较少的层次来表示大量的搜索码
- 低于根的一个级别子树至少有 $2* \ulcorner n/2\urcorner$ 个搜索码值
- 再下一级别则至少有 $2* \ulcorner n/2\urcorner *\ulcorner n/2\urcorner$ 个搜索码值
如果索引文件中有 K 个搜索键值，则树的高度（即搜索路径长度）不超过 $\urcorner \log_{\ulcorner n / 2 \urcorner}(K))\urcorner$ ，可以利用 B+树进行有效地搜索
B+树索引可以在有限时间内（与树的高度成正比关系）进行有效重构，可以有效地处理对主文件的插入和删除

B+树查询

特定值查找

从根向下遍历树，直到到达包含特定值 v 的叶子结点为止、或者返回 NULL

范围查找

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

查找次数

典型 B+树的节点规模通常与磁盘块的大小相同，通常取值为 4KB
- n 通常取值为 100 左右（每个索引条目 40 字节）
对于有 100 万个搜索码的索引文件、且 n=100
- 则最多查询 $\log _{50}(1,000,000) = 4$ 个节点（4 个块），即可完成从根到叶子节点的遍历

B 树索引

B 树索引文件

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

![[images/Pasted image 20260110155201.png]]

非叶节点指针 $B_i$ 是桶或文件记录指针

B 树索引优缺点

B 树的优点：

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

B 树的缺点：

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

![[images/Pasted image 20260110155317.png]]

散列索引

静态散列

桶是能存储一条或多条记录的一个存储单元(一个桶就是一个磁盘块)
在散列文件组织中，通过使用散列函数直接从搜索码中获得包含该记录的桶
散列函数 $h$ 是一个从 $K$ 到 $B$ 的函数
- $K$ 表示所有搜索码值的集合
- $B$ 表示所有桶地址的集合
散列函数用来为获取、插入和删除操作定位记录
具有不同搜索码值的记录可能映射到同一个桶，因此整个桶都要被顺序搜索来定位记录

散列文件组织

![[images/Pasted image 20260110155614.png]]

散列函数

理想的散列函数是均匀的。即：散列函数从所有可能的搜索码值集合中为每个桶分配同样数量的搜索码值
理想的散列函数是随机的，不管搜索码值实际怎样分布，每个桶应分配到的搜索码值数目几乎相同
最坏的可能是散列函数把所有的搜索码值映射到同一桶中；这使得访问时间与文件中的搜索码的数量成正比
散列索引无法支持范围查询

桶溢出

发生原因：

桶不足
偏斜
- 多个记录有相同的搜索码值
- 所选的散列函数可能会造成搜索码的分布不均

桶溢出可以减少，但是不能消除

用溢出桶来解决桶溢出问题

桶溢出处理

拉链法或开放寻址法

闭散列/闭地址

溢出链：一个给定桶的所有溢出桶用一个链接列表链接在一起

![[images/Pasted image 20260110155820.png]]

开散列

桶集合是固定的，没有溢出链，当一个桶满了后，系统将记录插入到初始桶集合的其他桶中

SQL 索引定义

创建索引

创建普通索引

-- 在 name 列上创建名为 idx_employee_name 的索引
CREATE INDEX idx_employee_name ON Employee (name);

创建复合索引

-- 在 dept 和 salary 上创建复合索引
CREATE INDEX idx_employee_dept_salary ON Employee (dept, salary);

创建唯一索引

-- 如果希望员工姓名唯一（实际中可能不合理，仅作示例）
CREATE UNIQUE INDEX idx_employee_unique_name ON Employee (name);

删除索引

-- 删除名为 idx_employee_name 的索引
DROP INDEX idx_employee_name;