首頁  >  文章  >  資料庫  >  mysql索引快的原因是什麼

mysql索引快的原因是什麼

PHPz
PHPz轉載
2023-05-31 20:58:101853瀏覽

透過預先排序,索引可以使用二分查找等高效率演算法進行查找。一般的順序查找,複雜度為O(n),而二分查找複雜度為O(log2n);當n很大時,二者的效率相差及其懸殊。

Mysql 作為互聯網中非常熱門的資料庫,其底層的儲存引擎和資料檢索引擎的設計非常重要,尤其是Mysql 資料的儲存形式以及索引的設計,決定了Mysql 整體的數據檢索性能。

我們知道,索引的作用是做資料的快速檢索,而快速檢索的實作的本質是資料結構。透過不同資料結構的選擇,實現各種資料快速檢索。在資料庫中,高效的查找演算法是非常重要的,因為資料庫中儲存了大量數據,一個高效的索引可以節省巨大的時間。例如下面這個數據表,如果Mysql 沒有實作索引演算法,那麼查找id=7 這個數據,那就只能採取暴力順序遍歷查找,找到id=7 這個數據需要比較7 次,如果這個表儲存的是1000W 個數據,查找id=1000W 這個數據那就要比較1000W 次,這種速度是不能接受的。

mysql索引快的原因是什麼

一、Mysql 索引底層資料結構選取


mysql索引快的原因是什麼


#哈希表(Hash)mysql索引快的原因是什麼
哈希表是做資料快速檢索的有效利器。 mysql索引快的原因是什麼

考慮這個資料庫表user,表中一共有7 個數據,我們需要檢索id=7 的數據, SQL 語法是:

select * from user where id=7;

哈希演算法首先計算儲存id=7 的資料的物理位址addr=hash(7)=4231,而4231 映射的物理位址是0x77,0x77 是id=7 儲存的額資料的實體位址,透過該獨立位址可以找到對應user_name='g'這個資料。這就是哈希演算法快速檢索資料的計算過程。

###但是雜湊演算法有個資料碰撞的問題,也就是雜湊函數可能會對不同的key 會計算出同一個結果,例如hash(7)可能跟hash(199)計算出來的結果一樣,也就是不同的key 映射到同一個結果了,這就是碰撞問題。解決碰撞問題的一個常見處理方式就是鏈結位址法,也就是用鍊錶把碰撞的資料接連起來。計算雜湊值之後,還需要檢查該雜湊值是否存在碰撞資料鍊錶,有則一直遍歷到鍊錶尾,直達找到真正的 key 對應的資料為止。 #############################################從演算法時間複雜度分析來看,哈希演算法時間複雜度為O(1),檢索速度非常快。例如查找 id=7 的數據,哈希索引只需要計算一次就可以獲得對應的數據,檢索速度非常快。但是 Mysql 並沒有採取哈希作為其底層演算法,這是為什麼呢? ######因為考慮到資料擷取有一個常用手段就是範圍查找,例如以下這個SQL 語句:###
select * from user where id \>3;
###針對以上這個語句,我們希望做的是找出id>3 的數據,這是很典型的範圍查找。如果使用哈希演算法實現的索引,範圍查找怎麼做呢?一個簡單的想法就是一次把所有資料找出來載入到內存,然後再在內存裡篩選篩選目標範圍內的資料。但是這個範圍查找的方法也太笨重了,沒有一點效率而言。 ######所以,使用哈希演算法實現的索引雖然可以做到快速檢索數據,但是沒辦法做數據高效範圍查找,因此哈希索引是不適合作為 Mysql 的底層索引的數據結構。 ######

二元查找樹(BST)

二元查找樹是一種支援資料快速尋找的資料結構,如圖下所示:

mysql索引快的原因是什麼

二元查找樹的時間複雜度是O(lgn),例如針對上面這個二元樹結構,我們需要計算比較3 次就可以檢索到id=7 的數據,相對於直接遍歷查詢省了一半的時間,從檢索效率看來是能做到高速檢索的。另外二叉樹的結構能不能解決哈希索引不能提供的範圍查找功能呢?

答案是可以的。觀察上面的圖,二元樹的葉子節點都是按序排列的,從左到右依次升序排列,如果我們需要找id>5 的數據,那我們取出節點為6 的節點以及其右子樹就可以了,範圍查找也算是比較容易實現。

但是普通的二元查找樹有個致命缺點:極端情況下會退化為線性鍊錶,二分查找也會退化為遍歷查找,時間複雜退化為 O(N),檢索性能急劇下降。例如以下這個情況,二元樹已經極度不平衡了,已經退化成鍊錶了,檢索速度大大降低。此時檢索 id=7 的資料的所需計算的次數已經變成 7 了。

mysql索引快的原因是什麼

在資料庫中,資料的自增是一個很常見的形式,例如一個表的主鍵是id,而主鍵一般預設都是自增的,如果採取二元樹這種資料結構作為索引,那上面介紹到的不平衡狀態導致的線性查找的問題必然出現。因此,簡單的二元查找樹有不平衡導致的檢索效能降低的問題,是無法直接用於實作 Mysql 底層索引的。

AVL 樹和紅黑樹

二元尋找樹有不平衡問題,因此學者提出透過樹節點的自動旋轉和調整,讓二元樹始終保持基本平衡的狀態,就能保持二元查找樹的最佳查找效能了。基於這種想法的自調整平衡狀態的二元樹有 AVL 樹和紅黑樹。

首先簡單介紹紅黑樹,這是一顆會自動調整樹形態的樹狀結構,例如當二元樹處於一個不平衡狀態時,紅黑樹就會自動左旋右旋節點以及節點變色,調整樹的形態,使其保持基本的平衡狀態(時間複雜度為O(logn)),也確保了查找效率不會明顯減低。例如從 1 到 7 升序插入資料節點,如果是普通的二元查找樹則會退化成鍊錶,但是紅黑樹則會不斷調整樹的形態,使其保持基本平衡狀態,如下圖所示。下面這個紅黑樹下查找 id=7 的要比較的節點數為 4,依然保持二元樹不錯的查找效率。

紅黑樹擁有不錯的平均查找效率,也不存在極端的 O(n)情況,那紅黑樹作為 Mysql 底層索引實現是否可以呢?其實紅黑樹也存在一些問題,觀察下面這個例子。
紅黑樹順序插入 1~7 個節點,找出 id=7 時需要計算的節點數為 4。

mysql索引快的原因是什麼

紅黑樹順序插入1~16 個節點,找出id=16 需要比較的節點數為6 次。觀察這個樹的形態,是不是當資料是順序插入時,樹的形態一直處於「右傾」的趨勢?從根本上看,紅黑樹並沒有完全解決二元查找樹雖然這個「右傾」趨勢遠沒有二元查找樹退化為線性鍊錶那麼誇張,但是資料庫中的基本主鍵自增操作,主鍵一般都是數百萬數千萬的,如果紅黑樹存在這種問題,對於查找性能而言也是巨大的消耗,我們資料庫不可能忍受這種無意義的等待的。

mysql索引快的原因是什麼

現在考慮另一種更嚴格的自平衡二元樹 AVL 樹。因為 AVL 樹是個絕對平衡的二元樹,因此他在調整二元樹的形態上消耗的表現會更多。

AVL 樹順序插入 1~7 個節點,找出 id=7 要比較節點的次數為 3。

mysql索引快的原因是什麼

AVL 樹順序插入 1~16 個節點,找出 id=16 需要比較的節點數為 4。從尋找效率而言,AVL 樹查找的速度高於紅黑樹的尋找效率(AVL 樹是 4 次比較,紅黑樹是 6 次比較)。從樹的形態看來,AVL 樹不存在紅黑樹的「右傾」問題。也就是說,大量的順序插入不會導致查詢效能的降低,這從根本上解決了紅黑樹的問題。

mysql索引快的原因是什麼

總結AVL 樹的優點:

  1. ##不錯的查找效能(O(logn)),不存在極端的低效率查找的情況。


  2. 可以實現範圍查找、資料排序。


看起來AVL 樹作為資料尋找的資料結構確實很不錯,但是AVL 樹並不適合做Mysql 資料庫的索引資料結構,因為考慮一下這個問題:

資料庫查詢資料的瓶頸在於磁碟IO,如果使用的是AVL 樹,我們每一個樹節點只儲存了一個數據,我們一次磁碟IO 只能取出一個節點上的資料載入到記憶體裡,那例如查詢id=7 這個資料我們就要進行磁碟IO 三次,這是多麼消耗時間的。所以我們設計資料庫索引時需要先考慮怎麼盡可能減少磁碟 IO 的次數。

磁碟IO 有個有個特點,就是從磁碟讀取1B 資料和1KB 資料所消耗的時間是基本上相同的,我們就可以根據這個思路,我們可以在一個樹節點上盡可能多地儲存數據,一次磁碟IO 就多加載點數據到內存,這就是B 樹,B 樹的設計原理了。


B 樹

在下面這個 B 樹,每個節點限制最多儲存兩個 key,一個節點如果超過兩個 key 就會自動分割。例如下面這個儲存了 7 個資料 B 樹,只需要查詢兩個節點就可以知道 id=7 這資料的具體位置,也就是兩次磁碟 IO 就可以查詢到指定數據,優於 AVL 樹。


mysql索引快的原因是什麼
下面是儲存了16 個資料的B 樹,同樣每個節點最多儲存2 個key,查詢id=16 這個資料要查詢比較4 個節點,也就是經過4 次磁碟IO。看起來查詢效能與 AVL 樹一樣。


mysql索引快的原因是什麼
但是考慮到磁碟IO 讀一個資料和讀取100 個資料消耗的時間基本上一致,那我們的最佳化思路就可以改為:盡可能在一次磁碟IO 中多讀一點資料到記憶體。這個直接反映到樹的結構就是,每個節點能儲存的 key 可以適當增加。

當我們把單一節點限制的 key 個數設定為 6 之後,一個儲存了 7 個資料的 B 樹,查詢 id=7 這個資料所要進行的磁碟 IO 為 2 次。


mysql索引快的原因是什麼

一個儲存了 16 個資料的 B 樹,查詢 id=7 這個資料要進行的磁碟 IO 為 2 次。相對於 AVL 樹而言磁碟 IO 次數降至一半。

mysql索引快的原因是什麼

所以資料庫索引資料結構的選型而言,B 樹是一個很不錯的選擇。總結來說,B 樹用作資料庫索引有以下優點:

  1. #優秀擷取速度,時間複雜度:B 樹的尋找效能等於O(h* logn),其中h 為樹高,n 為每個節點關鍵字的個數;

  2. 盡可能少的磁碟IO,加快了檢索速度;

  3. 可以支援範圍查找。

  4. B 樹

#B 樹和 B 樹有什麼不同?

第一,B 樹一個節點裡存的是數據,而B 樹儲存的是索引(位址),所以B 樹裡一個節點存不了很多個數據,但是B 樹一個節點能存很多索引,B 樹葉子節點存所有的資料。

第二,B 樹的葉子節點是資料階段用了一個鍊錶串聯起來,方便範圍查找。

mysql索引快的原因是什麼

透過B 樹和B 樹的比較我們看出,B 樹節點儲存的是索引,在單一節點儲存容量有限的情況下,單一節點也能儲存大量索引,使得整個B 樹高度降低,減少了磁碟IO。其次,B 樹的葉子節點是真正資料儲存的地方,葉子節點用了鍊錶連接起來,這個鍊錶本身就是有序的,在資料範圍查找時,更具備效率。因此 Mysql 的索引用的就是 B 樹,B 樹在尋找效率、範圍查找上都有非常不錯的效能。

二、Innodb 引擎和Myisam 引擎的實作

Mysql 底層資料引擎以外掛形式設計,最常見的是Innodb 引擎和Myisam 引擎,使用者可以根據個人需求選擇不同的引擎作為Mysql 資料表的底層引擎。我們剛剛分析了,B 樹作為 Mysql 的索引的資料結構非常合適,但是資料和索引到底怎麼組織起來也是需要一番設計,設計理念的不同也導致了 Innodb 和 Myisam 的出現,各自呈現獨特的效能。

MyISAM 雖然資料查找效能極佳,但不支援事務處理。 Innodb 最大的特色就是支援了 ACID 相容的事務功能,而且他支援行級鎖定。 Mysql 建立表格的時候就可以指定引擎,例如下面的例子,就是分別指定了 Myisam 和 Innodb 作為 user 表和 user2 表的資料引擎。

mysql索引快的原因是什麼
mysql索引快的原因是什麼

執行這兩個指令後,系統出現了以下的文件,說明這兩個引擎資料和索引的組織方式是不一樣的。

mysql索引快的原因是什麼

Innodb 建立表格後產生的檔案有:

  • # #frm:建立表格的語句


  • idb:表格裡面的資料索引檔


Myisam 建立表格後生成的檔案有


  • frm:建立表格的語句


  • #MYD:表格裡面的資料檔案(myisam data)


  • MYI:表裡面的索引檔案(myisam index)

#從產生的檔案看來,這兩個引擎底層資料和索引的組織方式並不一樣,MyISAM 引擎把資料和索引分開了,一人一個文件,這叫做非聚集索引方式;Innodb 引擎把資料和索引放在同一個文件裡了,這叫做聚集索引方式。下面將從底層實作角度分析這兩個引擎是怎麼依靠 B 樹這個資料結構來組織引擎實現的。

MyISAM 引擎的底層實作(非聚集索引方式)

MyISAM 用的是非聚集索引方式,即資料和索引落在不同的兩個文件上。 MyISAM 在建表時以主鍵作為 KEY 來建立主索引 B 樹,樹的葉子節點存的是對應資料的實體位址。我們拿到這個實體位址後,就可以到 MyISAM 資料檔直接定位到具體的資料記錄了。

mysql索引快的原因是什麼

當我們為某個欄位新增索引時,我們同樣會產生對應欄位的索引樹,該欄位的索引樹的葉子節點同樣是記錄了對應資料的實體位址,然後也是拿著這個實體位址去資料檔案定位到具體的資料記錄。

Innodb 引擎的底層實作(聚集索引方式)

InnoDB 是聚集索引方式,因此資料和索引都儲存在同一個檔案裡。首先InnoDB 會根據主鍵ID 作為KEY 建立索引B 樹,如左下圖所示,而B 樹的葉子節點儲存的是主鍵ID 對應的數據,例如在執行select * from user_info where id=15 這個語句時,InnoDB就會查詢這顆主鍵ID 索引B 樹,找出對應的user_name='Bob'。

這是建表的時候 InnoDB 就會自動建立好主鍵 ID 索引樹,這也是為什麼 Mysql 在建表時要求必須指定主鍵的原因。當我們為表裡某個欄位加索引時 InnoDB 會怎麼建立索引樹呢?例如我們要為 user_name 這個欄位加索引,那麼 InnoDB 就會建立 user_name 索引 B 樹,節點裡存的是 user_name 這個 KEY,葉子節點儲存的資料的就是主鍵 KEY。注意,葉子儲存的是主鍵 KEY!拿到主鍵 KEY 後,InnoDB 才會去主鍵索引樹裡根據剛在 user_name 索引樹找到的主鍵 KEY 查找到對應的資料。

mysql索引快的原因是什麼

#問題來了,為什麼InnoDB 只在主鍵索引樹的葉子節點儲存了具體數據,但是其他索引樹卻不存具體資料呢,而要多此一舉先找到主鍵,再在主鍵索引樹找到對應的資料呢?

#其實很簡單,因為InnoDB 需要節省儲存空間。一個表裡可能有很多個索引,InnoDB 都會為每個加了索引的字段生成索引樹,如果每個字段的索引樹都存儲了具體數據,那麼這個表的索引數據文件就變得非常巨大(數據極度冗餘了)。從節約磁碟空間的角度來說,真的沒有必要每個字段索引樹都存具體數據,通過這種看似“多此一舉”的步驟,在犧牲較少查詢的性能下節省了巨大的磁碟空間,這是非常有值得的。

在進行InnoDB 和MyISAM 特點比較時談到,MyISAM 查詢效能更好,從上面索引檔案資料檔案的設計來看也可以看出原因:MyISAM 直接找到實體位址後就可以直接定位到資料記錄,但InnoDB 查詢到葉子節點後,還需要再查詢一次主鍵索引樹,才可以定位到特定資料。等於 MyISAM 一步就查到了數據,但是 InnoDB 要兩步,那當然 MyISAM 查詢效能更高。

以上是mysql索引快的原因是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:yisu.com。如有侵權,請聯絡admin@php.cn刪除