一.前言：
在我們的生活中，導出可以看到索引效果的應用，如在火車站觀看的車次表、字典的目錄等。它們的作用就是索引的作用，通過不斷的縮小想要獲得數據的范圍來篩選出最終想要的結果，同時把隨機的事件變成順序的事件，也就是我們總是通過同一種查找方式來鎖定數據(字典的A-Z查找)。
生活舉例-乘火車：我去乘火車回老家，如果要坐火車時沒有車次表，最壞的結果我要跑遍每一個火車停靠點才能找到我要坐的火車；但是有了時刻表，我能快速知道我要做的火車在哪里停靠，可以直接奔向那里去，而不是一個一個過去看看是否為我要做的列車，從而加快訪問的速度。這個車次表，就是數據庫的索引。
二.磁盤原理：
這一部分文字理論比較多，看著還頭疼，有興趣也可看看，沒興趣也不影響后邊篇章的閱讀，只要記住本部分的一個結論即可：
讀取數據盡可能的【減少與操作系統I/O交互的次數】。
好了沒興趣的可以跳過了，到下一部分了。
數據庫實現比較復雜，數據保存在磁盤上，而為了提高性能，每次又可以把部分數據讀入內存來計算，因為我們知道訪問磁盤的成本大概是訪問內存的十萬倍左右，所以簡單的搜索樹難以滿足復雜的應用場景。前面提到了訪問磁盤，那么這里先簡單介紹一下磁盤IO和預讀，磁盤讀取數據靠的是機械運動，每次讀取數據花費的時間可以分為尋道時間、旋轉延遲、傳輸時間三個部分，
? ? a)·尋道時間：磁臂移動到指定磁道所需要的時間，主流磁盤一般在5ms以下； b)旋轉延遲：就是我們經常聽說的磁盤轉速，比如一個磁盤7200轉，表示每分鐘能轉7200次，也就是說1秒鐘能轉120次，旋轉延遲就是1/120/2 = 4.17ms； c).傳輸時間：指的是從磁盤讀出或將數據寫入磁盤的時間，一般在零點幾毫秒，相對于前兩個時間可以忽略不計。
? ? (看過一篇很詳細文章：http://wdxtub.com/2016/04/16/thin-csapp-3/）
那么訪問一次磁盤的時間，即一次磁盤IO的時間約等于5+4.17 = 9ms左右，聽起來還挺不錯的，但要知道一臺500-MIPS(Million Instructions Per Second每秒百萬指令數)的機器每秒可以執行5億條指令，因為指令依靠的是電的性質，換句話說執行一次IO的時間可以執行40萬條指令，數據庫動輒十萬百萬乃至千萬級數據，每次9毫秒的時間，顯然是個災難。
所以，結論:減少操作系統I/O交互的次數。
(每一次IO讀取的數據我們稱之為一頁(page)。具體一頁有多大數據跟操作系統有關，一般為4k或8k，也就是我們讀取一頁內的數據時候，實際上才發生了一次IO)
三.什么是索引：
在數據庫系統的使用過程當中，數據的查詢是使用最頻繁的一種數據操作。
????????最基本的查詢算法當然是順序查找（linear search），遍歷表然后逐行匹配行值是否等于待查找的關鍵字，其時間復雜度為O（n）。但時間復雜度為O（n）的算法規模小的表，負載輕的數據庫，也能有好的性能。??但是數據增大的時候，時間復雜度為O（n）的算法顯然是糟糕的，性能就很快下降了。
???????好在計算機科學的發展提供了很多更優秀的查找算法，例如二分查找（binary search）、二叉樹查找（binary tree search）等。如果稍微分析一下會發現，每種查找算法都只能應用于特定的數據結構之上，例如二分查找要求被檢索數據有序，而二叉樹查找只能應用于二叉查找樹上，但是數據本身的組織結構不可能完全滿足各種數據結構（例如，理論上不可能同時將兩列都按順序進行組織），所以，在數據之外，數據庫系統還維護著滿足特定查找算法的數據結構，這些數據結構以某種方式引用（指向）數據，這樣就可以在這些數據結構上實現高級查找算法。這種數據結構，就是索引。
四.MySQL的B-Tree索引（技術上說B+Tree）
好，本篇的核心來了！
在 MySQL 中，主要有四種類型的索引，分別為： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。我們主要分析B-Tree 索引。（ B：balace 平衡之意，并非binary tree 二叉樹）
1.詳解b+樹數據結構
上圖，是一顆b+tree，（innodb引擎下的，與myisam引擎下的B+結構又不一樣，說白了就是聚簇索引與非聚簇索引的區別，詳細見：
Mysql-聚簇索引
淺藍色的塊我們稱之為一個磁盤塊，可以看到每個磁盤塊包含幾個數據項（深藍色所示，范圍： [(M/2)-1, M-1] M為總數據）和指針（黃色所示），如磁盤塊1包含數據項17和35，包含指針P1、P2、P3，P1表示小于17的磁盤塊，P2表示在17和35之間的磁盤塊，P3表示大于35的磁盤塊。真實的數據存在于葉子節點即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非葉子節點只不存儲真實的數據(B+的特點)，只存儲指引搜索方向的數據項，如17、35并不真實存在于數據表中。
2.B+樹的查找過程
如圖所示，如果要查找數據項29，那么首先會把磁盤塊1由磁盤加載到內存，此時發生一次IO，在內存中用二分查找確定29在17和35之間，鎖定磁盤塊1的P2指針，內存時間因為非常短（相比磁盤的IO）可以忽略不計，通過磁盤塊1的P2指針的磁盤地址把磁盤塊3由磁盤加載到內存，發生第二次IO，29在26和30之間，鎖定磁盤塊3的P2指針，通過指針加載磁盤塊8到內存，發生第三次IO，同時內存中做二分查找找到29，結束查詢，總計三次IO。
真實的情況是，3層的b+樹可以表示上百萬的數據，如果上百萬的數據查找只需要三次IO，性能提高將是巨大的，如果沒有索引，每個數據項都要發生一次IO，那么總共需要百萬次的IO，顯然成本非常非常高。
（疑問？？？，如上所述，INNOBD的B+樹是聚簇索引類型的，真實數據與索引葉子節點放在一起，那么問題來了，我弱有多個索引，難不成每個索引下邊都存儲有數據？？那豈不是浪費磁盤存儲？若不是的話，我猜測是使用指針指過去的嗎，怎么用數據結構來表示一下？？）
答：每張表只能有一個聚集索引，可以有多個輔助索引。輔助索引也就是次索引，在根節點會存儲的不是數據而是一個指針指向存儲數據的主索引。
3.b+樹性質
1). 通過上面的分析，我們知道IO次數取決于b+數的高度h，假設當前數據表的數據為N，每個磁盤塊的數據項的數量是m，則有h=㏒(m+1)N，當數據量N一定的情況下，m越大，h越小；而m = 磁盤塊的大小 / 數據項的大小，磁盤塊的大小也就是一個數據頁的大小，是固定的，如果數據項占的空間越小，數據項的數量越多，樹的高度h越低，I/O也就少。這就是為什么每個數據項，即索引字段要盡量的小。
舉個反面教材，比如int占4字節，要比bigint8字節少一半。這也是為什么b+樹要求把真實的數據放到葉子節點而不是內層節點，一旦放到內層節點，磁盤塊的數據項會大幅度下降(原理見上邊二)，導致樹增高。當數據項等于1時將會退化成線性表。如下：
如果是左邊的結構，I/O次數為三次；如果是右邊的線性表，I/O次數為6次，很明顯嘛IO變多了
映射兩個結論：
1.要設置成索引的字段len要小；
2.做聯合索引時，聯合的字段個數也要少
2).當b+樹的數據項是復合的數據結構(多列索引)，比如(name,age,sex)的時候，b+數是按照從左到右的順序來建立搜索樹的。
比如當(張三,20,F)這樣的數據來檢索的時候，b+樹會優先比較name來確定下一步的所搜方向，如果name相同再依次比較age和sex，最后得到檢索的數據；但當(20,F)這樣的沒有name的數據來的時候，b+樹就不知道下一步該查哪個節點，因為建立搜索樹的時候name就是第一個比較因子，必須要先根據name來搜索才能知道下一步去哪里查詢。
比如當(張三,F)這樣的數據來檢索時，b+樹可以用name來指定搜索方向，但下一個字段age的缺失，所以只能把名字等于張三的數據都找到，然后再匹配性別是F的數據了， 這個是非常重要的性質，即索引的最左匹配特性。
映射兩個結論：
1.最左匹配特性，聯合索引是從左往右讀的
2.如果有了多列索引，那么從左往右一次的索引不需要建立 (a,b,c) 那么 (a),(a,b)就不用建立了
3. 更多結論 ： Mysql-索引總結 http://blog.csdn.net/ty_hf/article/details/53526405
以上就是?Mysql-索引數據結構的內容，更多相關內容請關注PHP中文網（www.php.cn）！
