【深入淺出】——MySQL索引B+Tree

        索引存在的意義是幫助我們提高查詢速度，那麼為什麼建立了索引，MySQL的查詢速度就可以提高呢？為什麼MySQL單表的資料達到千萬後就開始建議分庫分表？基于這些未知的問題，開始本文篇文章的内容。

何為索引

        索引是幫助MySQL高效擷取資料的排好序的資料結構。劃重點，排好序，資料結構，是以索引是真實存在的，不僅僅是一個虛無的概念。

        索引提升查詢的效率的原因是因為将排序的過程前置，當需要查找的時候，直接可以定位到具體資料，省去全表周遊的過程，進而提升查詢效率。是以好的索引，要避免資料變成連結清單，減少需要比對資料，進而達到預期效果。

索引資料結構

• 二叉樹

  二叉樹在一定程度上緩解連結清單的查詢效率問題，但是随着資料增加，二叉樹存在演變成連結清單的可能，故存在影響查詢效率的可能

• 紅黑樹

  紅黑樹又稱平衡二叉樹，相比二叉樹可能存在變成連結清單的風險，會在查詢好很多，但是依舊無法解決層高過高的問題，層高過高，則證明比對資料比較多，會影響查詢效率

  

• Hash表

  對索引的key進行一次hash計算就可以定位出資料存儲的位置，很多時候Hash索引要比B+ 樹索引更高效，但僅能滿足 “=”，“IN”，不支援範圍查詢，還會存在hash沖突問題

  面對範圍查找Hash表則隻能變成全局掃描，僅符合部分特征

  

• B-Tree

  B-Tree一層中可以存儲更多的資料節點，而且可以保證節點元素從左到右依次遞增，相比二叉樹、紅黑樹同樣的層高可以存儲元素更多，查詢效果更好。B-Tree存儲特點，每個節點存儲來索引以及具體資料，而MySQL頁容量大約為16KB，當單表資料集過大時，樹的高度同樣會比較高，影響查詢效率。而且B-Tree每個葉子結點是不會連的，無法支援範圍查找

  PS：檢視mysql檔案頁大小（16K）：SHOW GLOBAL STATUS like 'Innodb_page_size’;

  

  那麼問題來了MySQL的索引到底用的什麼資料結構，才能解決上述這些亂七八糟的問題？

B+Tree

    解決MySQL查詢效率問題，必須解決以下幾類問題

    1.樹高低且支援資料量要大

     2.支援範圍查詢

    從上述分析的資料結構可以得知，暫時B-Tree是最好，那麼解決B-Tree的不足之處，它就能變成好用的，故B+Tree（B-Tree）的變形應運而生。

B+Tree特點

• 非葉子結點不存儲data，隻存儲索引（備援），但是可以存放更多的索引
• 葉子結點包含所有的索引字段
• 葉子結點之間用指針相連（雙向指針），提高區域通路性能

  

  那麼這種資料結構，樹高為3能存儲多少資料呢？

  假設主鍵是bigint類型，長度8B，指針大小在Innodb源碼中為6B，一共14B，那麼一頁能存儲16K/14B=1170個（主鍵+指針），葉子結點存在資料假設為1k，則一顆高度為3的B+Tree能存儲資料為：1170 * 1170 * 16=21902400（千萬級條）

看到這裡回答下文章開頭的問題

1、為什麼索引可以提升查詢效率？

    索引将資料有序的排列，查詢資料時減少了比較IO操作，進而提高查詢效率，而且索引的根結點通常是常駐記憶體的，是以正确的索引可以提升查詢效率

2、為什麼MySQL單表的資料達到千萬後就開始建議分庫分表？

    随着單表資料的增長，索引的數高也會增大，會增大比較次數，降低查詢效率

從索引看存儲引擎實作

        MySQL存在多種資料存儲引擎，而且在使用時真正生效的存儲引擎其實還是table上的設定的存儲引擎，接下來隻介紹日常工作中經常MyISAM和InnoDB的索引實作方案。從data存儲方式，MySQL的安裝目錄data檔案夾下，有每個資料庫的具體存儲内容，看到table次元，可以發現MyISAM有三個存儲檔案frm(表結構)、MyD(資料)、MyI(索引),而InnoDB有兩個frm(表結構)，idb(資料+索引)，是以通過存儲方式可以看出兩種存儲引擎實作不同。

MyISAM

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

InnoDB

InnoDB索引檔案和資料檔案是存儲在一起的(聚集)，表資料檔案本身就是按B+Tree組織的一個索引結構檔案。聚集索引-葉節點包含了完整的資料記錄，在InooDB中僅有主鍵索引是聚集索引而其他索引都是非聚集索引

此時引出兩個概念聚集索引和非聚集索引，通過兩種存儲引擎的比較方式可以得知，聚集索引，将索引和具體資料存儲在一起，而非聚集索引則索引和資料分開存儲故查詢查詢效率會低一些。

其他索引的資料結構

從面試看B+Tree

設計分庫分表方案時有幾種拆分方式？為什麼這樣拆分？

• 兩種拆分方式，水準拆分和垂直拆分。
• 水準拆分解決單表資料過大，造成索引的樹高增加，增加查詢IO次數，進而影響查詢效率。
• 垂直拆分解決單條資料過大，造成葉子結點每頁存儲的資料減少，增大存儲空間，在範圍查詢時涉及資料頁過多，IO次數增加，影響查詢效率。

為什麼建議InnoDB表必須建主鍵，并且推薦使用整型的自增主鍵？

• 因為InnoDB的存儲方式是基于聚集索引建構的，如果沒有設定主鍵，那麼MySQL就在目前表結構中尋找不重複的一列作為索引來建構，而如果找不到符合條件的列，則會設定隐藏列來完成這一過程。MySQL的資源很寶貴，沒有必要浪費資源做這樣的運算僅為完成資料的建構。
• 索引是有序的，用整型比較是最友善的直接比大小即可，而使用其他類型還需要計算ascii碼，變相資源浪費。
• 索引是排好序的資料結構，亂序的主鍵，每次插入都需要B+Tree重新調整平衡，而自增隻有葉子結點會上移，成本肯定是小于調整平衡。

為什麼非主鍵索引結構葉子節點存儲的是主鍵值？

• 資料存儲多份，一緻性的保證會增加額外的成本
• 僅存儲主鍵值，這樣會節約大量資料存儲空間（主要原因）

為什麼B+Tree可以支援範圍查找？

• B+Tree的葉子節點的指針是互相指向張彼此的，這樣在範圍查找的，找到起始葉子節點不用再回溯到上層非葉子節點，通過葉子節點之間的指針即可完成。

為什麼MySQL索引僅支援左字首原則呢？

• 索引是排好序的資料結構，聯合索引的存儲方式，和普通索引基本無差别，就是在非葉子節點的時候，是按照聯合索引的定義的順序字段排序的，即每個字段都是有序的，如果打破順序，從第二個字段開始比對，因為不知道前置字段，故第二個字段起始位置無法确定，隻能從最左側開始比對。

總結

        MySQL使用B+Tree作為索引，主要原因是B+Tree的非葉子節點僅存儲索引值，使每頁可以存儲的索引資料增加，進而減少樹高，同時葉子節點之間的雙向指針，減少範圍查找的回溯次數，這兩個角度都是減少查找的IO操作，進而提高查詢效率。關于MySQL存儲引擎，InnoDB使用聚集索引，将資料和主鍵進行聚集，使得通過主鍵可以直接擷取資料詳細，無需二次查找。

PS：本文如有了解偏頗之處，肯定各位大神不惜賜教，不勝感激