数据库管理系统之存储和索引

一、基本概念

8.1 外部存储上的数据

在磁盘上读写存储信息的单位是页，页的大小是DBMS的一个参数，典型的值是4KB或者8KB.页I/O（从磁盘输入输入到主存和从主存输出到磁盘）的代价代表了典型的数据库操作的代价，因此优化数据库系统来减小这个代价十分重要。

谨记要点：

     1. 磁盘是最重要的外存设备，它允许以一个（或多或少）固定的代价来检索每一页，但是，如果我们按照页面存储的物理顺序连续读取若干页，所花的代价可能比以任意的顺序读取同样的页面要小得多。

     2. 磁带是顺序访问设备，需要我们一页一页的读，因此通常用于不常用的数据的存档

     3. 文件中的每一个记录都有一个唯一的标识符，成为记录id，简称rid，一个rid有一个属性，可以用于识别包含该记录的页在磁盘上的地址。

为了处理，文件需要读入内存，为了持久存储，数据需要写入磁盘，这些操作由成为缓冲区管理器的软件层来完成。磁盘上的空间由磁盘空间管理器来管理。

8.2 文件组织和索引

记录文件是DBMS的一个重要抽象，文件可以被创建，删除，以及向其中插入或者删除记录，文件层将文件中的记录存储于一组磁盘页。

最简单的文件结构树无序文件或者成为堆文件。

索引是在磁盘上组织数据记录的一种数据结构，用于优化某类数据检索的操作。我们使用术语数据项来指代存储在索引文件中的记录。搜索码值为k的数据项纪委k*，包含有足够的信息以定位搜索码值为k的数据记录。

以下是三种方式作为索引的数据存储：
1. 数据项k*是一个真正的数据记录。

2. 数据项是一个<k, rid>对，其中rid-list是搜索码值为k的数据记录的记录id.

3. 数据项是一个<k, rid-list>对，其中rid-list是搜索码值为k的数据记录的记录id的列表。

8.2.1 聚簇索引

定义：数据记录的顺序与某一索引的数据项顺序相同或类似，即为聚簇索引，否则就是非聚簇索引。在上述三种索引方式中，使用第一种方式是聚簇索引，而二三种方式的索引只有当数据记录按照搜索码排序时才是聚簇索引，否则，如果数据是任意排列的，仅仅由他们的物理顺序决定的，那么索引上的数据项按照数据记录的顺序排列是没有意义的。

索引为什么可以提高性能:因为可以迅速缩小查找范围！！！

8.3 索引数据结构：

a)基于哈希的索引：

文件中的记录分别放在不同的桶中，其中一个桶由一个主页或由一个主页和多个页构成的链组成。一个记录属于哪个桶可以由一个特殊的函数用于搜索码来决定，这个函数成为哈希函数。给出一个桶号，一个基于哈希的索引结构允许我们一两次I/O就能检索到该桶的主页。

b)基于树的索引：

数据项按照搜索码值进行排列，并且维护一个层次化的搜索数据结构，以便将搜索定向到数据项所属的页面。

非聚簇的哈希索引和树索引提供高速的插入，删除性能，但是处理扫描和有较多匹配结果的范围查询却比较慢。在等值搜索方面，哈希索引要略快一点，但是哈希索引却不支持范围搜索条件的选择。

***** I/O代价的比较：

用B来表示当页中无浪费空间时数据项页的数量，用R来表示每一页的记录数，读或写一个磁盘页的平均时间为D，处理一个记录的平均时间为C，在哈希文件组织中，使用一个函数（哈希函数）将一个记录映射到一组数，而将哈希函数应用于一个记录所需时间为H，对于树索引，用F表示扇出。则有下表：

a)聚簇索引的设计举例：

select E.do

from Employees E

where E.age>40

分析一下在年龄上使用B+树索引，这样的索引是否值得建立，首先依赖于条件的选择性（普及性）。如果实际上每个人都大于40岁的话，这样的索引优势就会很小。假设只有10％的雇员大于40岁，那么这样的索引是否有效呢？答案依赖于索引是否是聚簇的，如果是非聚簇的，每个满足条件的雇员都要花费一次I/O。如果是聚簇的，就只需要扫描10％的I/O了。

select E.dno,count(*)

from Employees E

where E.age>10

Group by E.dno

假设在年龄上有一个B+树索引，对取出的记录在dno上排序，就得到了该查询的结果了。如果几乎所有的雇员都大于10岁，这就不是一个号的执行计划，要是这个索引是非聚簇的，那么这个计划就可能是最糟糕的。

假设在dno上索引是否能满足我们的目标：是用该索引来检索所有记录，按照dno的值进行分组，然后对每一个dno值计算年龄大于10的记录个数（这个策略只需要记录被分组，并不需要记录被排序）。所以该方法的有效性十分依赖于索引是否是聚簇的。如果是非聚簇的，可能对每条记录都要进行一次I/O，这个方案的代价就非常的惊人了。

结论：如果age上的条件不是很有选择性（即符合该条件的记录占总记录数高达80％以上），就应该在dno上建立一个聚簇索引。如果age上的条件很有选择性，就应该考虑在age上建立索引（不必是聚簇的），以迅速缩小查找范围。

聚簇性对于在不包含候选码的搜索码上建立索引也是很重要的。

select E.dno

from Employees E

where E.hobby=‘Stamps‘

如果很多人都集邮，那么通过一个非聚簇索引来检索记录将是十分低效的。即使没有索引（简单的扫描所有记录可能更廉价些），因此，应该考虑hobby上建立一个聚簇索引。

再来看看聚集操作如何影响索引的选择：

select E.dno,count(*)

from Employees E

Group by E.dno

最直接的查询方案：将Employees按照dno进行排序，然后对每一个dno值计算雇员记录的个数。然而，如果有一个dno索引的话，则可以只通过扫描索引而无需扫描记录来回答查询。

b)复合码设计举例

一个复合搜索码支持更广范围的查询，因为它可以和更多条件匹配。

考虑如下查询，要求返回20<age<30且3000<sal<5000的雇员

select E.eid

from Employees E

where E.age between 20 and 30

and E.sal between 3000 and 5000

如果where条件选择性好的话，在<age,sal>或者<sal,age>的复合码对于查询可能有帮助。而且显然这个索引是B+树索引而非哈希索引，因为哈希索引无法回答范围查询。

然后搜索码的顺序有时也回带来很大不同：

select E.eid

from Employees E

where E.age =25

and E.sal between 3000 and 5000

在<age,sal>的B+树索引将拥有良好的性能，因为记录先age排序后sal排序。在<sal,age>上性能就没那么好了，就算两个拥有相同的age值的，也回离得很远。

在处理聚集查询时，复合索引也很有用：

select Avg(E.sal)

from Employees E

where E.age =25

and E.sal between 3000 and 5000

在<age,sal>或<sal,age>的索引，允许仅须扫描索引就可以回答查询。