本節，我們將循序漸進地進行介紹，從一個擴展的類比開始，以概述一些MongoDB鍵的實現細節結尾。期間，我將定義很多重要的術語並提供示例。如果你不太瞭解復合鍵索引、虛擬內存和索引數據結構，那麼閱讀本節將會受益匪淺。
7.1.1 思想實驗
要理解索引，你需要在腦中有個畫面，這裡建議想像一本食譜，不是普通的食譜，而是一本5000頁的厚重食譜，其中包含針對各種場合、菜餚和季節的精美食譜，在家就能找到所有的配料。這是本終極食譜，讓我們稱它The Cookbook Omega。
雖然這可能是所有食譜中最好的一本，但卻有兩個小問題。第一，所有的食譜是亂序的，第3475頁是Australian Braised Duck，而第2頁則是Zacatecan Tacos。
這還不是很要緊，關鍵問題是這本食譜沒有索引！
下面是你要問自己的第一個問題：沒有索引，如何在The Cookbook Omega中找到Rosemary Potatoes？唯一的選擇是一頁頁翻過去，直到找到為止。如果它在第3973頁，你得要翻多少頁啊！最壞的情況下，假設它在最後一頁，你需要把整本書都翻一遍！
這真令人抓狂，解決方案就是構建一個索引。
你可以想到多種食譜查找方法，其中食譜的名字可能是個不錯的起點。如果建立一個按字母排列的食譜名稱列表，隨後是其所在頁碼，那麼就按食譜名稱對本書建立索引了。其中的條目可能是下面這樣的：
Tibetan Yak Souffle: 45
Toasted Sesame Dumplings: 4,011
Turkey a 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樹心智模型，你還應該記住一些東西，例如索引是如何使用空間及如何進行維護的：再提醒一下，索引是有代價的。請謹慎選擇索引。