Dense vs. Sparse Indexes

英文原文 Dense vs. Sparse Indexes (opens in a new tab)

数据库索引的一个质量指标是它是稀疏（sparse）的还是密集（dense）的。每一个这种索引的质量指标都有它们自己的权衡，我们看一下使用下面这些用户数据时，每一种索引类型是如何工作的。

这是一个非常基础的包含四列的表，对于这个例子来说，这个表占用了四个 数据页，每个页包含四行数据。我们以 first_name 列的索引为例，先来看看密集索引：

我们可以看到表中每一个 first_name 字段都有一个索引项。如果我们以 Rachelle 来查询 first_name，我们需要在索引上执行一个二分查找，然后读取数据的位置。相反，稀疏索引质保函某些表行的记录。

我们可以看到，我们的稀疏索引只有四条记录（每一页一条）。现在，如果我们希望查找 Rachelle 所在的行，我们可以在我们的索引上执行二分查找来找到它在 Loyd 和 Shepherd 之间，之后根据这些边界，我们从 Loyd 所在的页开始扫描，直到找到 Rachelle的行。注意，本例中右侧的数据是有序的。这种有序是稀疏索引的一个限制，它需要数据是有序的，否则将无法实现扫描。

结论

在写入时，密集索引比稀疏索引的维护代价更高，因为每一行都必须有一个记录，数据库必须在插入，更新和删除时都维护索引。每一行都有一条索引记录也意味着密集索引需要更多的内存。它的优点是仅通过二分查找就可以快速的查找到值。它对数据的顺序也没有什么要求。

在写入数据时，因为值包含了部分值，稀疏索引比密集索引的维护代价更小。这种轻量的维护成本意味着插入，更新和删除也会更快。索引记录条数更少意味着内存占用更少。因为二分查找后需要跨页扫描数据，因此速度会慢一些。稀疏索引只有的数据是有序的时候才能使用。