B+树索引及其使用
B+樹索引及其使用
一、B+樹索引
我們先來回顧一下前面講的Innodb數據頁的7個組成部分，首先各個數據頁可以組成一個雙向鏈表，而每個數據頁中的記錄會按照主鍵值從小到大的順序組成一個單向鏈表，每個數據頁都會為存儲在它里邊兒的記錄生成一個頁目錄，在通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應的槽，然后再遍歷該槽對應分組中的記錄即可快速找到指定的記錄。
| File Header | 文件頭部 | 38字節 | 頁的一些通用信息（頁號、上下頁號、頁類型、表空間、校驗和等） |
| Page Header | 頁面頭部 | 56字節 | 數據頁專有的一些信息（槽的數量、記錄的數量地址、B+樹的層級、索引ID等） |
| Infimum + Supremum | 最大記錄和最小記錄 | 26字節 | 兩個虛擬行記錄 |
| User Records | 用戶記錄 | 不確定 | 實際存儲的行記錄內容 |
| Free Space | 空閑記錄 | 不確定 | 頁中尚未使用的空間 |
| Page Directory | 頁面目錄 | 不確定 | 頁中的某些記錄的相對位置（槽、每組最后一條記錄的的地址偏移量） |
| File Trailer | 文件尾部 | 8字節 | 檢驗頁是否完整（檢驗和、最后修改對應的日志序列位置LSN） |
| 預留位1 | 1 | 沒有使用 |
| 預留位2 | 1 | 沒有使用 |
| delete_mask | 1 | 標記該記錄是否被刪除 |
| min_rec_mask | 1 | B+樹的每層非葉子節點中的最小記錄都會添加該標記 |
| n_owned | 4 | 表示當前記錄擁有的記錄數 |
| heap_no | 13 | 表示當前記錄在記錄堆的位置信息 |
| record_type | 3 | 表示當前記錄的類型，0表示普通記錄，1表示B+樹非葉子節點記錄，2表示最小記錄，3表示最大記錄 |
| next_record | 16 | 表示下一條記錄的相對位置 |
1.1沒有索引的查找
本集的主題是索引，在正式介紹索引之前，我們需要了解一下沒有索引的時候是怎么查找記錄的。為了方便大家理解，我們下邊先只嘮叨搜索條件為對某個列精確匹配的情況，所謂精確匹配，就是搜索條件中用等于=連接起的表達式，比如這樣：
SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;在一個頁中的查找
假設目前表中的記錄比較少，所有的記錄都可以被存放到一個頁中，在查找記錄的時候可以根據搜索條件的不同分為兩種情況：
- 以主鍵為搜索條件
這個查找過程我們已經很熟悉了，可以在頁目錄中使用二分法快速定位到對應的槽，然后再遍歷該槽對應分組中的記錄即可快速找到指定的記錄。 - 以其他列為搜索條件
對非主鍵列的查找的過程可就不這么幸運了，因為在數據頁中并沒有對非主鍵列建立所謂的頁目錄，所以我們無法通過二分法快速定位相應的槽。這種情況下只能從最小記錄開始依次遍歷單鏈表中的每條記錄，然后對比每條記錄是不是符合搜索條件。很顯然，這種查找的效率是非常低的。
在很多頁中查找
大部分情況下我們表中存放的記錄都是非常多的，需要好多的數據頁來存儲這些記錄。在很多頁中查找記錄的話可以分為兩個步驟：
在沒有索引的情況下，不論是根據主鍵列或者其他列的值進行查找，由于我們并不能快速的定位到記錄所在的頁，所以只能從第一個頁沿著雙向鏈表一直往下找，在每一個頁中根據我們剛剛嘮叨過的查找方式去查找指定的記錄。因為要遍歷所有的數據頁，所以這種方式顯然是超級耗時的，如果一個表有一億條記錄，使用這種方式去查找記錄那要等到猴年馬月才能等到查找結果。所以祖國和人民都在期盼一種能高效完成搜索的方法，索引同志就要亮相登臺了。
1.2索引
一個簡單的索引方案
回到正題，我們在根據某個搜索條件查找一些記錄時為什么要遍歷所有的數據頁呢？因為各個頁中的記錄并沒有規律，我們并不知道我們的搜索條件匹配哪些頁中的記錄，所以 不得不 依次遍歷所有的數據頁。所以如果我們想快速的定位到需要查找的記錄在哪些數據頁中該咋辦？還記得我們為根據主鍵值快速定位一條記錄在頁中的位置而設立的頁目錄么？我們也可以想辦法為快速定位記錄所在的數據頁而建立一個別的目錄，建這個目錄必須完成下邊這些事兒：
- 下一個數據頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值。
咦？怎么分配的頁號是28呀，不應該是11么？再次強調一遍，新分配的數據頁編號可能并不是連續的，也就是說我們使用的這些頁在存儲空間里可能并不挨著。它們只是通過維護著上一個頁和下一個頁的編號而建立了鏈表關系。另外，頁10中用戶記錄最大的主鍵值是5，而頁28中有一條記錄的主鍵值是4，因為5 > 4，所以這就不符合下一個數據頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值的要求，所以在插入主鍵值為4的記錄的時候需要伴隨著一次記錄移動，也就是把主鍵值為5的記錄移動到頁28中，然后再把主鍵值為4的記錄插入到頁10中，這個過程的示意圖如下：
這個過程表明了在對頁中的記錄進行增刪改操作的過程中，我們必須通過一些諸如記錄移動的操作來始終保證這個狀態一直成立：下一個數據頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值。這個過程我們也可以稱為頁分裂。
- 給所有的頁建立一個目錄項。
由于數據頁的編號可能并不是連續的，所以在向index_demo表中插入許多條記錄后，可能是這樣的效果：
因為這些16KB的頁在物理存儲上可能并不挨著，所以如果想從這么多頁中根據主鍵值快速定位某些記錄所在的頁，我們需要給它們做個目錄，每個頁對應一個目錄項，每個目錄項包括下邊兩個部分
- 頁的用戶記錄中最小的主鍵值，我們用key來表示。
- 頁號，我們用page_no表示。
以頁28為例，它對應目錄項2，這個目錄項中包含著該頁的頁號28以及該頁中用戶記錄的最小主鍵值5。我們只需要把幾個目錄項在物理存儲器上連續存儲，比如把他們放到一個數組里，就可以實現根據主鍵值快速查找某條記錄的功能了。比方說我們想找主鍵值為20的記錄，具體查找過程分兩步：
至此，針對數據頁做的簡易目錄就搞定了。不過忘了說了，這個目錄有一個別名，稱為索引。
1.3InnoDB中的索引方案
上邊之所以稱為一個簡易的索引方案，是因為我們為了在根據主鍵值進行查找時使用二分法快速定位具體的目錄項而假設所有目錄項都可以在物理存儲器上連續存儲，但是這樣做有幾個問題：
- InnoDB是使用頁來作為管理存儲空間的基本單位，也就是最多能保證16KB的連續存儲空間，而隨著表中記錄數量的增多，需要非常大的連續的存儲空間才能把所有的目錄項都放下，這對記錄數量非常多的表是不現實的。
- 我們時常會對記錄進行增刪，假設我們把頁28中的記錄都刪除了，頁28也就沒有存在的必要了，那意味著目錄項2也就沒有存在的必要了，這就需要把目錄項2后的目錄項都向前移動一下，這種牽一發而動全身的設計不是什么好主意～
所以，設計InnoDB的大叔們需要一種可以靈活管理所有目錄項的方式。他們靈光乍現，忽然發現這些目錄項其實長得跟我們的用戶記錄差不多，只不過目錄項中的兩個列是主鍵和頁號而已，所以他們復用了之前存儲用戶記錄的數據頁來存儲目錄項，為了和用戶記錄做一下區分，我們把這些用來表示目錄項的記錄稱為目錄項記錄。那InnoDB怎么區分一條記錄是普通的用戶記錄還是目錄項記錄呢？別忘了記錄頭信息里的record_type屬性，它的各個取值代表的意思如下：
0：普通的用戶記錄
1：目錄項記錄
2：最小記錄
3：最大記錄
從圖中可以看出來，我們新分配了一個編號為30的頁來專門存儲目錄項記錄。這里再次強調一遍目錄項記錄和普通的用戶記錄的不同點：
- 目錄項記錄的record_type值是1，而普通用戶記錄的record_type值是0。
- 目錄項記錄只有主鍵值和頁的編號兩個列，而普通的用戶記錄的列是用戶自己定義的，可能包含很多列，另外還有InnoDB自己添加的隱藏列。
- 還記得我們之前在嘮叨記錄頭信息的時候說過一個叫min_rec_mask的屬性么，只有在存儲目錄項記錄的頁中的主鍵值最小的目錄項記錄的min_rec_mask值為1，其他別的記錄的min_rec_mask值都是0。
除了上述幾點外，這兩者就沒啥差別了，它們用的是一樣的數據頁（頁面類型都是0x45BF，這個屬性在File Header中，忘了的話可以翻到前邊的文章看），頁的組成結構也是一樣一樣的（就是我們前邊介紹過的7個部分），都會為主鍵值生成Page Directory（頁目錄），從而在按照主鍵值進行查找時可以使用二分法來加快查詢速度。現在以查找主鍵為20的記錄為例，根據某個主鍵值去查找記錄的步驟就可以大致拆分成下邊兩步：
雖然說目錄項記錄中只存儲主鍵值和對應的頁號，比用戶記錄需要的存儲空間小多了，但是不論怎么說一個頁只有16KB大小，能存放的目錄項記錄也是有限的，那如果表中的數據太多，以至于一個數據頁不足以存放所有的目錄項記錄，該咋辦呢？
當然是再多整一個存儲目錄項記錄的頁嘍～ 為了大家更好的理解新分配一個目錄項記錄頁的過程，我們假設一個存儲目錄項記錄的頁最多只能存放4條目錄項記錄（請注意是假設哦，真實情況下可以存放好多條的），所以如果此時我們再向上圖中插入一條主鍵值為320的用戶記錄的話，那就需要分配一個新的存儲目錄項記錄的頁嘍：
從圖中可以看出，我們插入了一條主鍵值為320的用戶記錄之后需要兩個新的數據頁：
- 為存儲該用戶記錄而新生成了頁31。
- 因為原先存儲目錄項記錄的頁30的容量已滿（我們前邊假設只能存儲4條目錄項記錄），所以不得不需要一個新的頁32來存放頁31對應的目錄項。
現在因為存儲目錄項記錄的頁不止一個，所以如果我們想根據主鍵值查找一條用戶記錄大致需要3個步驟，以查找主鍵值為20的記錄為例：
我們現在的存儲目錄項記錄的頁有兩個，即頁30和頁32，又因為頁30表示的目錄項的主鍵值的范圍是[1, 320)，頁32表示的目錄項的主鍵值不小于320，所以主鍵值為20的記錄對應的目錄項記錄在頁30中。
那么問題來了，在這個查詢步驟的第1步中我們需要定位存儲目錄項記錄的頁，但是這些頁在存儲空間中也可能不挨著，如果我們表中的數據非常多則會產生很多存儲目錄項記錄的頁，那我們怎么根據主鍵值快速定位一個存儲目錄項記錄的頁呢？其實也簡單，為這些存儲目錄項記錄的頁再生成一個更高級的目錄，就像是一個多級目錄一樣，大目錄里嵌套小目錄，小目錄里才是實際的數據（遞歸定義），所以現在各個頁的示意圖就是這樣子：
如圖，我們生成了一個存儲更高級目錄項的頁33，這個頁中的兩條記錄分別代表頁30和頁32，如果用戶記錄的主鍵值在[1, 320)之間，則到頁30中查找更詳細的目錄項記錄，如果主鍵值不小于320的話，就到頁32中查找更詳細的目錄項記錄。不過這張圖好漂亮喔，隨著表中記錄的增加，這個目錄的層級會繼續增加，如果簡化一下，那么我們可以用下邊這個圖來描述它：
這玩意兒像不像一個倒過來的樹呀，上頭是樹根，下頭是樹葉！其實這是一種組織數據的形式，或者說是一種數據結構，它的名稱是B+樹。
不論是存放用戶記錄的數據頁，還是存放目錄項記錄的數據頁，我們都把它們存放到B+樹這個數據結構中了，所以我們也稱這些數據頁為節點。從圖中可以看出來，我們的實際用戶記錄其實都存放在B+樹的最底層的節點上，這些節點也被稱為葉子節點或葉節點，其余用來存放目錄項的節點稱為非葉子節點或者內節點，其中B+樹最上邊的那個節點也稱為根節點。
從圖中可以看出來，一個B+樹的節點其實可以分成好多層，設計InnoDB的大叔們為了討論方便，規定最下邊的那層，也就是存放我們用戶記錄的那層為第0層，之后依次往上加。之前的討論我們做了一個非常極端的假設：存放用戶記錄的頁最多存放3條記錄，存放目錄項記錄的頁最多存放4條記錄。其實真實環境中一個頁存放的記錄數量是非常大的，假設，假設，假設所有存放用戶記錄的葉子節點代表的數據頁可以存放100條用戶記錄，所有存放目錄項記錄的內節點代表的數據頁可以存放1000條目錄項記錄，那么：
- 如果B+樹只有1層，也就是只有1個用于存放用戶記錄的節點，最多能存放100條記錄。
- 如果B+樹有2層，最多能存放1000×100=100000條記錄。
- 如果B+樹有3層，最多能存放1000×1000×100=100000000條記錄。
- 如果B+樹有4層，最多能存放1000×1000×1000×100=100000000000條記錄。哇咔咔～這么多的記錄！！！
你的表里能存放100000000000條記錄么？所以一般情況下，我們用到的B+樹都不會超過4層，那我們通過主鍵值去查找某條記錄最多只需要做4個頁面內的查找（查找3個目錄項頁和一個用戶記錄頁），又因為在每個頁面內有所謂的Page Directory（頁目錄），所以在頁面內也可以通過二分法實現快速定位記錄，這不是很牛么，哈哈！
B+樹
在介紹B樹之前，先來看另一棵神奇的樹——二叉排序樹（Binary Sort Tree），首先它是一棵樹，“二叉”這個描述已經很明顯了，就是樹上的一根樹枝開兩個叉，于是遞歸下來就是二叉樹了（下圖所示），而這棵樹上的節點是已經排好序的，具體的排序規則如下：
- 若左子樹不空，則左子樹上所有節點的值均小于它的根節點的值
- 若右子樹不空，則右字數上所有節點的值均大于它的根節點的值
- 它的左、右子樹也分別為二叉排序數（遞歸定義）
從圖中可以看出，二叉排序樹組織數據時，用于查找是比較方便的，因為每次經過一次節點時，最多可以減少一半的可能，不過極端情況會出現所有節點都位于同一側，直觀上看就是一條直線，那么這種查詢的效率就比較低了，因此需要對二叉樹左右子樹的高度進行平衡化處理，于是就有了平衡二叉樹（Balenced Binary Tree）。
所謂“平衡”，說的是這棵樹的各個分支的高度是均勻的，它的左子樹和右子樹的高度之差絕對值小于1，這樣就不會出現一條支路特別長的情況。于是，在這樣的平衡樹中進行查找時，總共比較節點的次數不超過樹的高度，這就確保了查詢的效率（時間復雜度為O(logn)）
總的來說，m階B樹滿足以下條件：
- 每個節點至多可以擁有m棵子樹。
- 根節點，只有至少有2個節點（要么極端情況，就是一棵樹就一個根節點，單細胞生物，即是根，也是葉，也是樹)。
- 非根非葉的節點至少有的Ceil(m/2)個子樹(Ceil表示向上取整，圖中5階B樹，每個節點至少有3個子樹，也就是至少有3個叉)。
- 非葉節點中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示該節點中保存的關鍵字個數，K為關鍵字且Ki<Ki+1，A為指向子樹根節點的指針。
- 從根到葉子的每一條路徑都有相同的長度，也就是說，葉子節在相同的層，并且這些節點不帶信息，實際上這些節點就表示找不到指定的值，也就是指向這些節點的指針為空。
B樹的查詢過程和二叉排序樹比較類似，從根節點依次比較每個結點，因為每個節點中的關鍵字和左右子樹都是有序的，所以只要比較節點中的關鍵字，或者沿著指針就能很快地找到指定的關鍵字，如果查找失敗，則會返回葉子節點，即空指針。
例如查詢圖中字母表中的K：
B樹的特點可以總結為如下：
- 關鍵字集合分布在整顆樹中。
- 任何一個關鍵字出現且只出現在一個節點中。
- 搜索有可能在非葉子節點結束。
- 其搜索性能等價于在關鍵字集合內做一次二分查找。
- B樹在插入刪除新的數據記錄會破壞B-Tree的性質，因為在插入刪除時，需要對樹進行一個分裂、合并、轉移等操作以保持B-Tree性質。
作為B樹的加強版，B+樹與B樹的差異在于
- 有n棵子樹的節點含有n個關鍵字（也有認為是n-1個關鍵字）。
- 所有的關鍵字全部存儲在葉子節點上，且葉子節點本身根據關鍵字自小而大順序連接。
- 非葉子節點可以看成索引部分，節點中僅含有其子樹（根節點）中的最大（或最小）關鍵字。
B+樹的查找過程，與B樹類似，只不過查找時，如果在非葉子節點上的關鍵字等于給定值，并不終止，而是繼續沿著指針直到葉子節點位置。因此在B+樹，不管查找成功與否，每次查找都是走了一條從根到葉子節點的路徑。
B+樹的特性如下：
- 所有關鍵字都存儲在葉子節上，且鏈表中的關鍵字恰好是有序的。
- 不可能非葉子節點命中返回。
- 非葉子節點相當于葉子節點的索引，葉子節點相當于是存儲（關鍵字）數據的數據層。
- 更適合文件索引系統。
如上圖所示，在B+Tree的每個葉子節點增加一個指向相鄰葉子節點的指針，就形成了帶有順序訪問指針的B+Tree。做這個優化的目的是為了提高區間訪問的性能，例如圖4中如果要查詢key為從18到49的所有數據記錄，當找到18后，只需順著節點和指針順序遍歷就可以一次性訪問到所有數據節點，極大提到了區間查詢效率。
紅黑樹等數據結構也可以用來實現索引，但是文件系統以及數據庫系統普遍采用B樹或者B+樹，這一節將結合計算機組成原理相關知識討論B-/+Tree作為索引的理論基礎。
一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲在磁盤上。這樣的話，索引查找過程中就要產生磁盤I/O消耗，相對于內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤I/O操作次數的漸進復雜度。換句話說，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數。
聚簇索引
我們上邊介紹的B+樹本身就是一個目錄，或者說本身就是一個索引。它有兩個特點：
- 使用記錄主鍵值的大小進行記錄和頁的排序，這包括三個方面的含義：
1. 頁內的記錄是按照主鍵的大小順序排成一個單向鏈表。
2. 各個存放用戶記錄的頁也是根據頁中用戶記錄的主鍵大小順序排成一個雙向鏈表。
3. 存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的主鍵大小順序排成一個雙向鏈表。 - B+樹的葉子節點存儲的是完整的用戶記錄。
所謂完整的用戶記錄，就是指這個記錄中存儲了所有列的值（包括隱藏列）。
我們把具有這兩種特性的B+樹稱為聚簇索引，所有完整的用戶記錄都存放在這個聚簇索引的葉子節點處。這種聚簇索引并不需要我們在MySQL語句中顯式的使用INDEX語句去創建（后邊會介紹索引相關的語句），InnoDB存儲引擎會自動的為我們創建聚簇索引。另外有趣的一點是，在InnoDB存儲引擎中，聚簇索引就是數據的存儲方式（所有的用戶記錄都存儲在了葉子節點），也就是所謂的索引即數據，數據即索引。
二級索引
大家有木有發現，上邊介紹的聚簇索引只能在搜索條件是主鍵值時才能發揮作用，因為B+樹中的數據都是按照主鍵進行排序的。那如果我們想以別的列作為搜索條件該咋辦呢？難道只能從頭到尾沿著鏈表依次遍歷記錄么？
不，我們可以多建幾棵B+樹，不同的B+樹中的數據采用不同的排序規則。比方說我們用c2列的大小作為數據頁、頁中記錄的排序規則，再建一棵B+樹，效果如下圖所示：
這個B+樹與上邊介紹的聚簇索引有幾處不同：
- 使用記錄c2列的大小進行記錄和頁的排序，這包括三個方面的含義：
- 頁內的記錄是按照c2列的大小順序排成一個單向鏈表。
- 各個存放用戶記錄的頁也是根據頁中記錄的c2列大小順序排成一個雙向鏈表。
- 存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的c2列大小順序排成一個雙向鏈表。
- B+樹的葉子節點存儲的并不是完整的用戶記錄，而只是c2列+主鍵這兩個列的值。
- 目錄項記錄中不再是主鍵+頁號的搭配，而變成了c2列+頁號的搭配。
所以如果我們現在想通過c2列的值查找某些記錄的話就可以使用我們剛剛建好的這個B+樹了。以查找c2列的值為4的記錄為例，查找過程如下：
根據根頁面，也就是頁44，可以快速定位到目錄項記錄所在的頁為頁42（因為2 < 4 < 9）。
在頁42中可以快速定位到實際存儲用戶記錄的頁，但是由于c2列并沒有唯一性約束，所以c2列值為4的記錄可能分布在多個數據頁中，又因為2 < 4 ≤ 4，所以確定實際存儲用戶記錄的頁在頁34和頁35中。
到頁34和頁35中定位到具體的記錄。
各位各位，看到步驟4的操作了么？我們根據這個以c2列大小排序的B+樹只能確定我們要查找記錄的主鍵值，所以如果我們想根據c2列的值查找到完整的用戶記錄的話，仍然需要到聚簇索引中再查一遍，這個過程也被稱為回表。也就是根據c2列的值查詢一條完整的用戶記錄需要使用到2棵B+樹！！！
為什么我們還需要一次回表操作呢？直接把完整的用戶記錄放到葉子節點不就好了么？你說的對，如果把完整的用戶記錄放到葉子節點是可以不用回表，但是太占地方了呀～相當于每建立一棵B+樹都需要把所有的用戶記錄再都拷貝一遍，這就有點太浪費存儲空間了。因為這種按照非主鍵列建立的B+樹需要一次回表操作才可以定位到完整的用戶記錄，所以這種B+樹也被稱為二級索引（英文名secondary index），或者輔助索引。由于我們使用的是c2列的大小作為B+樹的排序規則，所以我們也稱這個B+樹為為c2列建立的索引。
聯合索引
我們也可以同時以多個列的大小作為排序規則，也就是同時為多個列建立索引，比方說我們想讓B+樹按照c2和c3列的大小進行排序，這個包含兩層含義：
- 先把各個記錄和頁按照c2列進行排序。
- 在記錄的c2列相同的情況下，采用c3列進行排序
為c2和c3列建立的索引的示意圖如下：
如圖所示，我們需要注意一下幾點：
- 每條目錄項記錄都由c2、c3、頁號這三個部分組成，各條記錄先按照c2列的值進行排序，如果記錄的c2列相同，則按照c3列的值進行排序。
- B+樹葉子節點處的用戶記錄由c2、c3和主鍵c1列組成。
千萬要注意一點，以c2和c3列的大小為排序規則建立的B+樹稱為聯合索引，本質上也是一個二級索引。它的意思與分別為c2和c3列分別建立索引的表述是不同的，不同點如下：
- 建立聯合索引只會建立如上圖一樣的1棵B+樹。
- 為c2和c3列分別建立索引會分別以c2和c3列的大小為排序規則建立2棵B+樹。
1.4InnoDB的B+樹索引的注意事項
根節點萬年不動窩
我們前邊介紹B+樹索引的時候，為了大家理解上的方便，先把存儲用戶記錄的葉子節點都畫出來，然后接著畫存儲目錄項記錄的內節點，實際上B+樹的形成過程是這樣的：
- 每當為某個表創建一個B+樹索引（聚簇索引不是人為創建的，默認就有）的時候，都會為這個索引創建一個根節點頁面。最開始表中沒有數據的時候，每個B+樹索引對應的根節點中既沒有用戶記錄，也沒有目錄項記錄。
- 隨后向表中插入用戶記錄時，先把用戶記錄存儲到這個根節點中。
- 當根節點中的可用空間用完時繼續插入記錄，此時會將根節點中的所有記錄復制到一個新分配的頁，比如頁a中，然后對這個新頁進行頁分裂的操作，得到另一個新頁，比如頁b。這時新插入的記錄根據鍵值（也就是聚簇索引中的主鍵值，二級索引中對應的索引列的值）的大小就會被分配到頁a或者頁b中，而根節點便升級為存儲目錄項記錄的頁。
這個過程需要大家特別注意的是：一個B+樹索引的根節點自誕生之日起，便不會再移動。這樣只要我們對某個表建立一個索引，那么它的根節點的頁號便會被記錄到某個地方，然后凡是InnoDB存儲引擎需要用到這個索引的時候，都會從那個固定的地方取出根節點的頁號，從而來訪問這個索引。
內節點中目錄項記錄的唯一性
我們知道B+樹索引的內節點中目錄項記錄的內容是索引列 + 頁號的搭配，但是這個搭配對于二級索引來說有點兒不嚴謹。還拿index_demo表為例，假設這個表中的數據是這樣的：
| 1 | 1 | ‘u’ |
| 3 | 1 | ‘d’ |
| 5 | 1 | ‘y’ |
| 7 | 1 | ‘a’ |
如果二級索引中目錄項記錄的內容只是索引列 + 頁號的搭配的話，那么為c2列建立索引后的B+樹應該長這樣：
如果我們想新插入一行記錄，其中c1、c2、c3的值分別是：9、1、‘c’，那么在修改這個為c2列建立的二級索引對應的B+樹時便碰到了個大問題：由于頁3中存儲的目錄項記錄是由c2列 + 頁號的值構成的，頁3中的兩條目錄項記錄對應的c2列的值都是1，而我們新插入的這條記錄的c2列的值也是1，那我們這條新插入的記錄到底應該放到頁4中，還是應該放到頁5中啊？答案是：對不起，懵逼了。
為了讓新插入記錄能找到自己在那個頁里，我們需要保證在B+樹的同一層內節點的目錄項記錄除頁號這個字段以外是唯一的。所以對于二級索引的內節點的目錄項記錄的內容實際上是由三個部分構成的：
- 索引列的值
- 主鍵值
- 頁號
也就是我們把主鍵值也添加到二級索引內節點中的目錄項記錄了，這樣就能保證B+樹每一層節點中各條目錄項記錄除頁號這個字段外是唯一的，所以我們為c2列建立二級索引后的示意圖實際上應該是這樣子的：
這樣我們再插入記錄(9, 1, ‘c’)時，由于頁3中存儲的目錄項記錄是由c2列 + 主鍵 + 頁號的值構成的，可以先把新記錄的c2列的值和頁3中各目錄項記錄的c2列的值作比較，如果c2列的值相同的話，可以接著比較主鍵值，因為B+樹同一層中不同目錄項記錄的c2列 + 主鍵的值肯定是不一樣的，所以最后肯定能定位唯一的一條目錄項記錄，在本例中最后確定新記錄應該被插入到頁5中。
一個頁面最少存儲2條記錄
我們前邊說過一個B+樹只需要很少的層級就可以輕松存儲數億條記錄，查詢速度杠杠的！這是因為B+樹本質上就是一個大的多層級目錄，每經過一個目錄時都會過濾掉許多無效的子目錄，直到最后訪問到存儲真實數據的目錄。那如果一個大的目錄中只存放一個子目錄是個啥效果呢？那就是目錄層級非常非常非常多，而且最后的那個存放真實數據的目錄中只能存放一條記錄。費了半天勁只能存放一條真實的用戶記錄？逗我呢？所以InnoDB的一個數據頁至少可以存放兩條記錄，這也是我們之前嘮叨記錄行格式的時候說過一個結論（我們當時依據這個結論推導了表中只有一個列時該列在不發生行溢出的情況下最多能存儲多少字節，忘了的話回去看看吧）。
MyISAM中的索引方案簡單介紹
至此，我們介紹的都是InnoDB存儲引擎中的索引方案，為了內容的完整性，以及各位可能在面試的時候遇到這類的問題，我們有必要再簡單介紹一下MyISAM存儲引擎中的索引方案。我們知道InnoDB中索引即數據，也就是聚簇索引的那棵B+樹的葉子節點中已經把所有完整的用戶記錄都包含了，而MyISAM的索引方案雖然也使用樹形結構，但是卻將索引和數據分開存儲：
- 將表中的記錄按照記錄的插入順序單獨存儲在一個文件中，稱之為數據文件。這個文件并不劃分為若干個數據頁，有多少記錄就往這個文件中塞多少記錄就成了。我們可以通過行號而快速訪問到一條記錄。
MyISAM記錄也需要記錄頭信息來存儲一些額外數據，我們以上邊嘮叨過的index_demo表為例，看一下這個表中的記錄使用MyISAM作為存儲引擎在存儲空間中的表示：
由于在插入數據的時候并沒有刻意按照主鍵大小排序，所以我們并不能在這些數據上使用二分法進行查找。
- 使用MyISAM存儲引擎的表會把索引信息另外存儲到一個稱為索引文件的另一個文件中。MyISAM會單獨為表的主鍵創建一個索引，只不過在索引的葉子節點中存儲的不是完整的用戶記錄，而是主鍵值 + 行號的組合。也就是先通過索引找到對應的行號，再通過行號去找對應的記錄！
這一點和InnoDB是完全不相同的，在InnoDB存儲引擎中，我們只需要根據主鍵值對聚簇索引進行一次查找就能找到對應的記錄，而在MyISAM中卻需要進行一次回表操作，意味著MyISAM中建立的索引相當于全部都是二級索引！
- 如果有需要的話，我們也可以對其它的列分別建立索引或者建立聯合索引，原理和InnoDB中的索引差不多，不過在葉子節點處存儲的是相應的列 + 行號。這些索引也全部都是二級索引
MySQL中創建和刪除索引的語句
光顧著嘮叨索引的原理了，那我們如何使用MySQL語句去建立這種索引呢？InnoDB和MyISAM會自動為主鍵或者聲明為UNIQUE的列去自動建立B+樹索引，但是如果我們想為其他的列建立索引就需要我們顯式的去指明。為啥不自動為每個列都建立個索引呢？別忘了，每建立一個索引都會建立一棵B+樹，每插入一條記錄都要維護各個記錄、數據頁的排序關系，這是很費性能和存儲空間的。
我們可以在創建表的時候指定需要建立索引的單個列或者建立聯合索引的多個列：
CREATE TALBE 表名 (各種列的信息 ··· , [KEY|INDEX] 索引名 (需要被索引的單個列或多個列) )其中的KEY和INDEX是同義詞，任意選用一個就可以。我們也可以在修改表結構的時候添加索引：
ALTER TABLE 表名 ADD [INDEX|KEY] 索引名 (需要被索引的單個列或多個列);也可以在修改表結構的時候刪除索引：
ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;比方說我們想在創建index_demo表的時候就為c2和c3列添加一個聯合索引，可以這么寫建表語句：
CREATE TABLE index_demo(c1 INT,c2 INT,c3 CHAR(1),PRIMARY KEY(c1),INDEX idx_c2_c3 (c2, c3) );在這個建表語句中我們創建的索引名是idx_c2_c3，這個名稱可以隨便起，不過我們還是建議以idx_為前綴，后邊跟著需要建立索引的列名，多個列名之間用下劃線_分隔開。
如果我們想刪除這個索引，可以這么寫：
ALTER TABLE index_demo DROP INDEX idx_c2_c3;二、B+樹索引的使用
2.1索引的代價
在熟悉了B+樹索引原理之后，本篇文章的主題是嘮叨如何更好的使用索引，雖然索引是個好東西，可不能亂建，在介紹如何更好的使用索引之前先要了解一下使用這玩意兒的代價，它在空間和時間上都會拖后腿：
- 空間上的代價
這個是顯而易見的，每建立一個索引都要為它建立一棵B+樹，每一棵B+樹的每一個節點都是一個數據頁，一個頁默認會占用16KB的存儲空間，一棵很大的B+樹由許多數據頁組成，那可是很大的一片存儲空間呢。
- 時間上的代價
每次對表中的數據進行增、刪、改操作時，都需要去修改各個B+樹索引。而且我們講過，B+樹每層節點都是按照索引列的值從小到大的順序排序而組成了雙向鏈表。不論是葉子節點中的記錄，還是內節點中的記錄（也就是不論是用戶記錄還是目錄項記錄）都是按照索引列的值從小到大的順序而形成了一個單向鏈表。而增、刪、改操作可能會對節點和記錄的排序造成破壞，所以存儲引擎需要額外的時間進行一些記錄移位，頁面分裂、頁面回收啥的操作來維護好節點和記錄的排序。如果我們建了許多索引，每個索引對應的B+樹都要進行相關的維護操作，這還能不給性能拖后腿么？
所以說，一個表上索引建的越多，就會占用越多的存儲空間，在增刪改記錄的時候性能就越差。為了能建立又好又少的索引，我們先得學學這些索引在哪些條件下起作用的。
2.2B+樹索引適用的條件
下邊我們將嘮叨許多種讓B+樹索引發揮最大效能的技巧和注意事項，不過大家要清楚，所有的技巧都是源自你對B+樹索引本質的理解，所以如果你還不能保證對B+樹索引充分的理解，那么再次建議回過頭把前邊的內容看完了再來，要不然讀文章對你來說是一種折磨。首先，B+樹索引并不是萬能的，并不是所有的查詢語句都能用到我們建立的索引。下邊介紹幾個我們可能使用B+樹索引來進行查詢的情況。為了故事的順利發展，我們需要先創建一個表，這個表是用來存儲人的一些基本信息的：
CREATE TABLE person_info(id INT NOT NULL auto_increment,name VARCHAR(100) NOT NULL,birthday DATE NOT NULL,phone_number CHAR(11) NOT NULL,country varchar(100) NOT NULL,PRIMARY KEY (id),KEY idx_name_birthday_phone_number (name, birthday, phone_number) );對于這個person_info表我們需要注意兩點：
- 表中的主鍵是id列，它存儲一個自動遞增的整數。所以InnoDB存儲引擎會自動為id列建立聚簇索引。
- 我們額外定義了一個二級索引idx_name_birthday_phone_number，它是由3個列組成的聯合索引。所以在這個索引對應的B+樹的葉子節點處存儲的用戶記錄只保留name、birthday、phone_number這三個列的值以及主鍵id的值，并不會保存country列的值。
從這兩點注意中我們可以再次看到，一個表中有多少索引就會建立多少棵B+樹，person_info表會為聚簇索引和idx_name_birthday_phone_number索引建立2棵B+樹。下邊我們畫一下索引idx_name_birthday_phone_number的示意圖，不過既然我們已經掌握了InnoDB的B+樹索引原理，那我們在畫圖的時候為了讓圖更加清晰，所以在省略一些不必要的部分，比如記錄的額外信息，各頁面的頁號等等，其中內節點中目錄項記錄的頁號信息我們用箭頭來代替，在記錄結構中只保留name、birthday、phone_number、id這四個列的真實數據值，所以示意圖就長這樣（留心的同學看出來了，這其實和《高性能MySQL》里舉的例子的圖差不多，我覺得這個例子特別好，所以就借鑒了一下）：
為了方便大家理解，我們特意標明了哪些是內節點，哪些是葉子節點。再次強調一下，內節點中存儲的是目錄項記錄，葉子節點中存儲的是用戶記錄（由于不是聚簇索引，所以用戶記錄是不完整的，缺少country列的值）。從圖中可以看出，這個idx_name_birthday_phone_number索引對應的B+樹中頁面和記錄的排序方式就是這樣的：
- 先按照name列的值進行排序。
- 如果name列的值相同，則按照birthday列的值進行排序。
- 如果birthday列的值也相同，則按照phone_number的值進行排序。
這個排序方式十分、特別、非常、巨、very very very重要，因為只要頁面和記錄是排好序的，我們就可以通過二分法來快速定位查找。下邊的內容都仰仗這個圖了，大家對照著圖理解。
全值匹配
如果我們的搜索條件中的列和索引列一致的話，這種情況就稱為全值匹配，比方說下邊這個查找語句：
SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27' AND phone_number = '15123983239';我們建立的idx_name_birthday_phone_number索引包含的3個列在這個查詢語句中都展現出來了。大家可以想象一下這個查詢過程：
- 因為B+樹的數據頁和記錄先是按照name列的值進行排序的，所以先可以很快定位name列的值是Ashburn的記錄位置。
- 在name列相同的記錄里又是按照birthday列的值進行排序的，所以在name列的值是Ashburn的記錄里又可以快速定位birthday列的值是’1990-09-27’的記錄。
- 如果很不幸，name和birthday列的值都是相同的，那記錄是按照phone_number列的值排序的，所以聯合索引中的三個列都可能被用到。
有的同學也許有個疑問，WHERE子句中的幾個搜索條件的順序對查詢結果有啥影響么？也就是說如果我們調換name、birthday、phone_number這幾個搜索列的順序對查詢的執行過程有影響么？比方說寫成下邊這樣：
SELECT * FROM person_info WHERE birthday = '1990-09-27' AND phone_number = '15123983239' AND name = 'Ashburn';答案是：沒影響哈。MySQL有一個叫查詢優化器的東東，會分析這些搜索條件并且按照可以使用的索引中列的順序來決定先使用哪個搜索條件，后使用哪個搜索條件。我們后邊兒會有專門的章節來介紹查詢優化器，敬請期待。
匹配左邊的列
其實在我們的搜索語句中也可以不用包含全部聯合索引中的列，只包含左邊的就行，比方說下邊的查詢語句
SELECT * FROM person_info WHERE name = 'Ashburn';或者包含多個左邊的列也行：
SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27';那為什么搜索條件中必須出現左邊的列才可以使用到這個B+樹索引呢？比如下邊的語句就用不到這個B+樹索引么？
SELECT * FROM person_info WHERE birthday = '1990-09-27';是的，的確用不到，因為B+樹的數據頁和記錄先是按照name列的值排序的，在name列的值相同的情況下才使用birthday列進行排序，也就是說name列的值不同的記錄中birthday的值可能是無序的。而現在你跳過name列直接根據birthday的值去查找，臣妾做不到呀～ 那如果我就想在只使用birthday的值去通過B+樹索引進行查找咋辦呢？這好辦，你再對birthday列建一個B+樹索引就行了，創建索引的語法不用我嘮叨了吧。
但是需要特別注意的一點是，如果我們想使用聯合索引中盡可能多的列，搜索條件中的各個列必須是聯合索引中從最左邊連續的列。比方說聯合索引idx_name_birthday_phone_number中列的定義順序是name、birthday、phone_number，如果我們的搜索條件中只有name和phone_number，而沒有中間的birthday，比方說這樣：
SELECT * FROM person_info WHERE name = 'Ashburn' AND phone_number = '15123983239';這樣只能用到name列的索引，birthday和phone_number的索引就用不上了，因為name值相同的記錄先按照birthday的值進行排序，birthday值相同的記錄才按照phone_number值進行排序。
匹配列前綴
我們前邊說過為某個列建立索引的意思其實就是在對應的B+樹的記錄中使用該列的值進行排序，比方說person_info表上建立的聯合索引idx_name_birthday_phone_number會先用name列的值進行排序，所以這個聯合索引對應的B+樹中的記錄的name列的排列就是這樣的：
Aaron
Aaron
…
Aaron
Asa
Ashburn
…
Ashburn
Baird
Barlow
…
Barlow
字符串排序的本質就是比較哪個字符串大一點兒，哪個字符串小一點，比較字符串大小就用到了該列的字符集和比較規則，這個我們前邊兒嘮叨過，就不多嘮叨了。這里需要注意的是，一般的比較規則都是逐個比較字符的大小，也就是說我們比較兩個字符串的大小的過程其實是這樣的：
- 先比較字符串的第一個字符，第一個字符小的那個字符串就比較小。
- 如果兩個字符串的第一個字符相同，那就再比較第二個字符，第二個字符比較小的那個字符串就比較小。
- 如果兩個字符串的第二個字符也相同，那就接著比較第三個字符，依此類推。
所以一個排好序的字符串列其實有這樣的特點：
- 先按照字符串的第一個字符進行排序。
- 如果第一個字符相同再按照第二個字符進行排序。
- 如果第二個字符相同再按照第三個字符進行排序，依此類推。
也就是說這些字符串的前n個字符，也就是前綴都是排好序的，所以對于字符串類型的索引列來說，我們只匹配它的前綴也是可以快速定位記錄的，比方說我們想查詢名字以’As’開頭的記錄，那就可以這么寫查詢語句：
SELECT * FROM person_info WHERE name LIKE 'As%';但是需要注意的是，如果只給出后綴或者中間的某個字符串，比如這樣：
SELECT * FROM person_info WHERE name LIKE '%As%';MySQL就無法快速定位記錄位置了，因為字符串中間有’As’的字符串并沒有排好序，所以只能全表掃描了。有時候我們有一些匹配某些字符串后綴的需求，比方說某個表有一個url列，該列中存儲了許多url：
| www.baidu.com |
| www.google.com |
| www.gov.cn |
| … |
| www.wto.org |
假設已經對該url列創建了索引，如果我們想查詢以com為后綴的網址的話可以這樣寫查詢條件：WHERE url LIKE ‘%com’，但是這樣的話無法使用該url列的索引。為了在查詢時用到這個索引而不至于全表掃描，我們可以把后綴查詢改寫成前綴查詢，不過我們就得把表中的數據全部逆序存儲一下，也就是說我們可以這樣保存url列中的數據：
| moc.udiab.www |
| moc.elgoog.www |
| nc.vog.www |
| … |
| gro.otw.www |
這樣再查找以com為后綴的網址時搜索條件便可以這么寫：WHERE url LIKE ‘moc%’，這樣就可以用到索引了。
匹配范圍值
回頭看我們idx_name_birthday_phone_number索引的B+樹示意圖，所有記錄都是按照索引列的值從小到大的順序排好序的，所以這極大的方便我們查找索引列的值在某個范圍內的記錄。比方說下邊這個查詢語句：
SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';由于B+樹中的數據頁和記錄是先按name列排序的，所以我們上邊的查詢過程其實是這樣的：
- 通過B+樹在葉子節點中找到第一條name值大于Asa的二級索引記錄，讀取該記錄的主鍵值進行回表操作，獲得對應的聚簇索引記錄后發送給客戶端。
- 根據上一步找到的記錄，沿著記錄所在的鏈表向后查找（同一頁面中的記錄使用單向鏈表連接起來，數據頁之間用雙向鏈表連接起來）下一條二級索引記錄，判斷該記錄是否符合name < 'Barlow’條件，如果符合，則進行回表操作后發送至客戶端。
- 重復上一步驟，直到某條二級索引記錄不符合name <'Barlow’條件為止。
不過在使用聯合進行范圍查找的時候需要注意，如果對多個列同時進行范圍查找的話，只有對索引最左邊的那個列進行范圍查找的時候才能用到B+樹索引，比方說這樣
SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow' AND birthday > '1980-01-01';上邊這個查詢可以分成兩個部分：
這樣子對于聯合索引idx_name_birthday_phone_number來說，只能用到name列的部分，而用不到birthday列的部分，因為只有name值相同的情況下才能用birthday列的值進行排序，而這個查詢中通過name進行范圍查找的記錄中可能并不是按照birthday列進行排序的，所以在搜索條件中繼續以birthday列進行查找時是用不到這個B+樹索引的。
精確匹配某一列并范圍匹配另外一列
對于同一個聯合索引來說，雖然對多個列都進行范圍查找時只能用到最左邊那個索引列，但是如果左邊的列是精確查找，則右邊的列可以進行范圍查找，比方說這樣：
SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday > '1980-01-01' AND birthday < '2000-12-31' AND phone_number > '15100000000';這個查詢的條件可以分為3個部分：
同理，下邊的查詢也是可能用到這個idx_name_birthday_phone_number聯合索引的：
SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1980-01-01' AND phone_number > '15100000000';用于排序
我們在寫查詢語句的時候經常需要對查詢出來的記錄通過ORDER BY子句按照某種規則進行排序。一般情況下，我們只能把記錄都加載到內存中，再用一些排序算法，比如快速排序、歸并排序、吧啦吧啦排序等等在內存中對這些記錄進行排序，有的時候可能查詢的結果集太大以至于不能在內存中進行排序的話，還可能暫時借助磁盤的空間來存放中間結果，排序操作完成后再把排好序的結果集返回到客戶端。在MySQL中，把這種在內存中或者磁盤上進行排序的方式統稱為文件排序（英文名：filesort），跟文件這個詞兒一沾邊兒，就顯得這些排序操作非常慢了（磁盤和內存的速度比起來，就像是飛機和蝸牛的對比）。但是如果ORDER BY子句里使用到了我們的索引列，就有可能省去在內存或文件中排序的步驟，比如下邊這個簡單的查詢語句：
SELECT * FROM person_info ORDER BY name, birthday, phone_number LIMIT 10;這個查詢的結果集需要先按照name值排序，如果記錄的name值相同，則需要按照birthday來排序，如果birthday的值相同，則需要按照phone_number排序。大家可以回過頭去看我們建立的idx_name_birthday_phone_number索引的示意圖，因為這個B+樹索引本身就是按照上述規則排好序的，所以直接從索引中提取數據，然后進行回表操作取出該索引中不包含的列就好了。簡單吧？是的，索引就是這么牛逼。
使用聯合索引進行排序注意事項
對于聯合索引有個問題需要注意，ORDER BY的子句后邊的列的順序也必須按照索引列的順序給出，如果給出ORDER BY phone_number, birthday, name的順序，那也是用不了B+樹索引，這種顛倒順序就不能使用索引的原因我們上邊詳細說過了，這就不贅述了。
同理，ORDER BY name、ORDER BY name, birthday這種匹配索引左邊的列的形式可以使用部分的B+樹索引。當聯合索引左邊列的值為常量，也可以使用后邊的列進行排序，比如這樣：
SELECT * FROM person_info WHERE name = 'A' ORDER BY birthday, phone_number LIMIT 10;這個查詢能使用聯合索引進行排序是因為name列的值相同的記錄是按照birthday, phone_number排序的，說了好多遍了都。
2.3不可以使用索引進行排序的幾種情況
ASC、DESC混用
對于使用聯合索引進行排序的場景，我們要求各個排序列的排序順序是一致的，也就是要么各個列都是ASC規則排序，要么都是DESC規則排序。
為啥會有這種奇葩規定呢？這個還得回頭想想這個idx_name_birthday_phone_number聯合索引中記錄的結構：
- 先按照記錄的name列的值進行升序排列。
- 如果記錄的name列的值相同，再按照birthday列的值進行升序排列。
- 如果記錄的birthday列的值相同，再按照phone_number列的值進行升序排列。
如果查詢中的各個排序列的排序順序是一致的，比方說下邊這兩種情況：
- ORDER BY name, birthday LIMIT 10
這種情況直接從索引的最左邊開始往右讀10行記錄就可以了。
- ORDER BY name DESC, birthday DESC LIMIT 10，
這種情況直接從索引的最右邊開始往左讀10行記錄就可以了。
但是如果我們查詢的需求是先按照name列進行升序排列，再按照birthday列進行降序排列的話，比如說這樣的查詢語句：
SELECT * FROM person_info ORDER BY name, birthday DESC LIMIT 10;這樣如果使用索引排序的話過程就是這樣的：
- 先從索引的最左邊確定name列最小的值，然后找到name列等于該值的所有記錄，然后從name列等于該值的最右邊的那條記錄開始往左找10條記錄。
- 如果name列等于最小的值的記錄不足10條，再繼續往右找name值第二小的記錄，重復上邊那個過程，直到找到10條記錄為止。
累不累？累！重點是這樣不能高效使用索引，而要采取更復雜的算法去從索引中取數據，設計MySQL的大叔覺得這樣還不如直接文件排序來的快，所以就規定使用聯合索引的各個排序列的排序順序必須是一致的。
排序列包含非同一個索引的列
有時候用來排序的多個列不是一個索引里的，這種情況也不能使用索引進行排序，比方說：
SELECT * FROM person_info ORDER BY name, country LIMIT 10;name和country并不屬于一個聯合索引中的列，所以無法使用索引進行排序，至于為啥我就不想再嘮叨了，自己用前邊的理論自己捋一捋吧～
排序列使用了復雜的表達式
要想使用索引進行排序操作，必須保證索引列是以單獨列的形式出現，而不是修飾過的形式，比方說這樣：
SELECT * FROM person_info ORDER BY UPPER(name) LIMIT 10;使用了UPPER函數修飾過的列就不是單獨的列啦，這樣就無法使用索引進行排序啦。
用于分組
有時候我們為了方便統計表中的一些信息，會把表中的記錄按照某些列進行分組。比如下邊這個分組查詢：
SELECT name, birthday, phone_number, COUNT(*) FROM person_info GROUP BY name, birthday, phone_number這個查詢語句相當于做了3次分組操作：
然后針對那些小小分組進行統計，比如在我們這個查詢語句中就是統計每個小小分組包含的記錄條數。如果沒有索引的話，這個分組過程全部需要在內存里實現，而如果有了索引的話，恰巧這個分組順序又和我們的B+樹中的索引列的順序是一致的，而我們的B+樹索引又是按照索引列排好序的，這不正好么，所以可以直接使用B+樹索引進行分組。
和使用B+樹索引進行排序是一個道理，分組列的順序也需要和索引列的順序一致，也可以只使用索引列中左邊的列進行分組，吧啦吧啦的～
2.4回表的代價
上邊的討論對回表這個詞兒多是一帶而過，可能大家沒啥深刻的體會，下邊我們詳細嘮叨下。還是用idx_name_birthday_phone_number索引為例，看下邊這個查詢：
SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';在使用idx_name_birthday_phone_number索引進行查詢時大致可以分為這兩個步驟：
由于索引idx_name_birthday_phone_number對應的B+樹中的記錄首先會按照name列的值進行排序，所以值在Asa～Barlow之間的記錄在磁盤中的存儲是相連的，集中分布在一個或幾個數據頁中，我們可以很快的把這些連著的記錄從磁盤中讀出來，這種讀取方式我們也可以稱為順序I/O。根據第1步中獲取到的記錄的id字段的值可能并不相連，而在聚簇索引中記錄是根據id（也就是主鍵）的順序排列的，所以根據這些并不連續的id值到聚簇索引中訪問完整的用戶記錄可能分布在不同的數據頁中，這樣讀取完整的用戶記錄可能要訪問更多的數據頁，這種讀取方式我們也可以稱為隨機I/O。一般情況下，順序I/O比隨機I/O的性能高很多，所以步驟1的執行可能很快，而步驟2就慢一些。所以這個使用索引idx_name_birthday_phone_number的查詢有這么兩個特點：
- 會使用到兩個B+樹索引，一個二級索引，一個聚簇索引。
- 訪問二級索引使用順序I/O，訪問聚簇索引使用隨機I/O
需要回表的記錄越多，使用二級索引的性能就越低，甚至讓某些查詢寧愿使用全表掃描也不使用二級索引。比方說name值在Asa～Barlow之間的用戶記錄數量占全部記錄數量90%以上，那么如果使用idx_name_birthday_phone_number索引的話，有90%多的id值需要回表，這不是吃力不討好么，還不如直接去掃描聚簇索引（也就是全表掃描）。
那什么時候采用全表掃描的方式，什么時候使用采用二級索引 + 回表的方式去執行查詢呢？這個就是傳說中的查詢優化器做的工作，查詢優化器會事先對表中的記錄計算一些統計數據，然后再利用這些統計數據根據查詢的條件來計算一下需要回表的記錄數，需要回表的記錄數越多，就越傾向于使用全表掃描，反之傾向于使用二級索引 + 回表的方式。當然優化器做的分析工作不僅僅是這么簡單，但是大致上是個這個過程。一般情況下，限制查詢獲取較少的記錄數會讓優化器更傾向于選擇使用二級索引 + 回表的方式進行查詢，因為回表的記錄越少，性能提升就越高，比方說上邊的查詢可以改寫成這樣：
SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow' LIMIT 10;添加了LIMIT 10的查詢更容易讓優化器采用二級索引 + 回表的方式進行查詢。
對于有排序需求的查詢，上邊討論的采用全表掃描還是二級索引 + 回表的方式進行查詢的條件也是成立的，比方說下邊這個查詢：
SELECT * FROM person_info ORDER BY name, birthday, phone_number;由于查詢列表是*，所以如果使用二級索引進行排序的話，需要把排序完的二級索引記錄全部進行回表操作，這樣操作的成本還不如直接遍歷聚簇索引然后再進行文件排序（filesort）低，所以優化器會傾向于使用全表掃描的方式執行查詢。如果我們加了LIMIT子句，比如這樣：
SELECT * FROM person_info ORDER BY name, birthday, phone_number LIMIT 10;這樣需要回表的記錄特別少，優化器就會傾向于使用二級索引 + 回表的方式執行查詢。
覆蓋索引
為了徹底告別回表操作帶來的性能損耗，我們建議：最好在查詢列表里只包含索引列，比如這樣：
SELECT name, birthday, phone_number FROM person_info WHERE name > 'Asa' AND name < 'Barlow'因為我們只查詢name, birthday, phone_number這三個索引列的值，所以在通過idx_name_birthday_phone_number索引得到結果后就不必到聚簇索引中再查找記錄的剩余列，也就是country列的值了，這樣就省去了回表操作帶來的性能損耗。我們把這種只需要用到索引的查詢方式稱為索引覆蓋。排序操作也優先使用覆蓋索引的方式進行查詢，比方說這個查詢：
SELECT name, birthday, phone_number FROM person_info ORDER BY name, birthday, phone_number;雖然這個查詢中沒有LIMIT子句，但是采用了覆蓋索引，所以查詢優化器就會直接使用idx_name_birthday_phone_number索引進行排序而不需要回表操作了。
當然，如果業務需要查詢出索引以外的列，那還是以保證業務需求為重。但是我們很不鼓勵用*號作為查詢列表，最好把我們需要查詢的列依次標明。
2.5如何挑選索引
上邊我們以idx_name_birthday_phone_number索引為例對索引的適用條件進行了詳細的嘮叨，下邊看一下我們在建立索引時或者編寫查詢語句時就應該注意的一些事項。
只為用于搜索、排序或分組的列創建索引
也就是說，只為出現在WHERE子句中的列、連接子句中的連接列，或者出現在ORDER BY或GROUP BY子句中的列創建索引。而出現在查詢列表中的列就沒必要建立索引了：
SELECT birthday, country FROM person_name WHERE name = 'Ashburn';像查詢列表中的birthday、country這兩個列就不需要建立索引，我們只需要為出現在WHERE子句中的name列創建索引就可以了。
考慮列的基數
列的基數指的是某一列中不重復數據的個數，比方說某個列包含值2, 5, 8, 2, 5, 8, 2, 5, 8，雖然有9條記錄，但該列的基數卻是3。也就是說，在記錄行數一定的情況下，列的基數越大，該列中的值越分散，列的基數越小，該列中的值越集中。這個列的基數指標非常重要，直接影響我們是否能有效的利用索引。假設某個列的基數為1，也就是所有記錄在該列中的值都一樣，那為該列建立索引是沒有用的，因為所有值都一樣就無法排序，無法進行快速查找了～ 而且如果某個建立了二級索引的列的重復值特別多，那么使用這個二級索引查出的記錄還可能要做回表操作，這樣性能損耗就更大了。所以結論就是：最好為那些列的基數大的列建立索引，為基數太小列的建立索引效果可能不好
索引列的類型盡量小
我們在定義表結構的時候要顯式的指定列的類型，以整數類型為例，有TINYINT、MEDIUMINT、INT、BIGINT這么幾種，它們占用的存儲空間依次遞增，我們這里所說的類型大小指的就是該類型表示的數據范圍的大小。能表示的整數范圍當然也是依次遞增，如果我們想要對某個整數列建立索引的話，在表示的整數范圍允許的情況下，盡量讓索引列使用較小的類型，比如我們能使用INT就不要使用BIGINT，能使用MEDIUMINT就不要使用INT～ 這是因為：
- 數據類型越小，在查詢時進行的比較操作越快（這是CPU層次的東東）
- 數據類型越小，索引占用的存儲空間就越少，在一個數據頁內就可以放下更多的記錄，從而減少磁盤I/O帶來的性能損耗，也就意味著可以把更多的數據頁緩存在內存中，從而加快讀寫效率。
這個建議對于表的主鍵來說更加適用，因為不僅是聚簇索引中會存儲主鍵值，其他所有的二級索引的節點處都會存儲一份記錄的主鍵值，如果主鍵適用更小的數據類型，也就意味著節省更多的存儲空間和更高效的I/O。
索引字符串值的前綴
我們知道一個字符串其實是由若干個字符組成，如果我們在MySQL中使用utf8字符集去存儲字符串的話，編碼一個字符需要占用1~3個字節。假設我們的字符串很長，那存儲一個字符串就需要占用很大的存儲空間。在我們需要為這個字符串列建立索引時，那就意味著在對應的B+樹中有這么兩個問題：
- B+樹索引中的記錄需要把該列的完整字符串存儲起來，而且字符串越長，在索引中占用的存儲空間越大。
- 如果B+樹索引中索引列存儲的字符串很長，那在做字符串比較時會占用更多的時間。
我們前邊兒說過索引列的字符串前綴其實也是排好序的，所以索引的設計者提出了個方案 — 只對字符串的前幾個字符進行索引也就是說在二級索引的記錄中只保留字符串前幾個字符。這樣在查找記錄時雖然不能精確的定位到記錄的位置，但是能定位到相應前綴所在的位置，然后根據前綴相同的記錄的主鍵值回表查詢完整的字符串值，再對比就好了。這樣只在B+樹中存儲字符串的前幾個字符的編碼，既節約空間，又減少了字符串的比較時間，還大概能解決排序的問題，何樂而不為，比方說我們在建表語句中只對name列的前10個字符進行索引可以這么寫：
CREATE TABLE person_info(name VARCHAR(100) NOT NULL,birthday DATE NOT NULL,phone_number CHAR(11) NOT NULL,country varchar(100) NOT NULL,KEY idx_name_birthday_phone_number (name(10), birthday, phone_number) );name(10)就表示在建立的B+樹索引中只保留記錄的前10個字符的編碼，這種只索引字符串值的前綴的策略是我們非常鼓勵的，尤其是在字符串類型能存儲的字符比較多的時候。
索引列前綴對排序的影響
如果使用了索引列前綴，比方說前邊只把name列的前10個字符放到了二級索引中，下邊這個查詢可能就有點兒尷尬了：
SELECT * FROM person_info ORDER BY name LIMIT 10;因為二級索引中不包含完整的name列信息，所以無法對前十個字符相同，后邊的字符不同的記錄進行排序，也就是使用索引列前綴的方式無法支持使用索引排序，只好乖乖的用文件排序嘍。
讓索引列在比較表達式中單獨出現
假設表中有一個整數列my_col，我們為這個列建立了索引。下邊的兩個WHERE子句雖然語義是一致的，但是在效率上卻有差別：
第1個WHERE子句中my_col列并不是以單獨列的形式出現的，而是以my_col * 2這樣的表達式的形式出現的，存儲引擎會依次遍歷所有的記錄，計算這個表達式的值是不是小于4，所以這種情況下是使用不到為my_col列建立的B+樹索引的。而第2個WHERE子句中my_col列并是以單獨列的形式出現的，這樣的情況可以直接使用B+樹索引。
所以結論就是：如果索引列在比較表達式中不是以單獨列的形式出現，而是以某個表達式，或者函數調用形式出現的話，是用不到索引的。
主鍵插入順序
我們知道，對于一個使用InnoDB存儲引擎的表來說，在我們沒有顯式的創建索引時，表中的數據實際上都是存儲在聚簇索引的葉子節點的。而記錄又是存儲在數據頁中的，數據頁和記錄又是按照記錄主鍵值從小到大的順序進行排序，所以如果我們插入的記錄的主鍵值是依次增大的話，那我們每插滿一個數據頁就換到下一個數據頁繼續插，而如果我們插入的主鍵值忽大忽小的話，這就比較麻煩了，假設某個數據頁存儲的記錄已經滿了，它存儲的主鍵值在1~100之間：
如果此時再插入一條主鍵值為9的記錄，那它插入的位置就如下圖：
可這個數據頁已經滿了啊，再插進來咋辦呢？我們需要把當前頁面分裂成兩個頁面，把本頁中的一些記錄移動到新創建的這個頁中。頁面分裂和記錄移位意味著什么？意味著：性能損耗！所以如果我們想盡量避免這樣無謂的性能損耗，最好讓插入的記錄的主鍵值依次遞增，這樣就不會發生這樣的性能損耗了。所以我們建議：讓主鍵具有AUTO_INCREMENT，讓存儲引擎自己為表生成主鍵，而不是我們手動插入 ，比方說我們可以這樣定義person_info表：
CREATE TABLE person_info(id INT UNSIGNED NOT NULL AUTO_INCREMENT,name VARCHAR(100) NOT NULL,birthday DATE NOT NULL,phone_number CHAR(11) NOT NULL,country varchar(100) NOT NULL,PRIMARY KEY (id),KEY idx_name_birthday_phone_number (name(10), birthday, phone_number) );我們自定義的主鍵列id擁有AUTO_INCREMENT屬性，在插入記錄時存儲引擎會自動為我們填入自增的主鍵值。
冗余和重復索引
有時候有的同學有意或者無意的就對同一個列創建了多個索引，比方說這樣寫建表語句：
CREATE TABLE person_info(id INT UNSIGNED NOT NULL AUTO_INCREMENT,name VARCHAR(100) NOT NULL,birthday DATE NOT NULL,phone_number CHAR(11) NOT NULL,country varchar(100) NOT NULL,PRIMARY KEY (id),KEY idx_name_birthday_phone_number (name(10), birthday, phone_number),KEY idx_name (name(10)) );我們知道，通過idx_name_birthday_phone_number索引就可以對name列進行快速搜索，再創建一個專門針對name列的索引就算是一個冗余索引，維護這個索引只會增加維護的成本，并不會對搜索有什么好處。
另一種情況，我們可能會對某個列重復建立索引，比方說這樣：
CREATE TABLE repeat_index_demo (c1 INT PRIMARY KEY,c2 INT,UNIQUE uidx_c1 (c1),INDEX idx_c1 (c1) );我們看到，c1既是主鍵、又給它定義為一個唯一索引，還給它定義了一個普通索引，可是主鍵本身就會生成聚簇索引，所以定義的唯一索引和普通索引是重復的，這種情況要避免。
2.6總結
上邊只是我們在創建和使用B+樹索引的過程中需要注意的一些點，后邊我們還會陸續介紹更多的優化方法和注意事項，敬請期待。本集內容總結如下：
B+樹索引在空間和時間上都有代價，所以沒事兒別瞎建索引。
B+樹索引適用于下邊這些情況：
- 全值匹配
- 匹配左邊的列
- 匹配范圍值
- 精確匹配某一列并范圍匹配另外一列
- 用于排序
- 用于分組
- 只為用于搜索、排序或分組的列創建索引
- 為列的基數大的列創建索引
- 索引列的類型盡量小
- 可以只對字符串值的前綴建立索引
- 只有索引列在比較表達式中單獨出現才可以適用索引
- 為了盡可能少的讓聚簇索引發生頁面分裂和記錄移位的情況，建議讓主鍵擁有AUTO_INCREMENT屬性。
- 定位并刪除表中的重復和冗余索引
- 盡量使用覆蓋索引進行查詢，避免回表帶來的性能損耗。
總結
- 上一篇： monkeyrunner自动化测试工具-
- 下一篇： 详解设计模式：享元模式