本节，我们将循序渐进地进行介绍，从一个扩展的类比开始，以概述一些MongoDB键的实现细节结尾。期间，我将定义很多重要的术语并提供示例。如果你不太了解复合键索引、虚拟内存和索引数据结构，那么阅读本节将会受益匪浅。
7.1.1 思想实验
要理解索引，你需要在脑中有个画面，这里建议想象一本食谱，不是普通的食谱，而是一本5000页的厚重食谱，其中包含针对各种场合、菜肴和季节的精美食谱，在家就能找到所有的配料。这是本终极食谱，让我们称它The Cookbook Omega。
虽然这可能是所有食谱中最好的一本，但却有两个小问题。第一，所有的食谱是乱序的，第3475页是Australian Braised Duck，而第2页则是Zacatecan Tacos。
这还不是很要紧，关键问题是这本食谱没有索引！
下面是你要问自己的第一个问题：没有索引，如何在The Cookbook Omega中找到Rosemary Potatoes？唯一的选择是一页页翻过去，直到找到为止。如果它在第3973页，你得要翻多少页啊！最坏的情况下，假设它在最后一页，你需要把整本书都翻一遍！
这真令人抓狂，解决方案就是构建一个索引。
你可以想到多种食谱查找方法，其中食谱的名字可能是个不错的起点。如果建立一个按字母排列的食谱名称列表，随后是其所在页码，那么就按食谱名称对本书建立索引了。其中的条目可能是下面这样的：
Tibetan Yak Soufflé: 45
Toasted Sesame Dumplings: 4,011
Turkey à la King: 943
只要知道食谱名字（哪怕只是名字的开头几个字母），就能通过该索引快速找到书中的任意食谱。如果你只希望按照这种方式来检索食谱，那就已经完事了。
但这是不现实的。比方说，你还会希望根据储藏室里的食材查找食谱，或者是根据菜肴来进行查找。针对这些情况，你需要更多的索引。
这就产生了第二个问题。只有一个基于食谱名称的索引，如何才能找到所有的鸡肉（chicken）相关的食谱呢？缺少合适的索引，你仍然需要翻阅整本食谱——5000页。在根据食材或者菜肴进行检索时都是如此。
为此，你需要构建另一个索引，这次是对食材进行索引。在这个索引里，按字母顺序排列食材，每个食材都指向所有包含它的食谱所在的页码。最基本的食材索引是这样的：
Cashews: 3, 20, 42, 88, 103, 1,215...
Cauliflower: 2, 47, 88, 89, 90, 275...
Chicken: 7, 9, 80, 81, 82, 83, 84...
Currants: 1,001, 1,050, 2,000, 2,133...
这是你所希望的索引吗？是不是很有用？
如果只是需要指定食材的食谱清单，这个索引就够用了。但如果还希望在查找时包含任意其他与食谱相关的信息，还是要进行“扫描”——一旦知道菜花（cauliflower）的页码，你要翻到每一页找到食谱的名字以及菜肴类型。这比翻遍整本书要好，但还远远不够。
例如，几个月前，你无意间在The Cookbook Omega里发现了一个很棒的鸡肉料理食谱，但却忘了它的名字。目前为止，有两个索引，一个是食谱名称的索引，另一个是食材的索引。是否能将两者结合起来，找到被你遗忘的鸡肉食谱呢？
实际上，这是不可能的。如果从食谱名称的索引入手，但却不记得名字，检索这个索引只比翻阅全书好一点。从食材入手，则需要检查一系列页码，但这些页码无法插入基于食谱名称的索引。因此，这种情况下只能使用一个索引，本例中食材的索引更有用一些。
每个查询一个索引
用户通常认为一个查询里要查找两个字段，可以针对它们分离索引。有一个现成的算法：查找每个索引里匹配项的页码，针对同时匹配两个索引的食谱扫描它们页码的并集。会有不少匹配不上的页码，但还是能减少扫描的总数。一些数据库实现了这个算法，但MongoDB没有。就算它实现了，使用复合索引来查找两个字段总是会比我刚才描述的算法效率更高。请记住，每个查询中数据库只会使用一个索引，如果要对多个字段进行查询，请确保有这些字段的复合索引。
那该怎么办？幸好，我们有应对之道，答案在于使用复合索引。
到目前为止你所建立的是单键索引：它们都只对食谱的一个键进行索引。现在要为The Cookbook Omega构建一个新的索引，不同之处是这次要使用两个键。类似的使用多个键的索引称为复合索引（compound index）。
该复合索引依次使用了食材与食谱名称。可以这样来标记它： ingredient-name。其中的部分内容如图7-1所示。
图7-1 食谱中的复合索引
这个索引的值对人而言是显而易见的。现在你可以根据食材进行查找，大致定位要找的食谱，哪怕只记得名称的开头部分。对机器而言，它同样很有价值，不用扫描拥有该食材的全部食谱名称了。如果有几百个（或者几千个）鸡肉料理食谱，就像The Cookbook Omega一样，该复合索引尤其有用。你知道是为什么吗？
请注意一点：复合索引中的顺序是很有讲究的。假设将上述索引翻转为name-ingredient，它能替代我们之前用的复合索引吗？
明显不能！使用新索引，只要知道名称，搜索就一定会定位到一个食谱，书中的一页。如果是要查找含有香蕉（banana）食材的Cashew Marinade食谱，那么它就能确定不存在这个食谱。但现实情况恰恰相反：你知道食材，却不知道名称。
The Cookbook Omega现在有三个索引：recipe（食谱）、ingredient（食材）和ingredient-name（食材—食谱名称）。也就是说可以安全地去掉ingredient这个单键索引了。为什么？因为对某一食材的检索可以使用ingredient-name。如果你知道食材，可以遍历该复合索引，获得包含它的食谱的页码列表。再仔细看看该索引的示例，想想其中的原因。
本节的目的是为那些需要对索引有更进一步认识的读者提供一个隐喻。从中，你能认识到一些简单的经验法则，如下。
索引能显著减少获取文档所需的工作量。没有合适的索引，实现查询的唯一途径就是线性扫描整个文档，直到满足查询条件为止。这通常就是扫描整个集合。
解析查询时只会使用一个单键索引。1对于包含多个键（比如食材和食谱名称）的查询，包含这些键的复合索引能更好地解析查询。
1. 使用
$or操作符的查询是个例外。但通常情况下，只能使用一个索引，MongoDB也更倾向于此。如果有
ingredient-cuisine（食材—菜肴）索引，可以去掉ingredient索引，也应该这么做。更抽象一点，如果有一个a-b的复合索引，那么仅针对a的索引就是冗余的。22. 也有例外情况。如果b是一个多键索引，同时拥有a-b和a索引还是有意义的。
复合索引里键的顺序是很重要的。
请记住，这个比喻只能用到这一步。它是用来理解索引的一个模型，并不等于MongoDB中索引的工作方式。下一节里，我们会详细说明刚列出的几点内容，仔细探究MongoDB里的索引。
7.1.2 核心索引概念
上一节讲到了很多核心索引概念，本节和本章剩下的部分会对它们做详细说明。
1. 单键索引
单键索引中的每一项都对应了被索引文档里的一个值。默认的_id索引就是一个很好的例子，由于这个字段上有索引，可以根据它快速地获取文档。
2. 复合键索引
到目前为止，MongoDB中每个查询就使用一个索引。3但是你经常需要对多个属性进行查询，希望这些查询能尽可能高效一点。例如，假设你在本书电子商务示例的products集合上构建了两个索引：一个基于manufacturer（制造商）字段，另一个基于price（价格）字段。如此一来，你创建了两个截然不同的数据结构，在遍历时的顺序如图7-2所示。
3. 偶尔也有例外。举例来说，带有$or的查询里，每个$or查询的子句都能使用不同的索引，但每个子句本身只能使用一个索引。
图7-2 单键索引遍历
现在，假设查询是这样的：
db.products.find({/'details.manufacturer/': /'Acme/', /'pricing.sale/': {$lt: 7500}}) 这条查询的意思是找到所有Acme生产的售价低于75.00美元的产品。如果使用manufacturer或者price字段上的单键索引发起查询，那么只能用上其中的一个索引。查询优化器会选择两者中更高效的那个，但都无法给出理想的结果。要用这些索引满足查询，必须分别遍历这两个数据结构，抓取匹配数据的磁盘位置，再计算它们的并集。MongoDB目前并不支持这种做法，因为此时使用复合索引效率更高。
复合索引就是每一项都由多个键组合而成的索引。如果要构建一个基于 manufacturer和price的复合键索引，排序后的表示如图7-3所示。
图7-3 复合键索引遍历
要实现你的查询，查询优化器只需找到索引里第一条制造商是Acme、价格是75.00美元的索引项。随后简单地扫描连续的索引项，当制造商不再是Acme时停止。这样就能取到查询结果了。
结合使用索引和查询时，有两件事需要注意。第一，在索引里键的顺序很重要。如果声明了一个复合索引，价格是第一个键，制造商位于其后，那么查询效率很差。很难想通吗？看看图7-4里此类索引的结构吧。
图7-4 键顺序相反的复合索引
必须按照键的出现顺序进行比较。很遗憾，这个索引没办法轻松地跳至所有Acme产品，因此实现之前那条查询的唯一办法是查看每件价格小于75.00美元的产品，然后只取出Acme制造的产品。为了便于理解，假设你的集合里有100万个产品，价格都低于100.00美元，按价格均匀分布。在这种情况下，执行该查询要扫描750 000个索引项。相比之下，使用原来的复合索引，即制造商在价格之前，扫描的索引项数量就等于要返回的索引项数量。这是因为一旦找到Acme - 7500这一项，剩下的就是简单的顺序扫描了。
因此，在复合索引里键的顺序很重要。清楚了这一点之后，第二件要明白的事情是为什么选择这样的顺序。从图里看还是很明显的，但还可以换个方式来看这个问题。再仔细看下查询：有两个查询项指定了不同的匹配类型。在制造商字段上，希望精确匹配一项；但在价格字段上，希望匹配一个值范围，从7500开始。一般来说，一个查询里有一项要精确匹配，另一项指定了一个范围，在使用复合索引时，范围匹配的那个键放在第二个位置上。在查询优化的章节里我们还会看到这条规则。
3. 索引效率
索引对良好的查询性能来说是必不可少的，但每个新索引都会带来一些小的维护成本。其原因是显而易见的，每当向集合添加文档时，都必须修改集合上的所有索引，以加入新的文档。因此，如果一个集合上有10个索引，每次插入时就都要做10次独立的结构修改。对于所有写操作都是如此，无论是删除文档还是更新指定文档的索引键。
对于读密集型应用而言，索引的成本一般都是合理的，你只要认识到索引还是会引入一定开销，必须谨慎选择即可。这意味着确保所有索引都被用到，没有一个索引是多余的。可以在剖析应用程序的查询时部分落实这项工作，我会在本章的后续内容里描述这个过程。
此处还有另一个问题需要考虑：就算拥有正确的索引，还是有可能得不到快速的查询，索引和数据集无法全部放入内存时就会发生这种情况。
回想第1章，MongoDB使用mmap系统调用告诉操作系统将所有数据文件映射到内存里。基于这点，操作系统会按照名为页（page）的4 KB块4将数据文件换入换出内存，包含所有文档、集合与索引。在请求指定页的数据时，操作系统必须保证该页在内存里。如果不在，会抛出页错误（page fault）异常，告诉内存管理器从磁盘上把页加载到内存里。
4. 4 KB的页大小是标准值，但并非普遍适用。
有了充足的内存，所有使用中的数据文件最终都会被加载到内存里。当那块内存发生改变时，比如执行写操作时，那些改变会被操作系统异步地刷到磁盘上，而写操作很快，是直接发生在内存里的。数据完全装入内存是最为理想的状态，因为磁盘访问的数量会降到最低程度。但如果使用中的数据集无法全部装入内存，就该出现页错误了。也就是说操作系统会频繁访问磁盘，大大减缓读写操作。最坏的情况下，数据大小远远大于可用内存，这时任何读写操作的数据都必须到磁盘上做页交换。这种情况称为颠簸（thrashing），会导致性能严重下滑。
还好这种情况相对容易避免。最起码要保证索引都能放入内存；对于为何避免创建无用索引如此重要，这就是原因之一。拥有额外的索引，就会要求更多的内存来维护那些索引。同样道理，每个索引应该只包含它需要的键：有时会用到三键复合索引，但请注意它要比简单的单键索引占用更多的空间。
理想情况下，索引和使用中的数据集都能放入内存。但评估部署时需要有多少内存并非易事。你可以通过查看 stats命令的结果来了解总的索引大小。但要找到工作集（working set）大小却没这么容易，因为每个应用程序都不一样。工作集通常是查询与更新的全部数据的子集。举例来说，假设你有100万用户，只有一半是活跃用户，那么工作集就是用户集合的一半大小。如果全部都是活跃用户，那么工作集就等于整个数据集。
在第10章，我们会重温工作集的概念，了解诊断硬件相关性能问题的具体手段。就目前而言，只需知道添加新索引有潜在的成本，关注索引与工作集大小与内存的比率，这能帮你在数据增长时维护良好的性能。
7.1.3 B树
前文提到过，MongoDB内部使用B树来表示索引。B树无处不在（见http://mng.bz/wQfG），至少从20世纪70年代后期开始就流行于数据库记录和索引中。5如果你使用过其他数据库系统，那么可能已经熟知使用B树的各种情况了。这很好，你可以将之前的大多数索引相关的知识有效地利用起来。如果**不太了解**B树，也没关系，本节将介绍与使用MongoDB最为相关的概念。
5. MongoDB中B树仅用于索引；集合存储为双向列表（doubly-linked list）。
B树有两个显著特点，并因此成为了数据库索引的理想选择。第一，它们能用于多种查询，包括精确匹配、范围条件、排序、前缀匹配和仅用索引的查询。第二，在添加和删除键的时候，它们仍能保持平衡。
我们会看到一棵简单的B树，讨论一些应该牢记在心的原则。想象有一个用户的集合，在姓氏（last name）和年龄（age）字段上创建了一个复合索引。6结果B树的抽象表述可能是图7-5这样的。
6. 在姓氏与年龄上创建索引有点牵强，但却能很好地阐明一些概念。
你一定已经猜到了，B树是一个树型数据结构。树中的每一个节点都能包含多个键。在示例中，根节点包含两个键，每个都以BSON对象的形式来表示users集合中被索引的值。在读取了根节点的内容之后，你能看到两个文档的键，分别表示姓氏Edwards和Perry，年龄是21岁和18岁。每个键都包含了两个指针：一个指向它所属的数据文件，另一个指向子节点。此外，节点自己还指向另一个节点，其值小于本节点的最小值。
图7-5 B树结构示例
有件事情需要注意，每个节点都有一些留空的空间（不是用来伸缩的）。在MongoDB的B树实现里，新节点会被分配8192字节，也就是说实际上每个节点都能包含数百个键。这取决于索引键的平均大小；本例中，平均键大小可能在30字节左右。MongoDB v2.0里键最大可以是1024字节。每个键有额外的18字节，每个节点再多40字节，其结果就是每个节点能容纳170个键7。
7. (8192-40) / (30 + 18) = 169.8。
这很有关系，因为用户经常想知道为什么索引是这个大小。你现在知道了每个节点是8 KB，可以估算出每个节点能容纳多少键。计算时，请牢记：在默认情况下，B树节点的内容通常有意维持在60%左右。
如果理解了上述内容，除了这个粗略的B树心智模型，你还应该记住一些东西，例如索引是如何使用空间及如何进行维护的：再提醒一下，索引是有代价的。请谨慎选择索引。