索引与顺序搜索性能？

Question

说我有一个数据库，其中保存有关书籍及其出版日期的信息。 （两个属性，bookName和publicationDate）。

假设属性publicationDate具有哈希索引。

如果我想显示2010年出版的每一本书，我都会输入此查询：从PublicationDate = 2010的图书中选择bookName。

在我的演讲中，解释说如果有大量数据并且出版日期非常不同，则更优化的方法是使用哈希索引以仅保留2010年出版的书籍。

但是，如果数据库中的绝大多数图书都是在2010年出版的，那么从性能方面来说，最好按顺序搜索数据库。

我真的不明白为什么？在哪些情况下使用索引更优化？为什么？

Answer 1

令人惊讶的是，您在不了解此概念的情况下正在学习哈希索引。哈希索引是一个相当高级的数据库概念。大多数数据库甚至都不支持它们。

尽管该示例具有很大的误导性。 2010不是DATE；这是一年。这很重要，因为哈希索引仅适用于相等比较。因此，从日期获取一年数据的自然方法是：

where publicationDate >= date '2010-01-01' and
      publicationDate < date '2011-01-01'

由于比较不是相等比较，因此无法使用哈希索引。

索引可用于多种用途：

• 为了快速确定哪些行符合过滤条件，因此需要读取的数据页更少。
• 识别具有公共键值的行以进行聚合。
• 匹配表之间的行以进行连接。
• 支持唯一约束（通过唯一索引）。
• 并且对于b树索引，支持order by。

这是第一个目的，它是减少读取的数据页数。读取数据页并非易事，因为需要从磁盘中读取数据页。顺序扫描将读取所有数据页，无论是否需要它们。

如果只有一行符合索引条件，则只需读取一页。那是性能上的一大胜利。但是，如果每个页面都有符合条件的行，则您正在读取所有页面anyway。该索引似乎不太有用。

并且使用索引不是免费的。索引本身需要加载到内存中。在查找操作期间，需要对密钥进行哈希处理。如果您仅扫描页面，那么所有这些开销都是不必要的（尽管还有其他开销需要进行键比较以进行过滤）。

Answer 2

使用索引会降低性能。如果匹配百分比仅占整个表的一小部分，则无需扫描整个表就可以弥补这一成本。但是，如果匹配项的百分比很高，则简单地读取表格会更快。

读取索引会产生成本。较小的，经常使用的索引可能位于内存中，但是较大的或不经常使用的索引可能位于磁盘上。这意味着要访问索引并获取匹配的行号的磁盘访问速度慢。如果查询与少量行匹配，则此开销可以胜过搜索整个表。如果查询匹配大量行，则这种开销很浪费；您仍然必须阅读整个表格。

---

然后有IO成本。 [使用磁盘，顺序读取和写入要比随机读取要快得多。我们的通话速度提高了10到100倍。

旋转的磁盘有一个物理部分，即磁头，它必须四处移动以读取磁盘的不同部分。移动所需的时间称为“搜索时间”。当您在表中的各行之间跳来跳去时（可能是乱序），该值为random access，并会导致寻找时间。相比之下，读取整个表很可能是长时间连续读取。头部不必跳来跳去，没有寻找时间。

SSD快很多，没有物理部分可移动，但它们仍然是much faster for sequential access than random。

此外，操作系统和磁盘之间的随机访问会增加开销；它需要更多说明。

因此，如果数据库确定查询将要匹配表的大多数行，则可以决定顺序读取它们并清除不匹配项要比通过索引查找行和使用较慢的行更快。随机访问。

---

考虑一堆邮政信箱，每个信箱都用大网格编号。按数字查找每个框相当快，但是从框开始并按顺序打开它们要快得多。而且我们有谁拥有哪个盒子以及它们住在哪里的索引。

您需要获得South Northport的邮件。您可以在索引中查找哪些箱子属于South Northport的某人，发现只有少数箱子，然后逐个抓取邮件。那是一个索引查询和随机访问。因为只有几个邮箱要检查，所以速度很快。

现在，我请您为所有人寄信。[[但是南诺斯波特。您可以反向使用索引：获取South Northport的箱子列表，从每个箱子的列表中减去它们，然后分别获取每个箱子的邮件。但这将是缓慢的随机访问。相反，由于您将不得不打开几乎每个盒子，因此按顺序检查每个盒子并查看是否是寄给南诺斯波特的邮件更快。

---

更正式地说，索引与表扫描的性能类似。

# Indexed query
C[index] + (C[random] * M)

# Full table scan
(C[sequential] + C[match]) * N

C是各种不变成本（或接近足够的常数），M是匹配的行数，N是表中的行数。
我们知道C[sequential]比C[random]快10到100倍。因为磁盘访问比CPU或内存操作慢得多，所以与C[match]相比，C[sequential]（检查行是否匹配的成本）将相对较小。更正式...
C[random] >> C[sequential] >> C[match]

使用C[sequential] + C[match]为C[sequential]。
# Indexed query
C[index] + (C[random] * M)

# Full table scan
C[sequential] * N

[当M << N时，索引查询获胜。当M接近N时，全表扫描获胜。
请注意，使用索引的成本并不是真正恒定的。 C[index]是诸如加载索引，查找键以及读取行ID之类的事情。根据索引的大小，索引的类型以及它是在磁盘上（冷）还是在内存中（热），这可能会变化很大。这就是为什么在初次启动数据库服务器时前几个查询通常比较慢的原因。
在现实世界中，要复杂得多。实际上，行被分解为data pages，数据库具有许多技巧来优化查询和磁盘访问。但是，通常，如果要匹配大多数行，则全表扫描将胜过索引查找。
如今，哈希索引的使用受到限制。这是一个简单的键/值对，只能用于相等性检查。大多数数据库使用B-Tree作为其标准索引。它们的成本更高一些，但可以处理更广泛的操作，包括相等性，范围，比较和前缀搜索，例如like 'foo%'。
Postgres Index Types documentation很好地概括了索引类型的各种优缺点。