什么是数据库索引？

Question

我从大约18个月前开始在技术领域工作以来就听说过它们。我知道它们有可能提高性能，并且它们似乎是列特定的--（“我们在 date_of_birth 列上索引 User 表”）。

只想快速了解它们究竟是什么，用于什么，以及它们如何工作。

- Clay Wardell

Answer 1

我已经写了一本完整的书籍！它也可以在网上免费获取：http://use-the-index-luke.com/

我试着简短地回答你的问题——这并不是我的强项。上次我尝试回答，结果写了一本书……

像表格一样，索引由行和列组成，但是以逻辑排序的方式存储数据，以提高搜索性能。可以把它想象成电话簿（印刷版）。它们通常按照last_name、first_name和其他可能的标准（例如邮政编码）进行排序。这种排序使得快速查找特定姓氏的所有条目成为可能。如果你也知道名字，甚至可以很快地找到姓和名的组合的条目。

然而，如果你只知道名字，电话簿就不会真正帮助你。多列数据库索引也是如此。因此，是的，索引可以潜在地提高搜索性能。如果你对于你的问题使用了错误的索引（例如在搜索名字时使用电话簿），那么它们可能是无用的。

你可以在同一张表上的不同列上创建多个索引。因此，对last_name，first_name创建的索引与仅对first_name创建的索引是不同的（这将优化按名字搜索的操作）。

索引保存冗余数据（例如：聚集索引 = 电话簿）。它们具有表中存储的相同信息（例如：基于函数的索引），但以排序方式呈现。每次执行写入操作（插入/更新/删除）时，数据库会自动维护此冗余。因此，索引会降低写入性能。

除了快速查找数据外，索引还可用于优化排序操作（order by）并将相关数据物理上紧密排列在一起（聚簇）。

要更好地了解，请查看我的书的完整目录：http://use-the-index-luke.com/sql/table-of-contents。

- Markus Winand

---

你完全忽略了有时索引被用于强制实现多列唯一性约束这一点。 - horseyguy

Answer 2

将其视为表格的目录。如果它存在，数据库就知道在哪里查找更具体的内容。如果不存在，则数据库必须搜索所有数据才能找到它。

可以在此维基百科文章中找到更详细的解释。

- Bjoern

Answer 3

一个数据库索引是旨在改善查找操作时间复杂度的数据结构。

没有索引的查找最坏情况下具有O（N）的复杂度。借助索引实现高效查找可以达到对数级别的O（log（N））甚至是一些架构上的O（1）复杂度。

数据库索引还可以强制执行数据库约束。许多数据库系统对一组列设置称为“PRIMARY KEY”的索引。某些数据库系统要求“FOREIGN KEY”中的列被索引，以加快操作（插入，更新）。

- kiriloff

---

非平凡的查找永远不可能真正达到O(1)。最多只能将一个O(log(N))的过程“隐藏”在一个沉重的O(1)过程下，直到某个点。 - Hot Licks

如果查询字段是索引字段，并且使用哈希索引进行相等（WHERE）查询，则可以实现O(1)，这听起来正确吗？ - kiriloff

然而：根据PostgreSQL文档，哈希索引操作目前不支持WAL日志记录，因此在数据库崩溃后可能需要使用REINDEX重建哈希索引。它们也无法通过流式复制或基于文件的复制进行复制。出于这些原因，目前不建议使用哈希索引。 - kiriloff

最终哈希表的时间复杂度是O(log(N))，因为存储空间是O(log(N))。只是如果你固定了存储大小，它看起来像是O(1)。 - Hot Licks

Answer 4

索引是一个可选的结构，与表或表集群相关联，有时可以加快数据访问速度。通过在表的一个或多个列上创建索引，在某些情况下，您可以从表中检索到一小组随机分布的行。索引是减少磁盘I/O的众多手段之一。

如果堆组织表没有索引，则数据库必须执行完整的表扫描来查找值。例如，没有索引，对hr.departments表中位置2700的查询需要数据库搜索每个表块中的每一行以查找此值。随着数据量的增加，这种方法无法很好地扩展。

参考链接：http://docs.oracle.com/cd/E11882_01/server.112/e10713/indexiot.htm

- Pamma

Answer 5

我知道数据库索引可以潜在地提高性能。

没错，但请记住，有时候索引也会导致性能不佳。例如：给数据库的所有列都建立索引无疑会严重影响性能。

这里有一个类似的讨论：这里，你可以查阅一下，可能会有所帮助。

- Mayukh Roy