我是数据库新手，并且一直在阅读向需要搜索的字段添加索引可以显着加快搜索时间。我理解这个现实，但很好奇它实际上是如何工作的。我已经对这个主题进行了一些搜索，但没有找到任何好的、简洁的、而不是关于它如何工作的技术性答案。
我读过它类似于书后的索引的类比，但是对于唯一元素的数据字段（例如用户数据库中的电子邮件地址），使用书后类比将提供与非索引搜索相同的线性查找时间。
这里发生了什么来加快搜索时间？我已经阅读了一些关于使用B+-Trees进行搜索的内容，但是描述有点太深入了。我正在寻找的是对正在发生的事情的高级概述，以帮助我从概念上理解它，而不是技术细节。
扩展搜索算法的效率，数据库性能的一个关键领域是访问数据的速度。一般来说，从磁盘读取数据比从内存读取数据慢很多。
为了说明这一点，让我们假设所有内容都存储在磁盘上。如果您需要在表中的每一行数据中搜索某个字段中的某些值，您仍然需要从磁盘中读取整行数据以查看是否匹配——这通常称为“表扫描” '。
如果您的表是 100MB，那么您需要从磁盘读取 100MB。
如果您现在对要搜索的列进行索引，简单来说，索引将存储数据的每个唯一值以及对相应整行数据的确切位置的引用。与整个表的 100MB 相比，该索引现在可能只有 10MB。
从磁盘读取 10MB 的数据（读取每个匹配的完整行数据可能需要多一点）比读取 100MB 快大约 10 倍。
不同的数据库将以不同的方式将索引或数据存储在内存中，以使这些事情变得更快。但是，如果您的数据集很大并且不适合内存，那么磁盘速度会产生巨大的影响，而索引可以显示出巨大的收益。在内存中仍然可以有很大的性能提升（以及其他效率）。
一般来说，这就是为什么你可能不会注意到索引一个很容易放入内存的小数据集有任何明显的区别。
底层细节会因系统而异，实际上会复杂得多，但我一直发现磁盘读取与内存读取是一种易于理解的解释方式。
好的，经过一番研究和讨论，这是我学到的：
从概念上讲，索引是它正在索引的数据字段的排序副本，其中每个索引值都指向它的原始（未排序）行。因为数据库知道值是如何排序的，所以它可以应用更复杂的搜索算法，而不仅仅是从头到尾查找值。二进制搜索算法是排序列表搜索算法的一个简单示例，它将最大搜索时间从O(n)减少到O(log n)。
附带说明：一个体面的排序算法通常需要O(n log n)才能完成，这意味着（正如我们之前可能听说过的）你应该只在你经常搜索的字段上放置索引，因为它有点多添加索引（包括排序）比进行几次完整搜索要昂贵。例如，在超过 1,000,000 个条目的大型数据库中，排序的成本比搜索一次的成本高 20 倍。
编辑：请参阅@Jarod Elliott 的答案，以更深入地了解搜索效率，特别是关于从磁盘操作读取。
继续您的书后类比，如果页面按该元素排序，则查找时间与非索引搜索相同，是的。
但是，如果您的书是按作者排序的书评列表，但您只知道 ISBN，该怎么办。ISBN 是独一无二的，是的，但您仍然需要扫描每条评论才能找到您正在寻找的评论。
现在，在书的后面添加一个索引，按 ISBN 排序。繁荣，快速的搜索时间。这类似于数据库索引，从索引键 (ISBN) 到实际数据行（在本例中为您的书的页码）。