mysql進階(二十七)數據庫索引原理

Mysql進階(二十七)數據庫索引原理

前言

本文主要是闡述Mysql索引機制，主要是說明存儲引擎Innodb。

第一部分主要從數據結構及算法理論層面討論MySQL數據庫索引的數理基礎。

第二部分結合MySQL數據庫中InnoDB數據存儲引擎中索引的架構實現討論聚集索引、非聚集索引及覆蓋索引等話題。

第三部分討論MySQL中高性能使用索引的策略。

一、數據結構及算法理論

Innodb存儲引擎實現索引的數據結構是B+樹，下面介紹幾種數據結構，一步步闡述為什么要使用B+樹。

1.1 B+樹

B+樹索引的構造類似于二叉樹，根據鍵值快速找到數據。但是B+樹中的B不是代表二叉，而是代表平衡Balance。注意：B+樹索引能找到的只是被查找數據行所在的頁。然后數據庫通過把頁讀入內存，再在內存中進行查找，最后查到數據。

下面介紹二分查找法：將記錄按有序化（遞增或遞減）排列，查找過程中采用跳躍式方式查找，例如：5、10、19、21、31、37、42、48、50、52這10個數，如圖所示：

用了三次查找就能找到48。如果是順序查找的話，則需要8次。對于上面10個數來說，順序查找的平均查找次數為5.5次，而二分查找法為2.9次，在最壞的情況下，順序查找的次數為10，而二分查找的次數為4。二分查找在Innodb中Page Directory中的槽是按照主鍵的順序存放的，對于每一條具體記錄的查詢是通過對Page Directory進行二分查找。

1.2二叉查找樹

數字代表每個節點的鍵值，二叉查找樹中，左子樹的鍵值總是小于根的鍵值，右子樹的鍵值總是大于根的鍵值。通過中序遍歷得到鍵值：2、3、5、6、7、8。

二叉查找樹的平均查找次數為2.3次。但是二叉查找樹是可以任意構建，如構造如圖：

但是這樣跟順序查找就差不多，所以就引用了平衡二叉樹的思想，AVL樹。

1.3 AVL樹

定義：符合二叉查找樹的定義，其次必須滿足任何節點的左右兩個子樹的高度最大差為1。

平衡二叉樹雖然查找速度非常快但是維護一顆平衡二叉樹的代價是非常大，通常需要1次或多次左旋和右旋來得到插入或更新后樹的平衡性。

1.4 B+樹的特性

B+樹是應文件系統而出的一種B樹的變形樹。在B樹中，每一個元素在該樹中只出現一次，有可能在葉子節點上，也有可能在分支節點上。而在B+樹中，出現在分支節點的元素會被當作它們在該分支節點位置的中序后繼者(葉子節點)中再次列出。另外，每一個葉子節點都會保存一個指向后一葉子節點的指針。所有記錄都在葉節點，并且是順序存放，各個葉節點（頁為單位）都是邏輯的連續存放，是一個雙向循環鏈表。

如果是要隨機查找，我們就從根節點出發，與B樹的查找方式相同，只不過在分支節點即使找到了待查找的關鍵字，它也只是用來索引的，不能提供實際記錄的訪問，還是需要到達包含此關鍵字的終端節點。

如果我們是需要從最小關鍵字進行從小到大的順序查找，我們就可以從最左側的葉子節點出發，不經過分支節點，而是沿著指向下一葉子節點的指針就可遍歷所有的節點。

B+樹插入必須保證插入后葉節點中的記錄依然排序，所以在插入時必須考慮以下三種情況：

B+樹索引在數據庫中有一個特點就是其高扇出性，因此在數據庫中，B+樹高度一般在2-3層，也就是尋找某一鍵值的行記錄，最多2-3次IO，而一般的磁盤每秒至少可以做100次IO，2-3次的意味著查詢時間只需0.02-0.03秒。

二、聚集索引、非聚集索引

聚集索引與非聚集索引的區別是：頁節點是否存放一整行記錄

2.1 聚集索引

InnoDB存儲引擎表是索引組織表，即表中數據按照主鍵順序存放。而聚集索引就是按照每張表的主鍵構造一顆B+樹，并且葉節點中存放著整張表的行記錄數據，因此也讓聚集索引的葉節點成為數據頁。聚集索引的這個特性決定了索引組織表中的數據也是索引一部分。同B+樹數據結構一樣，每個數據頁都通過一個雙向鏈表來進行鏈接。

實際數據也只能按照一顆B+樹進行排序，因此每張表只能擁有一個聚集索引。在許多情況下，查詢優化器非常傾向于采用聚集索引，因為聚集索引能夠讓我們在索引的葉節點直接找到數據。此外，由于定義了數據的邏輯順序，聚集索引能夠快速地訪問針對范圍值得到查詢。查詢優化器能夠快速發現某一段范圍的數據需要掃描。注意每一個頁中的記錄也是雙向鏈表維護的。

2.2 非聚集索引

也稱輔助索引，頁級別不包含行的全部數據。頁節點除了包含鍵值以外，每個頁級別中的索引中還包含了一個書簽，該書簽用來告訴InnoDB存儲引擎，哪里可以找到與索引相對應的行數據。因為InnoDB存儲引擎表是索引組織表，因此InnoDB存儲引擎的輔助索引書簽就是相應行數據的聚集索引鍵。下圖是聚集索引和輔助索引的關系：

當通過輔助索引來尋找數據時，InnoDB存儲引擎會遍歷輔助索引并通過葉級別的指針獲得指向主鍵索引的主鍵，然后再通過主鍵索引來找到了一個完整的行記錄。舉例來說：一顆高度為3的輔助索引樹中查找數據，那么需要對這顆輔助索引遍歷3次找到指定主鍵；如果聚集索引樹的高度同樣為3，那么還需要對聚集索引進行三次查找，才能查找一個完整的行數據所在的頁，因此需要6次的邏輯Io來訪問最終的一個數據頁。

MySQL 數據庫

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。