[toc]
在MySQL中，索引屬於存儲引擎級別的概念，不同存儲引擎對索引的實現方式是不同的，本文主要討論是MyISAM和InnoDB兩個存儲引擎的B+Tree索引的實現方式。
MyISAM引擎使用B+Tree作為索引結構，葉節點的data域存放的是數據記錄的地址，下面是MyISAM索引的原理圖：
上圖是壹個MyISAM表的主索引示意，可以看出MyISAM的索引文件僅僅保存數據記錄的地址，在MyIASM中，主索引和輔助索引在結構上沒有任何區別，只是主索引要求key是唯壹的，而輔助索引的key可以重復。B+Tree的所有葉子節點包含所有關鍵字且按照升序排列的。
MyISAM表的索引和數據是分離的，索引保存在“表名.MYI”文件內，而數據保存在“表名.MYD”中。
MyISAM的索引方式也叫做 非聚集 的，之所以這麽稱呼是為了與InnoDB的聚集索引區分。
雖然InnoDB也使用B+Tree作為索引結構，但是具體實現方式卻與MyISAM截然不同。
第壹個重大區別是InnoDB的數據文件本身就是索引文件，從上文知道MyISAM索引文件和數據文件是分離的，索引文件僅保存數據記錄地址，而在InnoDB中，表數據文件本身就是按B+Tree組織的壹個索引結構，這棵樹的葉節點data域保存了完整的數據記錄，這個索引的key是數據表的主鍵，因此InnoDB表數據文件本身就是主索引。
上圖是InnoDB主索引(同時也是數據文件)的示意圖，可以看到葉節點包含了完整的數據記錄。這種索引叫做 聚集索引 。因為InnoDB的數據文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵(MyISAM可以沒有)，如果沒有顯示指定，則MySQL系統會自動選擇壹個唯壹標識數據記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成壹個隱含字段為主鍵，這個字段長度為6字節，類型為長整形。
第二個與MyISAM索引的不同時InnoDB的輔助索引data域存儲相應記錄主鍵值而不是地址，換句話說，InnoDB的所有輔助索引都引用主鍵作為data域，例如，下圖定義在col3上的輔助索引：
這裏的英文字符的ASCII碼作為比較準則。聚集索引這種方式使得按照主鍵的搜索十分高效，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然後用主鍵索引到主索引中檢索獲取記錄。
了解不同存儲引擎的索引實現對於正確使用和優化索引都非常有幫助，例如知道了InnoDB的索引實現後，就很容易明白不建議使用過長的字段作為主鍵， 因為所有輔助索引都引用主索引，過長的主索引會令輔助索引變的更大 ，在例如， 用非單調的字段作為主鍵在InnoDB中不是個好主意，因為InnoDB數據文件本身是壹顆B+Tree非單調的主鍵會造成在插入新紀錄時數據文件為了維持B+Tree的特性而頻繁的分裂調整，十分低效，而使用自增字段作為主鍵則是壹個很好的選擇
ES的索引不是B+Tree樹，而是倒排索引，ES的倒排索引由 Term index，Term Dictionary和Posting List 組成的。
有倒排索引(inverted index)就用正排索引(forward index)，正排索引就是文檔(Document)和他字段Fields正向對應的關系對應表如下：
那麽倒排索引是字段Field和擁有這個Field的文檔對應的關系如下：
Sex字段：
Age字段：
Jack、lucy或者17，18叫做term，而[1,3]就是Posting list。Posting list就是壹個int數組，存儲了所有包含某個term的文檔id，那麽什麽是term index和term dictionary？
如上如果name字段很多個term，比如Carla,Sara,Elin,Ada,Patty,Kate,Selena，如果按照這樣的順序排列，找出某個特定的term壹定很慢，因為term沒有排序，需要全部過濾壹遍，才能找出特定的term。排序之後就變成了：Ada,Carla,Elin,Kate,Patty,Sara,Selena。
這樣就可以使用二分法的方式，比全遍歷更快的找出目標的term，如果組織這些term的方式就是 term dictionary ，意思就是term的字典，有了term dictionary之後，就可以用比較少的比較次數和磁盤讀次數查找目標。但是磁盤的隨機讀操作仍然是非常昂貴的，所以盡量少的讀磁盤，有必要把壹些數據緩存到內存裏，但是整個Term dictionary本身又太大了，無法完整的放到內存中，於是就有了term index，Term index有點像壹本字典的打的章節表。比如：
A開頭的term ……………. Xxx頁
C開頭的term ……………. Xxx頁
E開頭的term ……………. Xxx頁
如果所有的term都是英文字符的話，可能這個term index就真的是26個英文字符表構成了。但是實際情況是，term未必都是英文字符，term可以是任意的byte數組。而且26個英文字符未必是每壹個字符都有均等的term，比如x字符開頭的term可能壹個都沒有，而s開頭的term又特別多，實際的term index是壹顆字典樹(trie 樹)：
上面例子是壹個包含A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的trie樹。這棵樹不會包含所有的term，他包含的是term的壹些 前綴 ，通過term index可以快速定位到term dictionary的某個offest，然後從這個位置在往後順序查找，再加上壹些壓縮技術，Term index的尺寸可以只有所有的term的尺寸的十分之壹，用內存緩存整個term index變成可能，整體上來說就是這樣的效果：
由Term index到Term Dictionary，再到posting list，通過某個字段的關鍵字去查詢結果的過程比較清楚了，通過多個關鍵字的posting list進行and或者or進行交集並集的查詢也簡單了( 倒排索引介紹了交集並集的過程 )
對比MySQL的B+Tree索引原理，可以發現：