稠密索引与稀疏索引

稀疏索引

索引项中只对应主文件中的部分记录，即不会给每条记录建立索引。

稀疏索引要求索引字段选自于主文件中的有序属性(即属性值是按照递增排序的)，如上图所示，索引字段选自于公寓名称，而公寓名称是按照字母进行排序的。

查询方式

如果要查找某条记录K，先从索引表找，如果未找到，则找相邻的小于K的最大索引字段值对应的索引项，然后从该索引项对应的记录开始顺序进行Table检索。拿上图来说，我们要找Donwtown所在的记录，但是在索引表中未找到对应的索引项，那么我们已知比Downtown小的是Brighton，我们可以从Brighton对应的记录开始查询，这样就提高了查询效率。

稠密索引

对于主文件中每一条记录都有索引项与之对应，因此有可能一个索引项会对应多个记录。

稠密索引分为以下三种：

候选键属性的稠密索引

因为使用候选键作为索引字段，所以稠密索引很好建立

属性值可重复的稠密索引

• 第一种是要求索引字段值不能重复，主文件记录按搜索码排序

由于索引字段值不能重复，但选取的属性可重复取相同的值，所以要求主文件中的记录需要排序。当我们从索引中找到对应的记录后，再从主文件中按顺序查找，就可以找到想要的记录了。

• 第二种是要求搜索字段不能重复，主文件记录无序

如同所示引入指针桶，先通过索引找到对应的指针桶，然后从指针桶找对应的记录。