Mysql-索引資料結構

一.前言：

在我們的生活中，導出可以看到索引效果的應用，如在火車站觀看的車次表、字典的目錄等。它們的作用就是索引的作用，透過不斷的縮小想要獲得資料的範圍來篩選出最終想要的結果，同時把隨機的事件變成順序的事件，也就是我們總是透過同一種查找方式來鎖定資料(字典的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的磁碟區塊。不儲存真實的資料(B+的特點)，只儲存指引搜尋方向的資料項，如17、35並不真實存在於資料表中。示，如果要查找資料項29，那麼首先會把磁碟區塊1由磁碟加載到內存，此時發生一次IO，在內存中用二分查找確定29在17和35之間，鎖定磁碟塊1的P2指針，內存時間因為非常短（相比磁碟的IO）可以忽略不計，透過磁碟區塊1的P2指標的磁碟位址把磁碟區塊3由磁碟載入到內存，發生第二次IO，29在26和30之間，鎖定磁碟區塊3的P2指針，透過指針載入磁碟區塊8到內存，發生第三次IO，同時記憶體中做二分查找找到29，結束查詢，總計三次IO。 b+樹可以表示百萬的數據，如果上百萬的數據查找只需要三次IO，性能提高將是巨大的，如果沒有索引，每個數據項都要發生一次IO，那麼總共需要百萬次的IO，顯然成本非常非常高。個索引，難不成每個索引下邊都儲存有資料？每張表只能有一個聚集索引，可以有多個輔助索引。

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）！