1. 首頁 > 生活百科 > >

4 MySQL學習---MySQL索引( 二 )

生活百科


毫無疑問，平衡二叉樹的查找效率是非常高的 。但是當數據量非常大，樹存儲的元素數量是有限的的，這樣會導致平衡二叉樹的平均深度過大而造成磁盤IO讀寫過于頻繁，進而導致查詢效率低下 。另外數據量過大會導致內存空間不夠容納平衡二叉樹所有節點的情況 。

時間復雜度和樹高相關 。樹有多高就需要檢索多少次 ， 每個節點的讀??，都夒sσ淮未排?IO 操 作 。樹的高度就等于每次查詢數據時磁盤 IO 操作的次數 。磁盤每次尋道時間為10ms，在表數據量大時，查詢性能就會很差 。（1百萬的數據量，log2n約等于20次磁盤IO ， 時間20*10=0.2s）
平衡二叉樹不支持范圍查詢快速查找 ， 范圍查詢時需要從根節點多次遍歷 ， 查詢效率不高 。
B樹是解決這個問題的很好的數據結構 。
前置知識：磁盤IO與預讀上文提到了磁盤訪問，這里簡單介紹一下磁盤IO和預讀，磁盤讀取數據靠的是機械運動，每次讀取數據花費的時間可以分為尋道時間、旋轉延遲、傳輸時間三個部分：
尋道時間指的是磁臂移動到指定磁道所需要的時間，主流磁盤一般在5ms以下；旋轉延遲就是我們經常說的磁盤轉速磁盤轉速，比如一個磁盤7200轉/min，表示每分鐘能轉7200次，也就是說一秒能轉120次，旋轉延遲就是1/120/2=4.17ms，也就是半圈的時間（這里有兩個時間：平均尋道時間 ， 受限于目前的物理水平，大概是5ms的時間，找到磁道了，還需要找到你數據存在的那個點，尋點時間，這尋點時間的一個平均值就是半圈的時間，這個半圈時間叫做平均延遲時間，那么平均延遲時間加上平均尋道時間就是你找到一個數據所消耗的平均時間，大概9ms，其實機械硬盤慢主要是慢在這兩個時間上了，當找到數據然后把數據拷貝到內存的時間是非常短暫的，和光速差不多了）；傳輸時間指的是從磁盤讀出或將數據寫入磁盤的時間，一般在零點幾毫秒，相對于前兩個時間可以忽略不計 。
那么訪問一次磁盤的時間，即一次磁盤IO的時間約等于5+4.17=9ms左右，聽起來還挺不錯的，但要知道一臺500-MIPS（Million Instructions Per Second）的機器每秒可以執行5億條指令，因為指令依靠的是電的性質，換句話說執行一次IO的消耗的時間段下cpu可以執行約450萬條指令 ， 數據庫動輒十萬百萬乃至千萬級數據 ， 每次9毫秒的時間 ， 顯然是個災難 ， 所以我們要想辦法降低IO次數 。下圖是計算機硬件延遲的對比圖，供大家參考：
4 MySQL學習---MySQL索引

文章插圖
考慮到磁盤IO是非常高昂的操作，計算機操作系統做了一些優化，當一次IO時 ， 不光把當前磁盤地址的數據 ， 而是把相鄰的數據也都讀取到內存緩沖區內，因為局部預讀性原理告訴我們，當計算機訪問一個地址的數據的時候，與其相鄰的數據也會很快被訪問到 。每一次IO讀取的數據我們稱之為一頁（page） 。具體一頁有多大數據跟操作系統有關，一般為4KB或8KB，也就是我們讀取一頁內的數據時候，實際上才發生了一次IO ， 這個理論對于索引的數據結構設計非常有幫助 。
B樹（平衡二叉樹的改造）的引入對于平衡二叉樹，考慮到磁盤IO對查詢數據效率的影響，我們更希望出現“矮胖”而不是“瘦高”樹，因為這樣可以顯著減少查詢時的IO次數，增加查詢效率 。那么我們如何能夠降低樹的高度呢？
假如key為8字節（bigint類型），每個節點有兩個指針，每個指針為4個字節（B），一個節點占用的空間16個字節（8+4*2=16）
因為在MySQL的InnoDB存儲引擎一次IO會讀取的一頁（默認一頁16KB）的數據量 ， 而二叉樹一次IO有效數據量只有16字節，空間利用率極低 。為了最大化利用一次IO空間 ， 一個簡單的想法是在每個節點存儲多個元素，在每個節點盡可能多的存儲數據 。每個節點可以存儲1000個索引（16kB/16B=1000），這樣就將二叉樹改造成了多叉樹，通過增加樹的叉樹，將樹從高瘦變為矮胖 。構建100萬條數據 ， 樹的高度只需要2層就可以（1000*1000=106），也就是說只需要2次磁盤IO就可以查詢到數據 。磁盤IO次數變少了，查詢數據的效率也就提高了 。、
B樹又叫多路平衡樹，通常我們所說的m階/m叉的B樹，它必須滿足以下條件：