1. 首頁 > 生活百科 > >

「MySQL高級篇」MySQL索引原理，設計原則( 二 )

生活百科


  • BTREE 索引 ： 最常見的索引類型，大部分索引都支持 B 樹索引 。
  • HASH 索引：只有Memory引擎支持，使用場景簡單。
  • R-tree 索引（空間索引）：空間索引是MyISAM引擎的一個特殊索引類型，主要用于地理空間數據類型，通常使用較少，不做特別介紹 。
  • Full-text （全文索引） ：全文索引也是MyISAM的一個特殊索引類型，主要用于全文索引，InnoDB從Mysql5.6版本開始支持全文索引 。
MyISAM、InnoDB、Memory三種存儲引擎對各種索引類型的支持
索引INNODB引擎MYISAM引擎MEMORY引擎BTREE索引支持支持支持HASH 索引不支持不支持支持R-tree 索引不支持支持不支持Full-text5.6版本之后支持支持不支持我們平常所說的索引，如果沒有特別指明，都是指B+樹（多路搜索樹，并不一定是二叉的）結構組織的索引 。其中聚集索引、復合索引、前綴索引、唯一索引默認都是使用 B+tree 索引，統稱為 索引 。
BTREE多路平衡搜索樹，一棵m階(m叉)BTREE滿足：
  • 每個節點最多m個孩子
    • 孩子個數：ceil(m/2) 到 m
    • 關鍵字個數：ceil(m/2)-1 到 m-1
ceil表示向上取整，ceil(2.3)=3
插入關鍵字案例
「MySQL高級篇」MySQL索引原理，設計原則

文章插圖
保證不破壞m階B樹的性質由于3階，最多只能2個節點，所以一開始26和30在一起，之后再來個85就要開始分裂了，30作為中間上位，26保持 ， 85去到右邊即：中間位置上位，然后左邊留在舊節點，右邊去到新結點
如圖中的70再插入的時候，70剛好是中間位置上位，然后62保持，85又去分一個新節點出來

「MySQL高級篇」MySQL索引原理，設計原則

文章插圖
上位后又需要分裂
繼續向上分裂即可 ， 同理的

「MySQL高級篇」MySQL索引原理，設計原則

文章插圖
相比優勢相比二叉搜索樹 ， 高度/深度更低 ， 自然查詢效率更高 。
B+TREE
  • B+樹有兩種類型的節點：內部結點（也稱索引結點）和葉子結點 。內部節點就是非葉子節點，內部節點不存儲數據，只存儲索引，數據都存儲在葉子節點 。
  • 內部結點中的key都按照從小到大的順序排列，對于內部結點中的一個key，左樹中的所有key都小于它，右子樹中的key都大于等于它 。葉子結點中的記錄也按照key的大小排列 。
  • 每個葉子結點都存有相鄰葉子結點的指針，葉子結點本身依關鍵字的大小自小而大順序鏈接 。
  • 父節點存有右孩子的第一個元素的索引 。
?
「MySQL高級篇」MySQL索引原理，設計原則

文章插圖
相比優勢
  • B+Tree的查詢效率更加穩定 。由于B+Tree只有葉子節點保存key信息，查詢任何key都要從root走到葉子，所以更穩定 。
  • 只需遍歷葉子節點，就可以實現整棵樹的遍歷 。
?
MySQL中的B+TreeMySql索引數據結構對經典的B+Tree進行了優化 。在原B+Tree的基礎上 ， 增加一個指向相鄰葉子節點的鏈表指針(整體類似一個雙向鏈表的結構)，就形成了帶有順序指針的B+Tree，提高區間訪問的性能 。?
細心的同學可以看出，這張圖跟我們的二叉查找樹簡圖的一個最大區別是什么？
  • 從二叉查找樹過渡到B樹，有一個顯著的變化就是 ， 一個節點可以存儲多個數據了，相當于一個磁盤塊里邊可以存儲多個數據，大大減少了我們的 IO次數?。?/li>
MySQL中的 B+Tree 索引結構示意圖：
「MySQL高級篇」MySQL索引原理，設計原則

文章插圖
二叉查找樹簡圖：
「MySQL高級篇」MySQL索引原理，設計原則

文章插圖
索引原理BTree索引：
「MySQL高級篇」MySQL索引原理，設計原則

文章插圖
初始化介紹淺藍色的稱之為一個磁盤塊，可以看到每個磁盤塊包含幾個數據項（深藍色所示）和指針（黃色所示)如磁盤塊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 。`
  • 非葉子節點不存儲真實的數據，只存儲指引搜索方向的數據項 ， 如17、35并不真實存在于數據表中 。`
查找過程如果要查找數據項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 ， 顯然成本非常非常高 。

推薦閱讀