首頁 > 資料庫 > mysql教程 > Mysql-索引資料結構

Mysql-索引資料結構

黄舟
發布: 2017-01-20 17:03:37
原創
1235 人瀏覽過

一.前言:

在我們的生活中,導出可以看到索引效果的應用,如在火車站觀看的車次表、字典的目錄等。它們的作用就是索引的作用,透過不斷的縮小想要獲得資料的範圍來篩選出最終想要的結果,同時把隨機的事件變成順序的事件,也就是我們總是透過同一種查找方式來鎖定資料(字典的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的磁碟區塊。不儲存真實的資料(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.做聯合索引時,聯合的字段數也要少

Mysql-索引資料結構

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中文網(m.sbmmt.com)!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板