首頁 > 軟體

深入解析MySQL索引資料結構

2021-10-13 19:01:54

概述

索引是對資料庫表中一列或多列的值進行排序的一種結構,使用索引可快速存取資料庫表中的特定資訊。

索引資料結構

二元樹

二元樹(binary tree)是指樹中節點的度不大於 2 的有序樹,它是一種最簡單且最重要的樹。二元樹的遞迴定義為:二元樹是一棵空樹,或者是一棵由一個根節點和兩棵互不相交的,分別稱作根的左子樹和右子樹組成的非空樹;左子樹和右子樹又同樣都是二元樹

對於陣列 {1,2,3,4,5} 資料結構將成為了連結串列

特點:

  • 父節點下面有兩個子節點。
  • 右邊節點的資料大於左邊節點的資料。


二元樹.png

紅黑樹

紅黑樹是一種特定型別的二元樹,它是在電腦科學中用來組織資料比如數位的塊的一種結構。若一棵二叉查詢樹是紅黑樹,則它的任一子樹必為紅黑樹。

紅黑樹是一種平衡二叉查詢樹的變體,它的左右子樹高差有可能大於 1,所以紅黑樹不是嚴格意義上的平衡二元樹(AVL),但對之進行平衡的代價較低, 其平均統計效能要強於 AVL 。

由於每一棵紅黑樹都是一棵二叉排序樹,因此,在對紅黑樹進行查詢時,可以採用運用於普通二叉排序樹上的查詢演演算法,在查詢過程中不需要顏色資訊。

紅黑樹資料結構如下圖:


紅黑樹資料結構.png

特點:

  • 紅黑樹是每個結點都帶有顏色屬性的二叉查詢樹,顏色或紅色或黑色。
  • 結點是紅色或黑色。
  • 根結點是黑色。
  • 所有葉子都是黑色。(葉子是NIL結點)
  • 每個紅色結點的兩個子結點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色結點)
  • 從任一節結點其每個葉子的所有路徑都包含相同數目的黑色結點。
  • 這些約束強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查詢某個值的最壞情況時間都要求與樹的高度成比例,這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的,而不同於普通的二叉查詢樹。
  • 是性質4導致路徑上不能有兩個連續的紅色結點確保了這個結果。最短的可能路徑都是黑色結點,最長的可能路徑有交替的紅色和黑色結點。因為根據性質5所有最長的路徑都有相同數目的黑色結點,這就表明了沒有路徑能多於任何其他路徑的兩倍長。
  • 因為紅黑樹是一種特化的二叉查詢樹,所以紅黑樹上的唯讀操作與普通二叉查詢樹相同。

B-Tree

  • 葉子結點具有相同的深度,葉節點的指標為空
  • 所有元素不重複
  • 節點中的資料索引從左到右邊遞增排列

B樹資料結構.png

B+Tree

  • 非葉子結點不儲存資料,只儲存索引(冗餘),可以存放更多的索引
  • 葉子結點包含所有索引欄位
  • 葉子結點用指標連結,提高區間存取的效能(可以提升範圍查詢的效率)

B+樹資料結構.png

特點關鍵字:節點內有序,葉子結點指標連結,非葉子結點儲存索引(冗餘)

查詢mysql 索引的資料頁的大小:

mysql> show global status like 'Innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| Innodb_page_size | 16384 |
+------------------+-------+

為什麼設定 16kb 呢?

Hash

  • 對索引的 key 進行一次 hash 計算就可以定位出資料儲存的位置
  • 很多的時候 hash 索引要比 B+ 樹索引更高效
  • 僅能滿足 「=」 , 「in」  不支援範圍查詢
  • 存在 hash 衝突問題


Hash 資料結構.png

索引

InnoDB 索引實現(聚集)

表資料檔案本身就是按 B+Tree 組織的一個索引結構檔案

聚集索引-葉子節點包含了完整的資料記錄

為什麼 InnoDb 表必須有主鍵,並且推薦使用整型的自增主鍵?

  • 如果沒有設定索引的話,MySQL 會選擇一個資料唯一的列作為主鍵索引, 如果找不這樣的列。會去做建立一個隱藏列類似  rowid。
  • 表資料檔案按照 B+Tree 的資料結構維護,在葉子節點維護的是該行的資料。所以必須有主鍵。
  • 整型更方便 B+Tree 排序,自增的話,對於資料結構的存放更快,  順序存放,不需要進行大量樹的平衡操作。

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

  • 一致性, 讓主鍵索引先成功,然後再去更新非主鍵索引關係
  • 節省儲存空間。

主鍵索引示意圖:


InnoDB 索引實現.png

非主鍵索引示意圖圖片

如果查詢的是通過 name = Alice 去查詢的時候:

  1. 走非主鍵索引去查詢,查詢完後拿到資訊(Alice, 18)。其實這裡也是一個非聚簇索引
  2. 然後進行回表查詢,再次通過主鍵去查詢做回表查詢。

兩個資料檔案:

.frm 主要是儲存表結構資訊

.ibd 主要是儲存索引和資料

MyISAM 索引檔案(非聚集)

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


MyISAM 儲存引擎索引.png

三個資料檔案:

.frm 資料結構檔案

.myd 檔案主要是儲存資料

.myi 檔案主要是儲存索引資訊

聚集索引和非聚集索引

特徵:

聚集/非聚集主要是索引檔案是否和資料檔案在一起。

查詢效率上來說聚集索引不會跨檔案查詢效率會更加快。

聯合/複合索引

多個欄位組織成一個共同的索引


組合索引.png

最左字首原理為什麼這樣來使用?

索引的資料是被排序的,如果跳過欄位的話是無法被使用的。

範例:

where name = 'Jeff' and age = 22              -- 命中索引

where age = 30  and postatin='manager'  -- 不命中索引

where postation = 'dev'                            -- 不命中索引

參考資料

百度百科

總結

到此這篇關於MySQL索引資料結構的文章就介紹到這了,更多相關MySQL索引資料結構內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com!


IT145.com E-mail:sddin#qq.com