一、稠密索引

如果记录是排好序的，我们就可以在记录上建立稠密索引，它是这样一系列存储块：块中只存放记录的键以及指向记录本身的指针，指针就是一个指向记录或存储块地址。稠密索引文件中的索引块保持键的顺序与文件中的排序顺序一致。既然我们假定查找键和指针所占存储空间远小于记录本身，我们就可以认为存储索引文件比存储数据文件所需存储块要少得多。当内存容纳不下数据文件，但能容纳下索引文件时，索引的优势尤为明显。这时，通过使用索引文件，我们每次查询只用一次I/O操作就能找到给定键值的记录。
  www.2cto.com  

下图所示为一个建立在顺序文件上的稠密索引。

图1 顺序文件（右）上的稠密索引（左）

第一个索引块存放指向前四个记录的指针，第二个索引块存放指向接下来的四个记录的指针，依此类推。

稠密索引支持按给定键值查找相应记录的查询。给定一个键值K，我们先在索引块中查找K。当找到K后，我们按照K所对应的指针到数据文件中找到相应的记录。似乎在找到K之前我们需要检索索引文件的每个存储块，或平均一半的存储块。然而，由于有下面几个因素，基于索引的查找比它看起来更为有效：
 

1.索引块数量通常比数据块数量少。

2.由于键被排序，我们可以使用二分查找法来查找K。若有n个索引块，我们只需查找log2n个块。

3.索引文件可能足够小，以至可以永久地存放在主存缓冲区中。要是这样的话，查找键K时就只涉及主存访问而不需执行I/O操作。
 

二、稀疏索引

稀疏索引只为数据文件的每个存储块设一个键-指针对,它比稠密索引节省了更多的存储空间，但查找给定值的记录需更多的时间。只有当数据文件是按照某个查找键排序时，在该查找键上建立的稀疏索引才能被使用，而稠密索引则可以应用在任何的查找键。如图2所示，稀疏索引只为每个存储块设一个键-指针对。键值是每个数据块中第一个记录的对应值。

图2 顺序文件上的稀疏索引

同图1实例一样，我们假定数据文件已排序，且其键值为连续的10的倍数，直至某个较大的数。我们还继续假定每个存储块可存放四个键-指针对。这样，第一个索引存储块中为前四个数据存储块的第一个键值的索引项，它们分别是10、30、50和70。按照前面假定的键值模式，第二个索引存储块中为第五至第八个数据存储块的第一个键值的索引项，它们分别是90、110、130和150。图中我们还列出第三个索引存储块存放的键值，它们分别是假设的第九至第十二个数据存储块的第一个键值。
  www.2cto.com  

在已有稀疏索引的情况下，要找出查找键值为K的记录，我们得在索引中查找到键值小于或等于K的最大键值。由于索引文件已按键排序，我们可以使用二分查找法来定位这个索引项，然后根据它的指针找到相应的数据块。现在我们必须搜索这个数据块以找到键值为K的记录。当然，数据块中必须有足够的格式化信息来标明其中的记录及记录内容，可以采用2.5节和2.7节中的任何技术。

来自为知笔记(Wiz)