關于MySQL的索引機制

正确建立合适的索引是資料庫優化的基礎

全值比對我最愛, 最左字首要遵守

帶頭大哥不能死, 中間兄弟不能斷

索引列上少計算, 範圍之後全失效

Like百分寫最後, 覆寫索引不寫 *

不等空置還有or, 索引失效要少用

索引的本質

索引是為了加速對表中資料行的檢索而建立的一種分散存儲的資料結構

在關系型資料庫管理系統( RDBMS )中, 資料的索引( 大部分 )都是硬碟級索引( InnoDB中少部分加載在記憶體中 )

索引的工作機制

資料結構的性能特點, 決定了資料的檢索性能

若未建立索引, 就會執行全表掃描, 0(n) 的時間複雜度, 建立索引後可以根據id快速定位磁盤位址

資料結構:

hash表

hash索引( key進行hashcode 得到一個數組的下标 )的優劣勢:

基于下标檢索, 查詢快( 時間複雜度為0(1), 要麼命中要麼不命中 )

hash沖突

不支援範圍查詢( like < > )

樹形結構

1. 二叉搜尋樹 -----不平衡

結構示範: https://www.cs.usfca.edu/~galles/visualization/BST.html

通過與每個值進行比對, 大于或者小于, 去向不同的分叉(小于該值去左叉, 大于該值去右叉, 若該值有分叉, 則也會比較該分叉上的值, 即新加入的值都在該樹的最底端)

若查詢38号, 則将55加入記憶體比較, 小于走左邊, 再将30加入記憶體中比較, 大于走右邊, …直到找到38号, 而55号的右分支則不會走, 大大加快檢索速度

一顆特殊二叉樹, 比如我們表中的自增ID主鍵, 若基于該列建立索引會形成下面這個遞增樹, 若查詢ID為4 的資料, 則需要将該右支索引遞歸一邊, 相當于全表掃描

缺陷 :

• 二叉樹結構作為索引機制會形成一個不穩定的樹結構(連結清單結構), 資料的搜尋過程相當于O(n)的時間複雜度, 不友好

1. 平衡二叉搜尋樹 ----相對平衡

結構示範: https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

針對樹中的某個節點, 其子節點的高度差不超過1, 即左右分支的層高相差不允許超過1, 例如20節點, 該節點左支高度為1, 右支高度為0, 內插補點為1

新增樹節點時, 會先按照二叉樹方式進行插入, 當左右分支高度差大于1時, 再通過節點的旋轉等操作來保證樹的相對平衡

若搜尋8号, 先将10号(磁盤塊1)加入記憶體, 關鍵字進行比對, 小于則通過P1節點引用到左分支, 再将5号(磁盤塊2)加入記憶體并比對, …比對到8号後找資料區(可以存指針位址, 也可以存相應具體的資料)

缺陷:

• 樹的高度太高, 磁盤IO操作頻繁, 每次比對都要将磁盤塊加入記憶體中, 硬碟級索引影響性能
• 沒有利用好作業系統跟磁盤的互動特性, 造成空間浪費( 作業系統與磁盤互動, 去磁盤讀資料以頁為機關, 一頁至少4KB空間, 是以每做一次IO互動就是操作4KB的資料内容, 而且每個節點塊隻存儲一個關鍵字, 一個資料區, 兩個子節點, 大部分空間浪費)==

1. 多路平衡樹( B樹 ) ----絕對平衡

   結構示範: https://www.cs.usfca.edu/~galles/visualization/BTree.html

所有子節點的高度都在同一水準線上, 每個節點有兩個或者兩個以上的支路

以根節點為例:

基于兩個關鍵字, 将資料區間劃分5個:

無窮小---->17

17

17------>35

35

35-------->無窮大

若查詢19号, 先将磁盤塊1寫入記憶體, 與區間進行比對, 在17-35區間, 通過P2子節點引用到中間分支, 再将磁盤塊3寫入記憶體, 區間比對,…比對到19号後找到磁盤塊中的資料區拿内容

該節點關鍵字的個數 = 該節點的分支路數 - 1

優點:

• B樹将二叉樹的瘦高型變成了矮胖型, 關鍵字更多, 支路更多, 層數也更少,
• 作業系統跟磁盤IO互動以頁為機關( 一頁至少4KB ), 一個int類型的關鍵字是4byte, 假設資料區和引用區為4byte, 則一頁可以存儲( 4096byte / 8 byte ) 500多個關鍵字, 即500多個支路數

通過節點的分裂合并操作來保證樹的絕對平衡

不要在經常變化的列上建立索引, 因為頻繁添加或者修改資料時, 要不斷去分裂合并去改變結構, 來保證樹的平衡

1. 加強版多路平衡樹( B+樹 )

   結構示範: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

   

   以根節點為例:

   基于三個關鍵字, 将資料區間劃分3個:

   左閉合

1 <= X < 28

28 <= X < 66

66 <= X

因為在MySQL定制的B+數中, 根節點和支節點沒有資料區, 所有資料區都在最後一層的葉子節點上, 是以即使在根節點或者支節點比對到該關鍵字, 也不會停留, 會一直往下查找到葉子節點資料區擷取内容

優點:

• IO能力強于B樹, 每個節點塊可以存儲更多的關鍵字, 操作一次磁盤IO更易精準擷取到内容
• 基于索引結構, 掃庫掃表能力強于B樹, 在B樹中根節點, 支節點, 葉子節點都需要掃描, 因為每個節點塊都有資料區, 而B+樹隻需要掃描葉子節點
• 範圍查詢, 強于B樹, 葉子節點末尾形成天然有序的連結清單結構
• 查詢性能穩定度強于B樹, 在B+樹中, 由于資料區都在葉子節點, 是以操作IO的次數一定是固定的, 而B樹則不一定, 有時候一次, 有時候多次

插拔式存儲引擎

--檢視資料庫的存儲位址
SHOW VARIABLES LIKE 'datadir'
           

MyISAM

每個葉子節點的資料區儲存的是資料所在的位址

MyISAM引擎有兩個檔案, .myi為索引檔案, .myd為資料檔案, 若建立索引, 則會在myi檔案中生成基于該字段為關鍵字的B+樹

主鍵索引與輔助索引沒有主次之分, 搜尋過程都一樣,

InnoDB

每個葉子節點的資料區儲存的是具體的内容

• 隻有主鍵索引的葉子節點資料區存儲的才是該行的所有資料, 關鍵字是索引列, 像這種資料組織方式被稱為聚集索引
• 輔助索引的葉子節點資料區存儲的是主鍵值, 關鍵字是索引列, 會基于主鍵值二次搜尋找到其他值( 回表 )
• 為什麼輔助索引的葉子節點不存儲位址, 直接擷取内容而不是再根據主鍵查找, 因為B+樹是絕對平衡樹, 索引樹中節點會為了保持平衡而不斷分裂合并, 使結構不斷變化, 若是這樣, 那要不斷去維護更新輔助列的位址值, 主鍵索引是最主要的, 不能去一直維護其他輔助索引

  

  innoDB支援BTree索引不支援hash索引, 但是該引擎可以自适應hash索引

  

  

  在MySQL運作過程中, 如果InnoDB發現很多SQL執行時, 存在每次都會通路很長的路徑(層數過多, 每次執行都是固定次數的IO操作), 會在buffer開辟一塊空間, 建立自适應Hash索引, 即将該值與真正的位址做一個對應, 當下次通路發現已經存在自适應Hash索引中, 就會基于該值快速定位而不是再進行查

其他

列的離散性

• 重複率越高, 離散性越差, 離散性很差的列作為索引可能會适得其反

• 離散性越好, 選擇性越好(查詢時, 到每一個節點, 去哪個方向很明确, 而不是模糊的去哪邊都可以), 選擇性好的列更适合做索引

  explain 執行計劃 type=range, 基于索引的範圍查詢都會考慮離散性

例如: 語句 select * from where name like ‘123%’, 能用索引嗎 ?

用離散性去分析, 則不一定, 若有100萬資料, 90萬的name都是以123開頭的, 則全表掃描比, 先基于索引樹找到主鍵, 再根據主鍵去主鍵索引樹查詢值, 更有效

最左比對

從左往右, 一個字元一個字元的去比對

聯合索引

例如:

create index (name)

則索引樹中的節點關鍵字為單列

張三

李四

…

create index(name, phoneNum)

則則索引樹中的節點關鍵字為多列

張三, 13574987451

李四, 14787562112

…

思考題: 會比對聯合索引中的name, phoneNum列, 而不會用到age列, 因為後邊的phoneNum是範圍查詢,age的選擇性就會很差, 離散性很差, 就不會用到索引

第一個索引是備援索引, 因為第二個聯合索引已經包含第一個索引

覆寫索引

三星索引

第一: 聯合索引, 覆寫索引

第二: 排序盡量使用葉子節點天然有序的結構

第三: 避免回表

每一條SQL語句, 一般都隻會用一個索引進行搜尋

name = ’ *** ’ OR age = **

OR的條件, 在MySQL中, 有可能存在合并, type = index_merage, 即會先将通過name索引查詢到的資料放在記憶體中, 再通過age索引去查詢