1. 首頁 > 生活百科 > >

4 MySQL學習---MySQL索引

生活百科

ps：沒有特殊說明 ， 此隨筆中默認采用innoDB存儲引擎中的索引，且索引都是指B+樹（多路平衡搜索樹）結構組織的索引 。其中聚集索引、復合索引、前綴索引、唯一索引默認都是使用B+樹，統稱為索引 。
索引概述索引是存儲引擎用于快速找到記錄的一種數據結構 。
如下圖所示：

4 MySQL學習---MySQL索引

文章插圖
圖中左邊是數據表 ， 一共有2列7行數據，最左邊的0x09格式的數據是物理地址（注：邏輯上相鄰的記錄在磁盤上也不一定是物理相鄰的） 。為了加快Col2列數據的查找，可以維護一個右邊所示的二叉查找樹，每個節點分別包含索引鍵值和一個指向對應數據的物理地址的指針，這樣就可以使用二叉查找樹來快速獲取到對應的數據 。
要理解MySQL中索引是如何工作的 ， 最簡單的方法就是去看看一本書的“索引”部分：如果想在一本書中找到某個特定主題，一般會先看書的“索引” ， 找到對應的頁碼 。
索引對于良好的性能非常關鍵 。尤其是當表中的數據越來越大時，索引對性能影響愈發重要 。在數據量較小且負載較低時 ， 不恰當的索引對性能的影響可能還不明顯，但當數據量逐漸增大時，性能則會急劇下降 。
一般來說索引本身占用也較大 ， 不可能將全部索引存儲在內存中，因此索引往往以索引文件（注：存儲引擎是MYISAM時，索引單獨存儲在.myi文件中；存儲引擎是InnoDB時 ， 索引和表數據一起存儲在.ibd文件中）的形式存儲在磁盤上 。索引是數據庫中用來提高性能的最常用的工具 。
為什么需要索引不使用索引，MySQL 就必須從第一條記錄開始讀完整個表 ， 直到找出相關的行 。表越大，查詢數據所花費的時間就越多 。如果表中查詢的列有一個索引，MySQL 就能快速到達一個位置去搜索數據文件，而不必查看所有數據，這樣將會節省很大一部分時間 。
建立索引的優勢與劣勢優勢
  • 類似于書籍的目錄索引，提高數檢索的效率，降低數據庫的IO成本 。
  • 在實現數據的參考完整性方面可以加速表與表之間的連接 。
  • 在使用分組和排序進行檢索的時候，可以減少查詢中分組和排序的時間.
劣勢
  • 實際上索引也是一張表，該表中保存了主鍵和索引字段，并指向實體類的記錄 ， 因此需要占用物理空間 。數據量越大，占用空間就越大 。
  • 創建和維護索引都需要耗費時間，這種時間隨著數據量的增加而增加 。
  • 雖然創建索引大大提高了查詢的效率，同時卻也降低了更新表的速度，例如對表進行insert、update、delete等操作 。因為更新表時 ， MySQL不僅要保存數據，還需要保存索引文件每次更新的索引列的字段 ， 動態調整因為更新所帶來的鍵值變化后的索引信息 。
索引的底層數據結構索引的底層數據結構是B+樹 。在學習它之前需要了解它的由來 。
二叉查找樹的引入首先，我們來看二叉查找樹 。
二叉查找樹有這樣的特點：
  • 若它的左子樹不空 ， 則左子樹上所有結點的值均小于它的根結點的值；
  • 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
  • 它的左、右子樹也分別為二叉查找樹 。
普通二叉查找樹如下圖所示：
4 MySQL學習---MySQL索引

文章插圖
二叉查找樹如果是完全二叉樹，查找的效率很高，時間復雜度為O(log2N) 。因為最多只需要查找到樹的log2N深度層 。
但是當二叉查找樹為單支樹時，其退化為鏈表，此時它的深度為N，時間復雜度為O(N) 。
此時的二叉查找樹如下圖所示：
4 MySQL學習---MySQL索引

文章插圖
因此，需要平衡二叉樹來降低最壞情況下二叉查找樹的深度 。
平衡二叉樹（AVL樹）的引入平衡二叉查找樹除了具備二叉查找樹的特點，最主要的特征是樹的左右兩個子樹的層級最多相差1 。其在插入刪除數據時通過左旋或右旋操作來保持樹的平衡，不會出現左右子樹一邊很高、一邊很矮的情況 。
平衡二叉樹如下圖所示：
4 MySQL學習---MySQL索引

文章插圖
平衡二叉樹通過對二叉查找樹進行平衡化，從而保證了對樹進行操作的時間復雜度不會退化 。因此，它的平均時間復雜度為O(log2N) 。

推薦閱讀