深入了解Mysql索引底層資料結構與算法

文章目錄

• 索引
• • 索引的本質
  • • 二叉樹
    • 紅黑樹
    • Hash表
    • B-Tree
    • B+Tree(B-Tree變種，多路平衡樹)
  • 存儲引擎索引實作
  • • MyISAM
    • InnoDB
  • 聯合索引底層結構
• 相關學習路線
• • JAVA資深架構師成長路線->架構師築基必備技能->MySql深度優化

索引

索引的本質

• 索引是幫助MySQL高效擷取資料的排好序的資料結構
• 索引資料結構
  • 二叉樹
  • 紅黑樹
  • Hash表
  • B-Tree

二叉樹

紅黑樹

Hash表

B-Tree

• 簡要
  • 葉節點具有相同的深度，葉節點的指針為空
  • 所有索引元素不重複
  • 節點中的資料索引從左到右遞增排列

• 參考

  B-Tree詳解

B+Tree(B-Tree變種，多路平衡樹)

• 非葉子節點不存儲data，隻存儲索引(備援)，可以放更多的索引
• 葉子節點包含所有索引字段
• 葉子節點用指針連接配接，提高區間通路的性能

  

存儲引擎索引實作

MyISAM

MyISAM索引檔案和資料檔案是分離的(非聚集)

InnoDB

• InnoDB索引實作(聚集)
  • 表資料檔案本身就是按B+Tree組織的一個索引結構檔案
  • 聚集索引-葉節點包含了完整的資料記錄
  • 為什麼InnoDB表必須有主鍵，并且推薦使用整型的自增主鍵？
  • 為什麼非主鍵索引結構葉子節點存儲的是主鍵值？(一緻性和節省存儲空間)

  

  

聯合索引底層結構

相關學習路線

JAVA資深架構師成長路線->架構師築基必備技能->MySql深度優化