當人們談論索引的時候，如果沒有特别指明類型 ，那多半說的是 b-tree 索引，它使用b-tree資料結構來存儲資料。大多數 mysql引擎都支援這種索引 。archive引擎是 一個例外 ：5.1 之前 archive 不支援任何索引 ，直到 5.1 才開始支援單個自增列 （ a uto increment ） 的索引。
我們使用術語＂b-tree ” ，是因為 mysql 在 create table 和其他語句中也使用該關鍵字 。
不過，底層的存儲引擎也可能使用不同的存儲結構，例如，ndb叢集存儲引擎内部實際上使用了t-tree結構存儲這種索引，即使其名字是btree1innodb則使用的是b+tree,各種資料結構和算榕的變種不在本書的讨論範圍之内。存儲引擎以不同的方式使用b-tree索引，性能也各有不同，各有優劣。例如，myisam使用字首壓縮技術使得索引更小，但innodb則按照原資料格式進行存儲。再如myisam索引通過資料的實體位置引用被索引的行，而innodb則根據主鍵引用被索引的行。b-tree通常意味着所有的值都是按順序存儲的，井且每一個葉子頁到根的距離相同。圖5-l展示了b-tree索引的抽象表示，大緻反映了innodb索引是如何工作的。myisam使用的結構有所不同，但基本思想是類似的。
b-tree索引能夠加快通路資料的速度，因為存儲引擎不再需要進行全表掃描來擷取需要的資料，取而代之的是從索引的根節點（圖示并未畫出）開始進行搜尋。根節點的槽中存放了指向子節點的指針，存儲引擎根據這些指針向下層查找。通過比較節點頁的值和要查找的值可以找到合适的指針進入下層子節點，這些指針實際上定義了子節點頁中值的上限和下限。最終存儲引擎要麼是找到對應的值，要麼該記錄不存在。
葉子節點比較特别，它們的指針指向的是被索引的資料，而不是其他的節點頁（不同引擎的“指針”類型不同）。圖5-1中僅繪制了一個節點和其對應的葉子節點，其實在根節點和葉子節點之間可能有很多層節點頁。樹的深度和表的大小直接相關。
b-tree對索引列是順序組織存儲的，是以很适合查找範圍資料。例如，在一個基于文本域的索引樹上，按字母順序傳遞連續的值進行查找是非常合适的，是以像“找出所有以i到k開頭的名字”這樣的查找效率會非常高。
假設有如下資料表：
1
2
3
4
5
6
7
<code>create</code> <code>table</code> <code>people (</code>
<code>last_name </code><code>varchar</code> <code>(32) </code><code>not</code> <code>null</code><code>,</code>
<code>first_name </code><code>varchar</code> <code>(32) </code><code>not</code> <code>null</code><code>,</code>
<code>dob </code><code>date</code> <code>not</code> <code>null</code><code>,</code>
<code>gender enum (</code><code>'m'</code><code>, </code><code>'f'</code><code>) </code><code>not</code> <code>null</code><code>,</code>
<code>key</code> <code>(last_name, f irst_name, dob)</code>
<code>)</code>
對于表中的每一行資料，索引中包含了last_name、first_name和dob列的值，圖5-2顯示了該索引是如何組織資料的存儲的。
請注意，索引對多個值進行排序的依據是四日.tetable語句中定義索引時列的順序。看一下最後兩個條目，兩個人的姓和名都一樣，則根據他們的出生日期來排列順序。
可以使用b-tree索引的查詢類型。b-tree索引适用于全鍵值、鍵值範圍或鍵字首查找其中鍵字首查找隻适用于根據最左字首的查找。前面所述的索引對如下類型的查詢有效。
全值比對
全值比對指的是和索引中的所有列進行比對，例如前面提到的索引可用于查找姓名為cubaallen、出生于1960-01-01的人。
比對最左前級
前面提到的索引可用于查找所有姓為allen的人，即隻使用索引的第一列。比對列前級也可以隻比對某一列的值的開頭部分。例如前面提到的索引可用于查找所有以j開頭的姓的人。這裡也隻使用了索引的第一列。
比對範圍值
例如前面提到的索引可用于查找姓在allen和barrymore之間的人。這裡也隻使用了索引的第一列。
精确比對呆一列并範圍比對另一列
前面提到的索引也可用于查找所有姓為allen，并且名字是字母k開頭（比如kim、karl等）的人。即第一列last_name全比對，第二列first_name範圍比對。
隻通路索引的查詢
b-tree通常可以支援“隻通路索引的查詢”，即查詢隻需要通路索引，而無須通路資料行。後面我們将單獨讨論這種“覆寫索引”的優化。
因為索引樹中的節點是有序的，是以除了按值查找之外，索引還可以用于查詢中的orderby操作（按順序查找）。一般來說，如果b-tree可以按照某種方式查找到值，那麼也可以按照這種方式用于排序。是以，如果0陽erby子句滿足前面列出的幾種查詢類型，則這個索引也可以滿足對應的排序需求。
下面是一些關于b-tree索引的限制：
•如果不是按照索引的最左列開始查找，則無法使用索引。例如上面例子中的索引在每用于查找名字為bill的人，也無怯查找某個特定生日的人，因為這兩列都不是最左資料列。類似地，也無戰查找姓氏以某個字母結尾的人。
•不能跳過索引中的列。也就是說，前面所述的索引無法用于查找姓為smith并且在某個特定日期出生的人。如果不指定名（first_name），則mysql隻能使用索引的第一列。
•如果查詢中有某個列的範圍(like between > < 都算範圍查詢)查詢，則其右邊所有列都無法使用索引優化查找。例如有查詢 where lastname='smith’and firstname like '%j%'and dob＝’1976-12-23＇，這個查詢隻能使用索引的前兩列，因為這裡的like是一個範圍條件（但是伺服器可以把其餘列用于其他目的）。如果範圍查詢列值的數量有限，那麼可以通過使用多個等于條件來代替範圍條件。在本章的索引案例學習部分，我們将示範一個詳細的案例。
到這裡讀者應該可以明白，前面提到的索引列的順序是多麼的重要：這些限制都和索引列的順序有關。在優化性能的時候，可能需要使用相同的列但順序不同的索引來滿足不同類型的查詢需求。
也有些限制并不是b-tree本身導緻的，而是mysql優化器和存儲引擎使用索引的方式導緻的，這部分限制在未來的版本中可能就不再是限制了。
摘抄至《高性能mysql》
特别說明：尊重作者的勞動成果，轉載請注明出處哦~~~http://blog.yemou.net/article/query/info/tytfjhfascvhzxcyt343