数据库系统原理与实践 笔记 #10

存储管理与索引(续)

数据字典存储

• 数据字典：也称系统目录存储元数据（即关于数据的数据）
• 关系的信息：
  • 关系的名字
  • 每个关系属性的名字、类型和长度
  • 视图的名字和定义
  • 完整性约束
• 用户和账户信息，包括密码
• 统计和描述性数据：每个关系中的元组数目
• 物理文件组织信息：
  • 关系如何存储(顺序/散列/…)
  • 关系的物理位置
• 索引的信息

系统元数据的关系表示

• 磁盘上关系的表示
• 为在内存中进行高效访问而设计的特殊数据结构（微型数据库）
  ,源站可能有防盗链机制,建议将图片保存下来直接上传](https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=image-18.png&pos_id=img-cCHHBIDt-1701068752975)

数据缓冲区

存储访问

• 每个文件分成定长的存储单元，称为块。块是存储分配和数据传输的基本单元
• 数据库系统的一个主要目标就是减少磁盘和存储器之间传输的块数。减少磁盘访问次数的一种方法是在主存储器中保留尽可能多的块
• 缓冲区：主存储器中用于存储磁盘块的副本的那一部分
• 缓冲区管理器：负责缓冲区空间的子系统

缓冲区管理器

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

• 1.如果这个块已经在缓冲区中，缓冲区管理器将这个块在主存储器中的地址传给请求者

• 2.如果这个块不在缓冲区中，缓冲区管理器

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

缓冲区替换策略

• 大多数操作系统使用LRU(最近最少使用策略 Least Recently Used)

• LRU—根据过去使用块的模式进行将来访问模式的预测

• 当设计对数据重复扫描的访问模式时，LRU是一个糟糕的策略

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

• 被钉住(Pinned)的块：不允许写回硬盘的块

• 立即丢弃策略：一旦块最后一个元组被处理完毕，就立刻命令缓冲区管理器释放这个块所占用的空间

• 最近最常使用策略(与LRU相反)：系统要替换最近一直在使用的块，当块中最后一个元组处理完毕后，块将被解除钉住，称为最近最常使用的块被移除

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

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

顺序索引

基本概念

• 索引机制用来加速对所需数据的访问
• 搜索码：用于在文件中查找记录的属性或属性集
• 一个索引文件包含如下形式的记录：

搜索码值	记录指针

• 索引文件一般比源文件小很多
• 两种基本类型索引：
  • 顺序索引：按搜索码顺序存储索引
  • 散列索引：使用散列函数将搜索码平均分布到若干散列桶中（一般作为辅助索引）

索引技术评价指标

• 访问类型：能有效支持的访问类型。例如：
  • 具有特定属性值的所有记录
  • 属性值在某个特定范围内的所有记录
• 访问、插入、删除时间、空间开销

顺序索引

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

稠密索引

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

稀疏索引

• 系数索引：只为搜索码的某些值建立索引记录：在记录按照搜索码顺序排列时适用
• 寻找有搜索值K的记录：
  • 找到最大搜索码值小于或等于K的索引值
  • 从该索引项指向的记录开始，沿着文件中的指针查找，查到找到所需记录为止

索引

• 稠密索引和稀疏索引对比：
  • 稀疏索引插入和删除时所需的空间及维护开销较小
  • 稀疏索引定位一条记录的速度比较慢
• 好的折中方案：为每个块建一个索引项（块起始搜索码）的系数索引
  

多级索引

• 如果主索引太大无法放入主存，那么开销就很大
• 解决方案：将主索引以顺序文件的形式放于磁盘，并为其建立一个系数索引
• 具有两级或两级以上的索引称为多级索引：
  • 外层索引—主索引的稀疏索引
  • 内层索引—主索引文件
• 如果外层索引还是太大，那么就可以再建另外一级索引，以此类推
• 对文件进行插入或删除操作后，所有级别的索引都需要更新

辅助索引

• 通常，我们希望找到某一特定字段（非主索引的搜索码）符合某些条件的所有记录
• 我们可以使用一个副主索引：每个搜索码都有一个索引记录（稠密索引）
• 索引记录指向包含所有指向具有特定搜索键值的实际记录的指针
• 辅助索引必须是稠密的，即不可能存在辅助稀疏索引

主索引与辅助索引

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

多码索引

• 复合搜索码是指包含不止一个属性的搜索码
• 词典顺序：$(a_1,a_2)<(b_1,b_2)$如果：
  • $a_1<b_1$，或
  • $a_1=b_1$且$a_2<b_2$

B+树索引

B+树索引文件

• 使用顺序索引的缺点：
  • 性能随着文件的增长而下降，因为创建了许多溢出块
  • 需要定期重组整个文件
• B+树索引文件的优势：
  • 在面对插入和删除时，使用小的局部更改自动重组
  • 不需要重组整个文件来保持查询性能
• B+树索引缺点：额外的插入和删除开销、空间开销
• B+树被广泛运用于数据库系统索引的数据结构

• B+树是一种满足以下属性的树：
  • 从根到所有叶的路径的长度都是相同的
  • 每个非叶结点（除根节点之外）都有$\lceil \frac{n}{2}\rceil$到$n$个子节点
  • 一个叶结点可包含搜索码的数量在$\lceil \frac{n-1}{2}\rceil$到$n-1$之间
• 特殊情况：
  • 如果根结点是一个非叶结点，则它至少有两个子结点
  • 如果根结点是一个叶子结点，则它可以有0到$n-1$个值（搜索码）

B+树结点结构

• B+树的典型结点
  

  • $K_i$搜索码的值
  • $P_i$是指向子节点(对于非叶结点)或指向记录或记录桶(对于叶结点)的指针

• 一个结点中的搜索码是按顺序排序的：
  $$K_1<K_2<K_3<...<K_{n-1}$$

B+树中的叶结点

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

B+树中的非叶结点

• 非叶结点在叶子结点之上形成了一个多级（稀疏）索引。对于带有m个指针（m称之为扇出,fanout）的非叶结点：
  • $P_1$所在的子树中的所有搜索码都小于$K_1$
  • 对于$2\le i\le n-1$，$P_i$所在子树的所有搜索码的值大于或等于$K_{i-1}$、且小于$K_i$
  • $P_n$所在的子树中的所有搜索键的值大于或等于$K_{n-1}$

B+树特性

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

B+树的查询

• 典型B+树的结点规模通常和磁盘块的大小相同，通常取值为4KB
  • 因此，n通常取值为100左右(每个索引条目40字节)
• 对于有100万个搜索码的索引文件，n=100
  • 最多查询${\log }_{50}(1,000,000)=4$个结点（4个块），即可完成从根到叶子结点的遍历
• 将其与具有100万个搜索键值的平衡二叉树(AVL树)对比：再一次查找中需要访问大约20个结点

B树索引文件

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

B树索引的优缺点

• B树的优点：
  • 可能比相应的B+树使用更少的结点
  • 有时可以在到达结点之前找到搜索码
• B树的缺点：
  • 在所有搜索码中，只有一小部分被早期找到
  • 非叶结点需要存储搜索码的记录指针，所以扇出相应地变小了。因此，B树通常比B+树具有更大的深度
  • 插入和删除比B+树更复杂
  • 实现比B+树更难

散列索引

静态散列

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

散列函数

• 一个理想的散列函数是均匀的。即：散列函数从所有可能的搜索码值集合中为每个桶分配同样数量的搜索码值
• 理想的散列函数是随机的的，不管搜索码值怎样分布，每个桶应分配到的搜索码值数目几乎相同
• 最坏的可能是散列函数把所有的搜索码值映射到同一个桶中；这使得访问时间与文件中的搜索码的数量成正比
• 通常散列函数依据搜索码字符的二进制码来计算
  • 这种类型的一个简单散列函数是先计算码中字符的二进制码的综合，然后返回该总和取桶数目的模
• 散列索引无法支持范围查询

桶溢出处理

• 溢出链：一个给定桶的所有溢出桶用一个链接列表链接在一起
• 开散列：桶集合固定，没有溢出链，当一个桶满了之后，系统将记录插入到初始桶集合的其他桶中

SQL中的索引定义

SQL中的索引定义

• 创建索引

create index <索引名> on <关系名>(<属性列表>);
# 例如
create index b-index on branch(branch_name);

• 使用create unique index直接声明该搜索码是一个候选码
  • 如果数据库系统支持SQL标准的unique声明，那么这里的unique特性就是多余的
• 撤销索引

drop index <索引名>;

• 大多数数据库允许指定索引类型，并声明聚集索引