下载
第4章 索 引 结 构
前面介绍了表示记录的几种可选方式，现在我们需要考虑整个关系或类外延如何表示。仅
仅把关系中的元组或类外延中的对象随机分散到各存储块中是不够的。为了说明这一点，我们
来看一看怎样回答哪怕是像 SELECT * FROM R这样最简单的查询。我们将不得不检索存储器
中的每个存储块，并且还得依赖于：
1) 块首部中存在足够的信息来标明该块中记录从什么地方开始。
2) 记录首部中存在足够的信息来说明该记录属于哪个关系。
一个稍好的记录组织方式是为给定的关系预留一些块甚至几个完整的柱面。我们可以认为
这些柱面上所有存储块中都存放表示该关系中元组的记录。现在，我们至少不需要扫描整个存
储器就能找到该关系的所有元组。
然而，这种组织方式却无助于回答下面这个简单查询：“找出给定主键值的元组”。举例来
说，n a m e是图3 - 1 所示关系M o v i e S t a r的主键。像
这样的查询需要扫描可能存放有 M o v i e S t a r元组的所有存储块。为了便于实现类似查询，
通常给关系建立一个或多个索引。如图 4 - 1 所示，索引是这样一种数据结构：它以记录的特征
（通常是一个或多个字段的值）为输入，并能“快速地”找出具有该特征的记录。具体来说，索
引使我们只需查看所有可能记录中的一小部分就能找到所需记录。建立索引的字段（组合）称
为查找键，在索引不言而喻时也可称“键”。
图4-1 索引以某个（或某些）字段值为输入并找出对应字段值符合要求的记录
对应的
记录
包含记
录的块
索引
值
