第十二、十三章

RAID

RAID：Redundant Arrays of Independent Disks(独立磁盘冗余阵列) 其实就是用多个独立的磁盘组成在一起形成一个大的磁盘系统，从而实现比单块磁盘更好的存储性能和更高的可靠性。

RAID5

这是目前用的最多的一种方式。
因为 RAID5 是一种将存储性能、数据安全、存储成本兼顾的一种方案。

在了解RAID5之前，我们可以先简单看一下RAID3，虽然RAID3用的很少，但弄清楚了RAID3就很容易明白RAID5的思路。

RAID3的方式是：将数据按照RAID0的形式，分成多份同时写入多块磁盘，但是还会另外再留出一块磁盘用于写「奇偶校验码」。例如总共有N块磁盘，那么就会让其中额度N-1块用来并发的写数据，第N块磁盘用记录校验码数据。一旦某一块磁盘坏掉了，就可以利用其它的N-1块磁盘去恢复数据。

但是由于第N块磁盘是校验码磁盘，因此有任何数据的写入都会要去更新这块磁盘，导致这块磁盘的读写是最频繁的，也就非常的容易损坏。

RAID5的方式可以说是对RAID3进行了改进。

RAID5模式中，不再需要用单独的磁盘写校验码了。它把校验码信息分布到各个磁盘上。例如，总共有N块磁盘，那么会将要写入的数据分成N份，并发的写入到N块磁盘中，同时还将数据的校验码信息也写入到这N块磁盘中（数据与对应的校验码信息必须得分开存储在不同的磁盘上）。一旦某一块磁盘损坏了，就可以用剩下的数据和对应的奇偶校验码信息去恢复损坏的数据。

RAID5校验位算法原理：P = D1 xor D2 xor D3 … xor Dn （D1,D2,D3 … Dn为数据块，P为校验，xor为异或运算）

RAID5的方式，最少需要三块磁盘来组建磁盘阵列，允许最多同时坏一块磁盘。如果有两块磁盘同时损坏了，那数据就无法恢复了。

数据库存储架构

持久性数据存储在非易失存储器中，通常是磁盘或者固态硬盘

磁盘和固态硬盘均是块结构设备，即以块为单位读或者写数据
数据库处理记录，一个记录通常比块小很多

大多数数据库使用操作系统文件作为存储记录的中间层，抽象底层块的细节

磁盘块访问的优化

来自磁盘的连续请求
- 顺序访问
  - 连续的请求会请求处于相同的磁道或者相邻的磁道上连续的块，第一块需要磁盘寻道，相邻的请求不需要寻道
- 随机访问
  - l相邻的请求会请求那些随机位于磁盘上的块，每一个请求都需要一次磁盘寻道
缓冲buffer
- 从磁盘中读取的块暂存在内存缓冲区中，以满足将来的需求
预读
- 当一个块被访问时，相同磁道的连续块也被读入内存缓冲区，即使对这些块没有请求。这种解决方案对于顺序请求比较有利
调度
- 如果需要把一个柱面上的几个块从磁盘传输到主存储器，可以按块经过读写头的顺序发出访问请求。
- 磁盘臂调度算法决定块的访问顺序从而使磁盘臂移动的距离最短
  - LOOK(查找)调度算法：磁臂仅移动到请求的最外道就回转，反方向查找服务。
  - 如果请求调度的磁道为98, 183, 37, 122, 14, 124, 65, 67，磁头从53号磁道开始移动，磁头就会按照65, 67, 98, 122, 124, 183, 37,14 的顺序依次查找，并将数据输入内存。
文件组织 – 为了减少块访问时间，我们可以按照与预期的数据访问方式最接近的方式来组织磁盘上的块
- 一段时间后文件可能变得碎片化
- 一些系统提供减少碎片的功能以提高文件访问速度

文件组织

数据库被映射到多个不同的文件，每个文件分成定长的存储单元，称作块(block)，块是存储分配和数据传输的基本单元。
一个文件在逻辑上组织成为记录的一个序列，一个记录是多个字段的序列
一种实现方法
- 假设记录是定长的
- 每个文件都只有一种特定类型的记录
- 不同的文件被用于不同的关系
- 这种方法容易实现，后面将会考虑变长的记录
一个块包含很多记录，一个块包含的确切的记录集合是由使用的物理数据组织形式所决定的。
一般假定没有记录比块更大，这个假定对于大多数数据处理应用都是现实的。
- 除了BLOB与CLOB

定长记录

一种简单实现方法

从字节n * (i - 1)开始存储记录i， n是每个记录的长度

上述存放方式的缺点：

访问记录很容易，但是记录可能会分布在不同的块上

修改约束：不允许记录跨越块的边界

删除记录困难
- 删除记录所占的空间必须由文件的其他记录来填充，或者我们自己必须用一种方法标记删除的记录，使得它可以被忽略

删除记录i的3种选择

移动记录 i + 1, . . ., n到i, . . . , n - 1
移动记录 n 到 i
不移动记录，但是链接所有的空闲记录到一个 free list

变长记录

Attributes：属性。Null Bitmap的0000表示前面记录的四个属性都非空。

分槽的页结构

分槽的页结构一般用于在块中组织记录
分槽页页头，在每个块的块头(此处“页”=“块”)
- 记录条目的个数
- 块中空闲空间的末尾处
- 一个包含每条记录位置和大小的条目组成的数组
可以将记录在一页内移动以保证记录之间没有空闲的空间，则数组中信息也要更新
实际记录从块的尾部开始排列
块中空闲空间是连续的，在块头数组的最后一个条目和第一条记录之间
如果插入一条记录，在空闲的尾部给这条记录分配空间，并且将包含这条记录大小和位置的条目添加到块头中
如果一条记录被删除，它所占用的空间被释放，并且它的条目被设置成删除状态，块中被删除记录之前的记录被向后移动，由此删除产生的空闲空间与原先的空闲空间合并，并且所有的空闲空间在块头数组的最后一个条目和第一条记录之间
块头中的空闲末尾指针也要做适当的调整，

大对象

对于图片、音频等数据，这些数据比块大很多，可以使用blob和clob数据类型，大对象一般存储到一个特殊文件中，而不是与记录的其他属性存储在一起，然后一个指向该对象的指针存储到包含该大对象的记录中。大对象可以以文件形式存储在被数据库管理的一个文件系统区域中，或者作为文件结构在数据库中并被数据库管理。

第十四章、索引

索引基本概念

索引机制用于加快访问所需数据的速度，例如，字典

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

索引文件由 搜索码+指针 形式的记录(被称为索引项)组成，索引文件通常远小于原始文件

两种基本的索引类型

顺序索引
- 基于搜索码值的顺序排序
散列索引
- 基于将值平均分布到若干散列桶中
- 一个值所属的散列桶是由一个函数决定，该函数称为散列函数

索引评价指标

能有效支持的访问类型
- 具有特定属性值的记录
- 或者属性值基于某个特定范围内的记录
访问时间
- 在查询中使用该技术找到一个特定数据项或者数据项集合所需的时间
更新时间
- 增删改一个新数据项所需要的时间，包括找到增删改这个新数据项的正确位置所需的时间，以及更新索引结构所需的时间
空间开销
- 索引结构所占的额外存储空间，如果存储索引结构的额外空间大小适度，通常牺牲一定的空间代价来换取性能的提高是值得的

建立索引的原则

索引提高数据查询效率，但是影响数据更新的效率，建立索引的原则：

为经常用于查询条件的属性建立索引
为经常用于表连接的属性建立索引
为经常需要排序和分组属性建立索引
大部分DBMS为主码自动建立唯一索引
取值区分度高的属性适合建索引，取值重复度高的属性不适合建索引
充分利用复合索引
- 比如表中已经有属性a的索引，现在要增加属性a和属性b的索引(a,b)，那么只需要修改原来的索引即可

顺序索引

在一个顺序索引中，索引项按照搜索码值的排序顺序存储，并将每个搜索码的与包含该搜索码的记录关联起来

主索引：包含记录的文件按照某个搜索码指定的顺序排序，那么该搜索码对应的索引称为主索引
- 也被称为聚集索引
- 主索引的搜索码可以建立在主码上也可以建立在非主码属性上
辅助索引: 搜索码指定的顺序与文件中记录的物理顺序不同的索引。也称为非聚集索引
索引顺序文件: 在搜索码上有聚集索引的文件

稠密索引

在稠密索引中，文件中的每个搜索码值都有一个索引项。

举例：

稀疏索引

在稀疏索引中，只为搜索码的某些值建立索引项，只有索引是主索引(聚集索引)时才能使用稀疏索引。

为了定位一个搜索码值为 K 的记录，我们需要:
- 找到搜索码值 <K 的最大索引项
- 从该索引项所指向的记录开始，沿着文件中的指针查找，直到找到所需记录为止

与稠密索引比较:

稀疏索引所占空间较小，更有可能常驻内存，插入和删除时所需的维护开销也较小
稀疏索引定位一条记录时，通常比稠密索引更慢

为文件中的每个块建一个索引项的稀疏索引是一个很好的折中，索引项的搜索码是块中第一个元组值

多级索引

如果主索引不能放在内存中，访问效率将变低

单层索引在索引文件上使用二分搜索定位索引项，如果索引占b个块，二分搜索需要读取 $log_2(b)$ 个块

解决方案：把主索引当做一个连续的文件保留在磁盘上，创建一个它之上的稀疏索引

外层索引 – 主索引上的稀疏索引
内索层引 – 主索引文件

如果外层索引还是太大而无法放在内存中，可以再次创建一个次级索引，以此类推

多级索引的缺点：对文件进行插入或删除操作时，各级索引必须全部更新

索引更新

文件中有记录被删除或者插入时，每个索引都必须更新

文件中有记录被更新时，其搜索码属性受到更新影响的任何索引也必须被更新

单级索引插入:
- 用被插入记录的搜索码值进行一次检索
- 稠密索引
  - 如果搜索码值没有出现在索引中，将其插入
  - 否则
    - 如果索引项存储的是指向具有相同搜索码值的所有记录的指针，那么系统就在索引项中增加一个指向新纪录的指针
    - 否则，索引项存储一个仅指向具有相同搜索码值的第一条记录的指针，系统把待插入的记录放到具有相同搜索码值的其他记录后面
- 稀疏索引
  - 如果索引对文件中的每个块只存储一个索引项，除非创建了一个新的块，否则不对索引做任何改变
  - 如果创建了一个新的块，出现在新块中的第一个搜索码值被插入到索引项中
多级索引的插入和删除：算法是单级算法的简单扩展

删除

稠密索引

如果待删除的记录是具有这个特定搜索码值的唯一的记录，则系统就从索引中删除相应的索引项
否则
- 如果索引项存储的是具有相同搜索码的所有记录指针，则系统从索引项中删除指向待删除记录的指针
- 否则，索引项存储一个仅指向具有该搜索码值的第一条记录的指针，如果待删除的记录是具有该搜索码值的第一条记录，系统更新索引项，使其指向下一条记录

稀疏索引

如果索引中并不包含待删除记录搜索码值的索引项，则索引不作任何变动
否则
- 如果待删除记录是具有该搜索码值的唯一记录，系统用下一个搜索码值的索引记录替换相应的索引记录；如果下一个搜索码值已经有了一个索引项，则删除而不是替换
- 否则，如果该搜索码值的索引项指向待删除记录，系统更新索引项，使其指向具有相同搜索码值的下一条记录