ch14 索引

索引基本概念

加快访问所需数据的速度（例如图书馆的作者目录、字典）

搜索码：用于在文件中查找记录的属性（集）

索引文件中索引项由搜索码和指针构成

s e a r c h - k e y_{1} p o i n t e r_{1}

s e a r c h - k e y_{2} p o i n t e r_{2}

s e a r c h - k e y_{3} p o i n t e r_{3}

. . . . . .

索引文件远小于源文件

基本索引类型：顺序索引（按照搜索码的值顺序排列）和散列索引（基于将值平均分布在若干桶中，一个值所属的桶是由一个函数决定，该函数称之为散列函数）

索引的评价指标

能有效支持的访问类型
访问时间
插入时间
删除时间
空间开销

顺序索引

在一个顺序索引中，索引项按照搜索码的值的排序顺序存储

主索引/聚集索引：包含记录的文件按照某个搜索码指定的顺序排序，该索引称为主索引（搜索码常常是主码）

辅助索引/非聚集索引：搜索码指定的顺序与文件中记录的物理顺序不同的索引

索引顺序文件：在搜索码上有聚集索引的文件

稠密索引文件

稠密索引：文件中每个搜索码值都有一个索引项

搜索码	指针		ID	Name	Dept_Name	Salary	ptr
$10101$	$p t r_{1}$	$\overset{指向}{\to}$	$10101$	$S r i n i v a s a n$	$C o m p . S c i .$	$65000$	$↓$
$12121$	$p t r_{2}$	$\overset{指向}{\to}$	$12121$	$W u$	$F i n a n c e$	$90000$	$↓$
$15151$	$p t r_{3}$	$\overset{指向}{\to}$	$15151$	$M o z a r t$	$M u s i c$	$40000$	$↓$
$. . .$	$. . .$	$. . .$	$. . .$	$. . .$	$. . .$	$. . .$	$. . .$
$83821$	$p t r_{n - 1}$	$\overset{指向}{\to}$	$83821$	$B r a n d t$	$C o m p . S c i .$	$92000$	$↓$
$98345$	$p t r_{n}$	$\overset{指向}{\to}$	$98345$	$K i m$	$E l e c . E n g .$	$80000$	$\times$

上表中ID作为索引码，ID储存时按照顺序

搜索码	指针		ID	Name	Dept_Name	Salary	ptr
$C o m p . S c i .$	$p t r_{1}$	$\overset{指向}{\to}$	$10101$	$S r i n i v a s a n$	$C o m p . S c i .$	$65000$	$↓$
			$45565$	$K a t z$	$C o m p . S c i .$	$75000$	$↓$
			$83821$	$B r a n d t$	$C o m p . S c i .$	$92000$	$↓$
$E l e c . E n g .$	$p t r_{2}$	$\overset{指向}{\to}$	$98345$	$K i m$	$E l e c . E n g .$	$80000$	$↓$
$. . .$	$. . .$	$. . .$	$. . .$	$. . .$	$. . .$	$. . .$	$. . .$
$M u s i c$	$p t r_{n}$	$\overset{指向}{\to}$	$15151$	$M o z a r t$	$M u s i c$	$40000$	$\times$

上表中Dept_Name作为索引码，Dept_Name储存时按照顺序，仍然是稠密索引（对于索引码的每一个值都建立了索引），当记录有多条时指向第一条

稀疏索引文件

稀疏索引：只为搜索码的某些值建立索引项，只有索引是聚集索引的时候才能使用稀疏索引

搜索码	指针		ID	Name	Dept_Name	Salary	ptr
$10101$	$p t r_{1}$	$\overset{指向}{\to}$	$10101$	$S r i n i v a s a n$	$C o m p . S c i .$	$65000$	$↓$
			$12121$	$W u$	$F i n a n c e$	$90000$	$↓$
$15151$	$p t r_{2}$	$\overset{指向}{\to}$	$15151$	$M o z a r t$	$M u s i c$	$40000$	$↓$
$. . .$	$. . .$	$. . .$	$. . .$	$. . .$	$. . .$	$. . .$	$. . .$
$83821$	$p t r_{3}$	$\overset{指向}{\to}$	$83821$	$B r a n d t$	$C o m p . S c i .$	$92000$	$↓$
			$98345$	$K i m$	$E l e c . E n g .$	$80000$	$\times$

为了定位一个搜索码值为 $K$ 的记录，需要：1.找到搜索码值 $< K$ 的最大索引项 2.从该索引项所指的记录开始，沿着文件中的指针查找，直到找到记录为止
与稠密索引比空间开销更小，插入和删除的开销也更小；但是定位一条记录时通常比稠密索引慢
为文件中的每一个块建立一个索引项的稀疏索引是一个很好的折中方案

多级索引

如果主索引不能放在内存中，访问效率将会变低，解决方案是把主索引当作一个连续的文件保留在磁盘上，创建主索引上的一个稀疏索引
此时外层索引是主索引上的稀疏索引，内层索引是主索引
如果外层索引还是太大无法放入内存可以再继续建立次级索引，依次类推
对文件进行插入删除操作的时候各级索引都需要更新

辅助索引

索引记录指向一个包含所有具有特定搜索码值的实际记录的指针的桶
辅助索引必须稠密
可以找到属性值再某个满足一定条件的域（不是主索引的搜索码的域）内的所有记录
可以使用一个对每个搜索码都具有索引项的辅助索引

主索引和辅助索引

索引为检索提供了巨大的便利
索引更新的开销强加于数据库之上（当一个文件被修改时，此文件上所有索引也必须更新）
按主索引顺序对文件进行扫描非常有效，但是是由辅助索引进行顺序扫描很费时

索引更新：插入

单级索引插入：用被插入记录的搜索码值进行一次检索。对于稠密索引：如果搜索码值没有出现在索引中，将其插入。对于稀疏索引：如果索引文件中的每个块只储存了一个索引项，除非创建了新的块，否则不做更改；如果创造了新的块，那么把出现在新的块中的第一个搜索码的值插入到索引项中
多级索引的插入与删除是单级索引插入删除算法的简单扩展

索引更新：删除

如果被删除的记录是具有某个搜索码值的唯一记录，那么这个搜索码值也会同时被删除。
单级索引删除：对于稠密索引，搜索码的删除和文件记录的删除类似。对于多级索引，对应某个搜索码值的索引项，他被删除是通过用下一个搜索码值替代该索引项来完成的，如果下个搜索码值已经有索引项了，此索引项直接删除

B+树索引文件

是一种索引顺序文件的替代

索引顺序文件的缺点：随着文件增大索引查找性能和数据的顺序扫描性能都会下降，这是由于许多溢出块会被创建，需要频繁重组整个文件

B+树索引文件的优点：在插入和删除时能够通过小的自动调整来保持平衡，不需要重组文件来维持性能

B+树索引文件的缺点：增加了文件插入和删除的时间开销，增加空间开销

整体利大于弊，被广泛应用

B+树

平衡，从根节点到叶节点所有路径长度是一致的
每一个非根节点有 $⌈ \frac{n}{2} ⌉$ 到 $n$ 个孩子节点
一个叶子节点有 $⌈ \frac{n - 1}{2} ⌉$ 到 $n - 1$ 个值
特例：根节点如果是非叶节点至少有 $2$ 个孩子；如果根节点是一个叶节点，那么他有 $0$ 到 $1$ 个值

B+树节点结构

典型节点

P_{1} K_{1} P_{2} . . . P_{n - 1} K_{n - 1} P_{n}

其中 $K_{i}$ 是搜索码， $P_{i}$ 是指向孩子节点的指针（对于非叶子节点）或者指向记录或记录桶的指针（对于叶子节点）

搜索码是有序的（假设不重复）：

K_{1} < K_{2} < K_{3} < . . . < K_{n - 1}

叶子节点属性
1. 指针 $P_{i} (i = 1, 2, 3, . . ., n - 1)$ 指向搜索码值为 $K_{i}$ 的文件记录
2. 如果 $L_{i}, L_{j}$ 是叶子节点且 $i < j$ ，那么 $L_{i}$ 的搜索码的值小于或者等于 $L_{j}$ 的搜索码的值
3. $P_{n}$ 指向按搜索码排序的下一个叶节点
非叶子节点上形成一个多级稀疏索引，对于一个包含了 $m$ 个指针的非叶子节点：
1. $P_{1}$ 指针所指子树上的所有搜索码的值小于 $K_{1}$
2. 对于 $2 < i < n - 1$ ， $P_{i}$ 指针所指的子树上的所有搜索码的值大于或者等于 $K_{i - 1}$ 且小于 $K_{i}$
3. $P_{n}$ 指针所指子树上的所有搜索码值大于或等于 $K_{n - 1}$

P_{1} K_{1} P_{2} . . . P_{n - 1} K_{n - 1} P_{n}

观察B+树

由于节点间通过指针进行连接，逻辑临近的块不一定在物理上临近
B+树的一层非叶子节点构成一级稀疏索引
B+树的每层有如下特点：
1. 根节点下面的一层节点至少有 $2 * ⌈ \frac{n}{2} ⌉$ 个值
2. 下一层节点至少有 $2 * ⌈ \frac{n}{2} ⌉ * ⌈ \frac{n}{2} ⌉$ 个值
3. 如果在文件中有 $K$ 个搜索码值，树的高度不超过 $⌈ \log_{⌈ \frac{n}{2} ⌉} K ⌉$ ，从而可以有效的进行检索
可以高效的对主文件进行插入和删除操作，并且索引可以在对数时间内重构

重复处理

对于重复的搜索码
1. 叶节点和内部节点
  我们无法保证 $K_{1} < K_{2} < K_{3} < . . . < K_{n - 1}$
  但是可以保证 $K_{1} \leq K_{2} \leq K_{3} \leq . . . \leq K_{n - 1}$
2. $P_{i}$ 指针所指向的子树的搜索码
  是 $\leq K_{i}$ 但不一定 $< K_{i}$
  假设存在相同的搜索码值 $V$ 存在于两个叶节点 $L_{i}$ 和 $L_{i + 1}$ 中，则父节点 $K_{i}$ 就必须等于 $V$
三种替代方案
1. 在单独的块中建立桶（不好的方法）
2. 建立指针列表
3. 创建包含原始搜索码和其他属性的复合搜索码来使得搜索码唯一

B+树文件组织

通过使用B+树索引可以解决索引文件退化问题
通过使用B+树文件组织可以解决数据文件退化问题
用B+树文件组织的叶节点储存结构，而不是使用指针
叶节点仍需要半满
插入删除与B+树索引一致

记录比指针使用的空间更多，所以良好的空间利用率是非常重要的。为了提高空间利用率，会涉及到更多的兄弟节点的重新分配和分裂合并

散列索引

散列：

桶：能储存一条或多条记录的存储单位，通常一个桶就是一个磁盘块
在散列文件组织中可以直接从搜索码使用散列函数得到包含记录的桶
散列函数 $h$ 是一个从所有的搜索码集合 $K$ 映射到桶地址的集合 $B$ 的函数
散列函数用于用来丁文要访问，插入或删除的记录
带有不同搜索码值的记录可以被映射到一个桶中，因此，为了找到一个记录，桶要被一次检索

散列函数

最糟糕的散列函数把所有的搜索码值映射到一个桶，导致查询花费时间与文件中搜索码数成正比
理想的散列函数是均匀的
理想的散列函数是随机的
通常的散列函数在搜索码中字符的内部二进制机器表示上执行计算

桶溢出处理

桶溢出原因
1. 桶不足
2. 偏斜
尽管分配的桶比需要多一些，但是桶溢出还是有可能发生

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

散列索引

散列不仅可用于文件组织，也可用于索引
散列索引将搜索码及其相应的指针组织成散列文件结构
严格来说，散列索引只是一种辅助索引结构

静态散列的不足

静态散列要求固定桶地址集合 $B$ ，但是大多数的数据库都会随着时间而变大，这会带来很严重的问题
如果初始桶的数目太小，随着文件的增长，由于溢出的产生，导致性能下降
周期性重组：规模大，耗时，扰乱正常操作
更好的解决方案：允许桶的数量动态变化

顺序索引和散列的比较

周期性重组的代价？
插入删除的相对频率？
是否愿意以增加最坏情况下的访问时间为代价优化平均访问时间？
用户可能提出的查询类型？
可以高效的对主文件进行插入和删除操作，并且索引可以在对数时间内重构

多码访问

多码检索应使用多个索引或使用建立在多个属性索引码上的索引
使用单属性索引的策略：先使用一个索引，在结果集上检验；或分别使用两个索引结果取交集

复合索引

复合搜索码：搜索码有多个属性，数据排列有顺序，查询也要注意顺序（在前边的只能取等号才能用得上索引，用 $<$ 或 $>$ 就用不上了）

覆盖索引

索引中储存了一些其他值（非搜索码属性）
可以只用索引找到结果，无需扫描数据文件
仅在叶子节点存储这些值，引起索引树的扁平

创建索引

sql

Create Index <index_name> on <relation_name> (<attribute_list>)

可以使用Create Unique Index来强制性的指定搜索码是一个候选码（但是null是可以放进去的，不要求非空只要求唯一）
删除索引

sql

Drop Index <index_name>

不同的DBMS对于索引有不同的策略，很多的DBMS也提供一种方法来详细说明要使用的索引类型；有些DBMS也允许一个关系上的某个索引声明是聚集的；有些DBMS给关系上的主码自动建立索引
有些DBMS给关系上的外码自动建立索引

t a k e s ⋈ σ_{n a m e =^{'} S h a n k e r^{'}} (s t u d e n t)

索引能提高查找速度，但是也会大大提升更新成本

写优化索引结构

B+树随机读写操作会导致性能变得非常差，每处理一个叶节点都需要一次I/O
高效写入方法：
1. 日志结构合并树 Log-structured merge tree
2. 缓冲树 Buffer tree

日志结构合并树LSM

算法
- 记录先插入到内存树 $L_{0} t r e e$
- 内存树满了转移至磁盘 $L_{1} t r e e$
  - $L_{0} t r e e$ 与已经存在的 $L_{1} t r e e$ 进行归并
  - 顺次分配新的叶子节点，避免了随机写
- 当 $L_{1} t r e e$ 过大，再归并至 $L_{2} t r e e$
- 以此类推...每个 $L_{n + 1} t r e e$ 的大小都是 $L_{n} t r e e$ 的 $k$ 倍
优点
- 新叶子按顺序分配，避免了后续归并出现的随机I/O操作
- 叶子是满的，避免了页面拆分可能出现的部分占有叶子的开销
- 跟普通的B+树相比减少了插入时的I/O操作
缺点
- 查询需要检索多棵树
- 每个记录可能在特定级别写多次
阶梯式合并索引
- 每层多棵树
- 减少写代价，提高查询代价

缓冲树

LSM树的替代方案
- B+树的每个内部节点都有一个缓冲区来储存插入的信息
- 新纪录先插入到根缓冲区，缓冲区满了统一推送至下一层节点
- 以此类推...
优点
- 查询加快
- 可以用于任何类型树结构索引
缺点：更多的随机I/O

位图索引

一种特殊索引，高效查询多个key
针对列中大量相同值的列（例如性别）
作用
- 含 $=$ 的谓词和计数类查询可用

record_number	ID	gender	income_level
0	76766	m	L1
1	22222	f	L2
2	12121	f	L1
3	15151	m	L4
4	58583	f	L3

对于上表， $g e n d e r$ 的位图

m 10010

f 01101

$i n c o m e_l e v e l$ 的位图

L 1 10100

L 2 01000

L 3 00001

L 4 00010

L 5 00000

此时给定一个编号 $n$ ，很容易就能检索到记录 $n$

位图是一个位数组，或者一个向量，长度与记录的条数相对应
- 如果编号为 $i$ 的记录在属性 $A$ 的值为 $v_{i}$ ，那么位图中的第 $i$ 位为 $1$ ，而该位图其他所有位置设置为 $0$
$r$ 关系在 $A$ 属性上的位图索引有 $A$ 能取的所有值对应的位图构成
位图索引不适合列中值太多的情况
创建位图索引

sql

Create Bitmap Index gender_bitmap on info(gender)

位图索引对于查询多个属性很有用，可以用 $A n d / O r / N o t$ 操作，每个操作取两个大小相同的位图，并对相应的位应用该操作获得结果位图

100110 A n d 110011 = 100010

100110 O r 110011 = 110111

N o t 100110 = 011001

相比于关系本身，位图索引很小

时空数据索引

关系型数据库存储和检索空间信息
- 使用空间条件的查询（包含或重叠）
- 混合使用空间条件和非空间条件的查询
最近邻查询：查找最近的目标
范围查询：查找指定范围的目标
传统索引就会导致比较差的性能

空间数据索引

k-d树索引——多维索引
二分+迭代：
- 每一层把空间分成两个部分
- 树根层沿着一个维度一分为二，两边点数量尽量相同
- 下次分割沿着另一个维度，以此推至结束
四叉树
- 每个节点与一个矩形空间相关联
- 顶部节点与整个空间相关联
- 每个非叶节点把其对应的区域划分为四个大小相等的象限
- 每个节点有四个对应于四个象限的子节点，以此类推
- 叶结点的点数在零和某个固定的最大值之间
R树——B+树的N维扩展，用于索引矩形和其他多边形的集合
- 将与每个B+树节点相关联的一维区间概念推广到N维区间，即N维矩形
- 节点的边框是一个包含该节点并于节点轴平行的最小尺寸的矩形
- 最坏情况下可能非常低效，可能会搜索多条路径，但是在实践中可以接受

时间数据索引

时间数据：具有相关时间段（间隔）的数据
时间段包含起始时间到终止时间
查询可能会在某个时间点或某个时间段内有效的所有元组
- 比如属性 $a = v$ 和一个时间点 $t_{1}$
  - 如果时间区间数量不多可以直接用 $a$ 上的索引，再验证 $t_{1}$ 是否符合标准
  - 如果时间区间数量很多可以考虑用R树，把 $a$ 当成一个维度，时间是另一个维度

ch14 索引 ​

索引基本概念 ​

索引的评价指标 ​

顺序索引 ​

稠密索引文件 ​

稀疏索引文件 ​

多级索引 ​

辅助索引 ​

主索引和辅助索引 ​

索引更新：插入 ​

索引更新：删除 ​

B+树索引文件 ​

B+树节点结构 ​

观察B+树 ​

重复处理 ​

B+树文件组织 ​

散列索引 ​

散列函数 ​

桶溢出处理 ​

散列索引 ​

静态散列的不足 ​

顺序索引和散列的比较 ​

多码访问 ​

复合索引 ​

覆盖索引 ​

创建索引 ​

写优化索引结构 ​

日志结构合并树LSM ​

缓冲树 ​

位图索引 ​

时空数据索引 ​

空间数据索引 ​

时间数据索引 ​

ch14 索引

索引基本概念

索引的评价指标

顺序索引

稠密索引文件

稀疏索引文件

多级索引

辅助索引

主索引和辅助索引

索引更新：插入

索引更新：删除

B+树索引文件

B+树节点结构

观察B+树

重复处理

B+树文件组织

散列索引

散列函数

桶溢出处理

散列索引

静态散列的不足

顺序索引和散列的比较

多码访问

复合索引

覆盖索引

创建索引

写优化索引结构

日志结构合并树LSM

缓冲树

位图索引

时空数据索引

空间数据索引

时间数据索引