数据存储

DBMS把数据存储到文件中。最常见的存储结构是按行存储，其中文件被分成一个一个“块”(block)。每个块包含一组元组(tuple)。DBMS每次读取都一次读一个整块。

上图中，我们有4个数据库块，每个块有2个元组。

数据文件的类型

DBMS把数据存储到文件中。而文件分为2种类型，heap file（堆型文件）和sequential file(序列型文件)。heap file是无序的。sequential file是有序的，它根据一些被称作key的属性排序。（注意这里key跟primary key不是一个概念）。

索引

索引(index)是除数据文件之外，一种额外的文件。在给出一个搜索词之后，它能使你快速访问数据文件中的记录。

索引包含键值对：键(key)是一个属性值（如studentID or name）；值(value)是指向记录的指针。

一个表可以有多个索引。

这里,key（键），代表搜索词。

索引组织

有几种不同的索引组织方式：

1， B+ trees（最流行）。他们是搜索树。

2， Hash table

3， 专门的索引(specialized indexes): bit maps, R-trees, inverted index

B+ trees 索引

Hash table 索引

聚集索引和非聚集索引

对比

聚集索引和非聚集索引：

聚集索引：那些离得近的索引的记录，它们的数据离得也近。

非聚集索引：那些离得近的索引的记录，它们的数据也可能离得远。

查找数据文件

由于硬盘是一种物理设备，它的速度取决于硬盘旋转的速度，所以顺序访问比随机访问速度要快很多。

• 快的访问：读取块 1, 2, 3, 4, 5,…

• 慢的访问：读取块 2342, 11, 321, 9, …

定律：随机访问1-2%的数据文件等于顺序访问整个文件的速度。

选择索引

索引选择问题是对于一个数据查询很重的应用，你要决定创建哪些索引，不创建哪些索引。这可由数据库管理员(DBA)决定，或者由半自动化工具生成。

决定搜索词

让一些属性成为搜索词，如果WHERE子句包含：

• 一个精确的匹配
• 一个范围匹配
• 一个join on 对应属性

例子

数据schema： V(M, N, P); 索引： INDEX I1 on V(M)

1，

SELECT * FROM V WHERE V.M = 33

不走索引的查询：

查找 V
对于每个记录：
  如果M=33，则输出

走索引的查询

在索引I1中寻找key=33
对于每个记录，输出

2，

SELECT * FROM V WHERE V.M = 33 and V.P = 55

不走索引的查询：

搜索V
对于每个记录
如果M=33且P=55，则输出

走索引的查询

在索引I1中寻找key=33
对于每个记录，如果P=55
  则输出

选择索引的原则

1， 考虑缩短那些工作量大的频繁的查询的时间。

2， Consider relations accessed by query – No point indexing other relations

3， 查看WHERE子句，找可能的search key。

4， 试着找那些能提高多个查询速度的索引。

是否使用聚集

范围查询从聚集(clustering)索引上得到好处最多。

Covering indexes 不需要聚集，它和非聚集的效果是一样的。