我对数据库还比较陌生，但已经了解到在需要搜索的字段上添加索引可以极大地加快搜索时间。我明白这个道理，但想知道它是如何实现的。我在这个问题上进行了一些搜索，但没有找到任何好的、简洁明了且不过度技术化的答案。
我读过一篇类比，描述它就像书后索引，但在数据字段中包含唯一元素（例如用户数据库中的电子邮件地址）的情况下，使用书后索引的类比会提供与非索引搜索相同的线性查找时间。
那么究竟发生了什么，才能如此大大加快搜索时间呢？我读了一些关于使用B+树进行搜索的内容，但这些描述都有点太深入了。我所寻求的是一个高层次的概述，帮助我概念上理解它，而不是技术细节。
扩展搜索算法的效率，数据库性能的一个关键领域是数据访问的速度。通常情况下，从磁盘读取数据要比从内存中读取数据慢得多。
为了说明这一点，假设所有数据都存储在磁盘上。如果您需要搜索表中每一行数据以查找某个字段中的特定值，则仍然需要从磁盘读取整行数据以查看是否匹配 - 这通常被称为“表扫描”。
如果您的表是100MB，那么您需要从磁盘中读取100MB的数据。
现在，如果您对要搜索的列创建索引，简单来说，索引将存储数据的每个唯一值以及相应完整行数据的确切位置的引用。现在，相对于整个表的100MB，此索引可能仅为10MB。
从磁盘中读取10MB的数据（并可能稍微多读一些以读取每个匹配项的完整行数据）大约比读取100MB快10倍。
不同的数据库将以不同的方式将索引或数据存储在内存中，以使这些操作更快。然而，如果您的数据集很大，并且不适合内存，则磁盘速度可能会产生巨大影响，并且索引可以显示出巨大的收益。在内存中，仍然可以获得很大的性能提升（以及其他方面的效率）。
通常来说，这就是为什么您可能不会注意到对小型数据集创建索引的任何实质性差异，因为它们很容易适合内存。
虽然系统的基础细节会有所不同，但我一直认为磁盘读取与内存读取是一个容易理解的说明方式。
好的，经过一番研究和讨论，我学到了以下内容：
从概念上讲，索引是数据字段的排序副本，其中每个索引值指向其原始（未排序）行。因为数据库知道值的排序方式，所以它可以应用比仅从头到尾查找更复杂的搜索算法。二分查找算法是已排序列表的简单示例搜索算法，并将最大搜索时间从O(n)减少到O(log n)。
顺带一提：一个不错的排序算法通常需要O(n log n)完成，这意味着（正如我们可能听说过的那样），你应该只在经常搜索的字段上放置索引，因为添加索引（包括排序）比进行几次完整搜索更加昂贵。例如，在一个大于1,000,000条目的大型数据库中，排序比一次搜索多20倍左右的成本。
编辑： 请参考@Jarod Elliott的答案，对于从磁盘读取操作的搜索效率有更深入的了解。
