SQLite 中的大多数表由零个或多个行组成，这些行具有唯一的整数键（rowid或INTEGER PRIMARY KEY），后跟内容。（WITHOUT ROWID表除外。）这些行在逻辑上按 rowid 递增的顺序存储。例如，本文使用名为“FruitsForSale”的表，该表将各种水果与其种植所在的州及其市场单价相关联。架构是这样的：

CREATE TABLE FruitsForSale(
  Fruit TEXT,
  State TEXT,
  Price REAL
);

对于一些（任意）数据，这样的表可能逻辑上存储在磁盘上，如图 1 所示：

图 1：表“FruitsForSale”的逻辑布局

在此示例中，rowid 不是连续的，而是有序的。SQLite 通常创建从 1 开始的 rowids，并随着每添加一行而增加 1。但是，如果删除行，序列中可能会出现间隙。如果需要，应用程序可以控制分配的 rowid，这样行就不一定插入到底部。但无论发生什么，rowid 始终是唯一的并且严格按升序排列。

假设您想查询桃子的价格。查询如下：

SELECT price FROM fruitsforsale WHERE fruit='Peach';

为了满足这个查询，SQLite 从表中读取每一行，检查“fruit”列是否具有“Peach”的值，如果是，则从该行输出“price”列。下面的图 2说明了该过程。这种算法称为全表扫描 ，因为必须读取和检查表的全部内容才能找到感兴趣的一行。对于只有 7 行的表，全表扫描是可以接受的，但如果表包含 700 万行，则全表扫描可能会读取数兆字节的内容才能找到一个 8 字节的数字。出于这个原因，人们通常会尽量避免全表扫描。

图 2：全表扫描

1.2. 按 Rowid 查找

避免全表扫描的一种技术是按 rowid（或等效的INTEGER PRIMARY KEY）进行查找。要查找桃子的价格，可以查询 rowid 为 4 的条目：

SELECT price FROM fruitsforsale WHERE rowid=4;

由于信息以 rowid 顺序存储在表中，SQLite 可以使用二进制搜索找到正确的行。如果表包含 N 个元素，则查找所需行所需的时间与 logN 成正比，而不是像在全表扫描中那样与 N 成正比。如果该表包含 1000 万个元素，则意味着查询的速度将达到 N/logN 的数量级或大约快 100 万倍。

图 3：按 Rowid 查找

1.3. 按索引查找

通过 rowid 查找信息的问题是您可能不关心“第 4 项”的价格是多少——您想知道桃子的价格。所以 rowid 查找没有帮助。

为了使原始查询更有效率，我们可以在“fruitsforsale”表的“fruit”列上添加一个索引，如下所示：

CREATE INDEX Idx1 ON fruitsforsale(fruit);

索引是另一个类似于原始“fruitsforsale”表的表，但内容（在本例中为 fruit 列）存储在 rowid 之前，并且所有行都按内容顺序排列。图 4给出了 Idx1 索引的逻辑视图。“fruit”列是用于对表的元素进行排序的主键，“rowid”是用于在两行或更多行具有相同“fruit”时打破平局的辅助键。在示例中，rowid 必须用作“橙色”行的决胜局。请注意，由于 rowid 在原始表的所有元素中始终是唯一的，因此“fruit”后跟“rowid”的复合键在索引的所有元素中都是唯一的。

图 4：水果栏上的索引

这个新索引可用于为原始“桃子价格”查询实施更快的算法。

SELECT price FROM fruitsforsale WHERE fruit='Peach';

查询首先在 Idx1 索引上执行二进制搜索，以查找具有 fruit='Peach' 的条目。SQLite 可以在 Idx1 索引上执行此二进制搜索，但不能在原始 FruitsForSale 表上执行此二进制搜索，因为 Idx1 中的行按“水果”列排序。在 Idx1 索引中找到包含 fruit='Peach' 的行后，数据库引擎可以提取该行的 rowid。然后，数据库引擎对原始 FruitsForSale 表进行第二次二分搜索，以找到包含 fruit='Peach' 的原始行。从 FruitsForSale 表的行中，SQLite 可以提取价格列的值。这个过程如图 5 所示。

图 5：桃子价格的索引查找

SQLite 必须使用上面显示的方法进行两次二进制搜索才能找到桃子的价格。但是对于行数很多的表，这还是比做全表扫描要快很多。

1.4. 多个结果行

在前面的查询中，fruit='Peach' 约束将结果缩小到单行。但即使获得多行，同样的技术也能奏效。假设我们查询的是橙子而不是桃子的价格：

SELECT price FROM fruitsforsale WHERE fruit='Orange'

图 6：橙子价格的索引查找

在这种情况下，SQLite 仍然执行单个二分查找以找到索引的第一个条目，其中 fruit='Orange'。然后它从索引中提取 rowid 并使用该 rowid 通过二进制搜索查找原始表条目并从原始表中输出价格。但是数据库引擎并没有退出，而是前进到索引的下一行，为下一个 fruit='Orange' 条目重复该过程。前进到索引（或表）的下一行比执行二进制搜索的成本要低得多，因为下一行通常与当前行位于同一数据库页面上。事实上，与二分查找相比，前进到下一行的成本非常低，以至于我们通常会忽略它。所以我们估计这个查询的总成本是 3 次二进制搜索。

1.5. 多个 AND 连接的 WHERE 子句项

接下来，假设您不仅要查找任何橙子的价格，而且要查找加州产橙子的价格。适当的查询如下：

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA'

图 7：加州橙子的索引查找

此查询的一种方法是使用 WHERE 子句的 fruit='Orange' 项来查找所有与橙子有关的行，然后通过拒绝来自加利福尼亚以外的州的任何行来过滤这些行。这个过程如上面的图 7所示。在大多数情况下，这是一种完全合理的方法。是的，数据库引擎确实必须对后来被拒绝的佛罗里达橙色行进行额外的二进制搜索，因此它没有我们希望的那样高效，尽管对于许多应用程序来说它已经足够高效了。

假设除了“fruit”索引之外，还有一个“state”索引。

CREATE INDEX Idx2 ON fruitsforsale(state);

图 8：状态列上的索引

“state”索引的工作方式与“fruit”索引一样，因为它是一个新表，在 rowid 前面有一个额外的列，并按该额外列作为主键进行排序。唯一的区别是在 Idx2 中，第一列是“state”而不是 Idx1 中的“fruit”。在我们的示例数据集中，“状态”列中有更多冗余，因此它们是更多重复条目。仍然使用 rowid 解析关系。

使用“state”上的新 Idx2 索引，SQLite 有另一个选项来查找加州橙子的价格：它可以查找包含来自加州的水果的每一行并过滤掉那些不是橙子的行。

图 9：加州橙子的索引查找

使用 Idx2 而不是 Idx1 会导致 SQLite 检查一组不同的行，但最终会得到相同的答案（这非常重要 - 请记住索引永远不会改变答案，只会帮助 SQLite 更快地找到答案）并且它做相同数量的工作。所以 Idx2 索引在这种情况下对性能没有帮助。

在我们的示例中，最后两个查询花费的时间相同。那么SQLite会选择Idx1还是Idx2哪个索引呢？如果在数据库上运行了 ANALYZE命令，那么 SQLite 就有机会收集有关可用索引的统计信息，那么 SQLite 就会知道 Idx1 索引通常会将搜索范围缩小到单个项目（我们的示例 fruit=' Orange' 是该规则的例外），而 Idx2 索引通常只会将搜索范围缩小到两行。因此，如果其他条件相同，SQLite 将选择 Idx1，希望将搜索范围缩小到尽可能少的行数。由于ANALYZE提供的统计数据，这种选择才有可能。如果分析尚未运行，那么选择使用哪个索引是任意的。

1.6. 多列索引

要从 WHERE 子句中具有多个 AND 连接项的查询中获得最大性能，您确实需要一个多列索引，其中包含用于每个 AND 项的列。在这种情况下，我们在 FruitsForSale 的“fruit”和“state”列上创建一个新索引：

CREATE INDEX Idx3 ON FruitsForSale(fruit, state);

图 1：两列索引

多列索引遵循与单列索引相同的模式；索引列添加在 rowid 的前面。唯一的区别是现在添加了多个列。最左边的列是用于对索引中的行进行排序的主键。第二列用于打破最左侧列中的平局。如果有第三列，它将用于打破前两列的平局。对于索引中的所有列，依此类推。因为 rowid 保证是唯一的，所以索引的每一行都是唯一的，即使两行的所有内容列都相同。这种情况不会发生在我们的示例数据中，但有一种情况 (fruit='Orange')，其中第一列上有平局，必须由第二列打破。

鉴于新的多列 Idx3 索引，SQLite 现在可以仅使用 2 个二进制搜索来查找加州橙子的价格：

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA'

图 11：使用两列索引进行查找

通过 WHERE 子句约束的两列上的 Idx3 索引，SQLite 可以对 Idx3 进行一次二进制搜索以找到加州橙子的一个 rowid，然后进行一次二进制搜索以在原始表中查找该项目的价格. 没有死胡同，也没有浪费的二进制搜索。这是一个更高效的查询。

请注意， Idx3 包含与原始Idx1 相同的所有信息。所以如果我们有 Idx3，我们就不再需要 Idx1 了。通过简单地忽略 Idx3 的“状态”列，可以使用 Idx3 满足“桃子价格”查询：

SELECT price FROM fruitsforsale WHERE fruit='Peach'

图 12：多列索引上的单列查找

因此，一个好的经验法则是您的数据库模式永远不应包含两个索引，其中一个索引是另一个索引的前缀。删除列数较少的索引。SQLite 仍然能够使用更长的索引进行高效查找。

1.7. 覆盖指数

通过使用两列索引，“加利福尼亚橘子的价格”查询变得更加高效。但是 SQLite 可以使用还包括“价格”列的三列索引做得更好：

CREATE INDEX Idx4 ON FruitsForSale(fruit, state, price);

图 13：覆盖索引

这个新索引包含查询使用的原始 FruitsForSale 表的所有列 - 包括搜索词和输出。我们称之为“覆盖索引”。因为所有需要的信息都在覆盖索引中，SQLite 永远不需要查阅原始表来找到价格。

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA';

图 14：使用覆盖索引进行查询

因此，通过在索引末尾添加额外的“输出”列，可以避免必须引用原始表，从而将查询的二进制搜索次数减少一半。这是性能的常数因子改进（大约是速度的两倍）。但另一方面，它也只是一种提炼；两倍的性能提升并不像首次为表建立索引时的一百万倍那样显着。对于大多数查询，不太可能注意到 1 微秒和 2 微秒之间的差异。

1.8. WHERE 子句中的 OR 关联项

多列索引仅在查询的 WHERE 子句中的约束条件由 AND 连接时才有效。因此，当搜索既是橘子又是在加利福尼亚种植的商品时，Idx3 和 Idx4 很有用，但如果我们想要所有既是橘子又是在加利福尼亚种植的商品，这两个索引都不会那么有用。

SELECT price FROM FruitsForSale WHERE fruit='Orange' OR state='CA';

当在 WHERE 子句中遇到 OR 连接的术语时，SQLite 会分别检查每个 OR 术语并尝试使用索引来查找与每个术语关联的 rowid。然后它使用生成的 rowid 集的并集来找到最终结果。下图说明了这个过程：

图 15：使用 OR 约束的查询

上图暗示 SQLite 首先计算所有的 rowid，然后在开始对原始表进行 rowid 查找之前将它们与联合操作结合起来。实际上，rowid 查找穿插在 rowid 计算中。SQLite 一次使用一个索引来查找 rowid，同时记住它之前看到的 rowid 以避免重复。不过，这只是一个实现细节。该图虽然不是 100% 准确，但很好地概述了正在发生的事情。

为了使上面显示的 OR-by-UNION 技术有用，必须有一个可用的索引来帮助解析 WHERE 子句中的每个 OR 连接项。如果即使是单个 OR 连接词没有被索引，那么就必须进行全表扫描才能找到由一个词生成的 rowid，如果 SQLite 必须进行全表扫描，它也可以这样做它在原始表上并一次获得所有结果，而不必混淆联合操作和后续二进制搜索。

人们可以看到，通过使用相交运算符代替并集，还可以如何利用 OR-by-UNION 技术在 WHERE 子句具有由 AND 连接的术语的查询中使用多个索引。许多 SQL 数据库引擎都可以做到这一点。但是与仅使用单个索引相比，性能提升很小，因此 SQLite 目前没有实现该技术。但是，未来版本的 SQLite 可能会得到增强以支持 AND-by-INTERSECT。

2.排序

除了加速查找之外，SQLite（与所有其他 SQL 数据库引擎一样）也可以使用索引来满足查询中的 ORDER BY 子句。换句话说，索引可以用来加速排序和搜索。

当没有合适的索引可用时，带有 ORDER BY 子句的查询必须作为一个单独的步骤进行排序。考虑这个查询：

SELECT * FROM fruitsforsale ORDER BY fruit;

SQLite 通过收集查询的所有输出然后通过排序器运行该输出来处理此问题。

图 16：没有索引的排序

如果输出行数为 K，则排序所需的时间与 KlogK 成正比。如果 K 很小，排序时间通常不是一个因素，但是在上面 K==N 的查询中，排序所需的时间可能比进行全表扫描所需的时间长得多。此外，整个输出都累积在临时存储中（可能在主内存中或磁盘上，具体取决于各种编译时和运行时设置），这可能意味着需要大量临时存储才能完成查询。

2.1. 按 Rowid 排序

因为排序可能很昂贵，所以 SQLite 努力将 ORDER BY 子句转换为空操作。如果 SQLite 确定输出将自然地按指定的顺序出现，则不进行排序。因此，例如，如果您请求按 rowid 顺序输出，则不会进行排序：

SELECT * FROM fruitsforsale ORDER BY rowid;

图 17：按 Rowid 排序

您还可以像这样请求逆序排序：

SELECT * FROM fruitsforsale ORDER BY rowid DESC;

SQLite 仍然会省略排序步骤。但是为了使输出以正确的顺序出现，SQLite 将从末尾开始进行表扫描，而不是从头开始并向末尾扫描，如图 17所示。

2.2. 按索引排序

当然，按 rowid 对查询的输出进行排序很少有用。通常人们想按其他列对输出进行排序。

如果 ORDER BY 列上有可用索引，则该索引可用于排序。考虑对按“水果”排序的所有项目的请求：

SELECT * FROM fruitsforsale ORDER BY fruit;

图 18：使用索引排序

从上到下扫描 Idx1 索引（如果使用“ORDER BY fruit DESC”，则从下到上扫描）以便按水果顺序查找每个项目的 rowid。然后对于每个 rowid，进行二进制搜索以查找并输出该行。通过这种方式，输出以请求的顺序出现，而不需要收集整个输出并使用单独的步骤对其进行排序。

但这真的能节省时间吗？原始无索引排序中的步骤数与 NlogN成正比，因为这是对 N 行进行排序所花费的时间。但是，当我们使用此处所示的 Idx1 时，我们必须进行 N 次 rowid 查找，每次查找需要 logN 次，因此 NlogN 的总时间是相同的！

SQLite 使用基于成本的查询规划器。当有两种或多种方法可以解决同一个查询时，SQLite 会尝试使用每个计划来估计运行查询所需的总时间，然后使用具有最低估计成本的计划。成本主要是根据估计时间计算的，因此这种情况可能会根据表大小和可用的 WHERE 子句约束等进行选择。但一般来说，如果没有其他原因，索引排序可能会被选择，因为它不需要在排序前将整个结果集累积到临时存储中，因此使用的临时存储少得多。

2.3. 按覆盖索引排序

如果一个查询可以使用覆盖索引，那么就可以避免多次 rowid 查找，并且查询的成本会大大降低。

图 19：使用覆盖索引排序

使用覆盖索引，SQLite 可以简单地将索引从一端遍历到另一端，并及时提供与 N 成比例的输出，而无需分配大缓冲区来保存结果集。

3.同时搜索和排序

前面的讨论将搜索和排序视为不同的主题。但在实践中，经常会出现同时搜索和排序的情况。幸运的是，可以使用单个索引来做到这一点。

3.1. 使用多列索引进行搜索和排序

假设我们要查找按产地所在州排序的各种橙子的价格。查询是这样的：

SELECT price FROM fruitforsale WHERE fruit='Orange' ORDER BY state

该查询在 WHERE 子句中包含搜索限制，在 ORDER BY 子句中包含排序顺序。使用双列索引 Idx3 可以同时完成搜索和排序。

图 20：按多列索引搜索和排序

该查询对索引执行二分搜索以查找具有 fruit='Orange' 的行子集。（因为水果列是索引最左边的列，索引的行是排序的，所有这样的行将是相邻的。）然后它从上到下扫描匹配的索引行，得到 rowids原始表，并针对每个 rowid 在原始表上进行二进制搜索以查找价格。

您会注意到上图中的任何地方都没有“排序”框。查询的 ORDER BY 子句已成为空操作。这里不必进行排序，因为输出顺序是按 state 列排序的，而 state 列也恰好是索引中 fruit 列之后的第一列。因此，如果我们从上到下扫描 fruit 列具有相同值的索引条目，则保证这些索引条目按 state 列排序。

3.2. 使用覆盖索引进行搜索和排序

覆盖索引也可以同时用于搜索和排序。考虑以下：

SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state

图 21：按覆盖索引搜索和排序

和以前一样，SQLite 对覆盖索引中满足 WHERE 子句的行范围进行单一二分查找，从上到下的扫描范围得到想要的结果。保证满足 WHERE 子句的行是相邻的，因为 WHERE 子句是对索引最左侧列的相等约束。通过从上到下扫描匹配的索引行，可以保证输出按州排序，因为州列是水果列右侧的下一列。因此，生成的查询非常高效。

SQLite 可以为降序 ORDER BY 使用类似的技巧：

SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state DESC

遵循相同的基本算法，只是这次索引的匹配行是从下到上而不是从上到下扫描的，因此状态将按降序显示。

3.3. 使用索引进行部分排序（又名块排序）

有时使用索引只能满足 ORDER BY 子句的一部分。例如，考虑以下查询：

SELECT * FROM fruitforsale ORDER BY fruit, price

如果使用覆盖索引进行扫描，“水果”列自然会按正确的顺序出现，但当有两行或更多行具有相同的水果时，价格可能会乱序。发生这种情况时，SQLite 会进行许多小排序，对每个不同的水果值进行排序，而不是进行一次大排序。下面的图 22 说明了这个概念。

图 22：部分按索引排序

在示例中，对于 fruit=='Orange' 的情况，有 5 种单元素和 1 种 2 元素，而不是单一的 7 个元素。

进行许多较小的排序而不是单一的大排序的优点是：

多个小排序共同使用比单个大排序更少的 CPU 周期。
每个小分类都是独立运行的，这意味着在任何时候都需要将更少的信息保存在临时存储中。
ORDER BY 的那些由于索引而已经处于正确顺序的列可以从排序键中省略，进一步减少存储要求和 CPU 时间。
输出行可以在每个小排序完成时返回到应用程序，并且在表扫描完成之前。
如果存在 LIMIT 子句，则可以避免扫描整个表。

由于这些优点，SQLite 总是尝试使用索引进行部分排序，即使无法按索引进行完整排序。

4.没有 ROWID 表

上述基本原则适用于普通 rowid 表和WITHOUT ROWID表。唯一的区别是用作表键并在索引中显示为最右边的项的 rowid 列被 PRIMARY KEY 取代。