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+樹數據結構

Mysql-索引數據結構

上圖,是一顆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時將會退化成線性表。如下:

Mysql-索引數據結構

如果是左邊的結構,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)!

? 版權聲明
THE END
喜歡就支持一下吧
點贊6 分享