第06章 索引的數據結構

来源:https://www.cnblogs.com/lengyingmofeng/archive/2023/04/03/17283412.html
-Advertisement-
Play Games

1. 為什麼使用索引 索引是存儲引擎用於快速找到數據記錄的一種數據結構，就好比一本教科書的目錄部分，通過目錄中找到對應文章的頁碼，便可快速定位到需要的文章。MySQL中也是一樣的道理，進行數據查找時，首先查看查詢條件是否命中某條索引，符合則通過索引查找相關數據，如果不符合則需要全表掃描，即需要一條一 ...


1. 為什麼使用索引

索引是存儲引擎用於快速找到數據記錄的一種數據結構，就好比一本教科書的目錄部分，通過目錄中找到對應文章的頁碼，便可快速定位到需要的文章。MySQL中也是一樣的道理，進行數據查找時，首先查看查詢條件是否命中某條索引，符合則通過索引查找相關數據，如果不符合則需要全表掃描，即需要一條一條地查找記錄，直到找到與條件符合的記錄。
image.png

如上圖所示，資料庫沒有索引的情況下，數據分佈在硬碟不同的位置上面，讀取數據時，擺臂需要前後擺動查詢數據，這樣操作非常消耗時間。如果數據順序擺放，那麼也需要從1到6行按順序讀取，這樣就相當於進行了6次IO操作，依舊非常耗時。如果我們不藉助任何索引結構幫助我們快速定位數據的話，我們查找 Col 2 = 89 這條記錄，就要逐行去查找、去比較。從Col 2 = 34 開始，進行比較，發現不是，繼續下一行。我們當前的表只有不到10行數據，但如果表很大的話，有上千萬條數據，就意味著要做很多很多次硬碟I/0才能找到。現在要查找 Col 2 = 89 這條記錄。CPU必須先去磁碟查找這條記錄，找到之後載入到記憶體，再對數據進行處理。這個過程最耗時間就是磁碟I/O（涉及到磁碟的旋轉時間（速度較快），磁頭的尋道時間(速度慢、費時)）

假如給數據使用 二叉樹 這樣的數據結構進行存儲，如下圖所示

image.png

對欄位 Col 2 添加了索引，就相當於在硬碟上為 Col 2 維護了一個索引的數據結構，即這個 二叉搜索樹。二叉搜索樹的每個結點存儲的是 (K, V) 結構，key 是 Col 2，value 是該 key 所在行的文件指針（地址）。比如：該二叉搜索樹的根節點就是：(34, 0x07)。現在對 Col 2 添加了索引，這時再去查找 Col 2 = 89 這條記錄的時候會先去查找該二叉搜索樹（二叉樹的遍歷查找）。讀 34 到記憶體，89 > 34; 繼續右側數據，讀 89 到記憶體，89==89；找到數據返回。找到之後就根據當前結點的 value 快速定位到要查找的記錄對應的地址。我們可以發現，只需要 查找兩次 就可以定位到記錄的地址，查詢速度就提高了。

這就是我們為什麼要建索引，目的就是為了 減少磁碟I/O的次數，加快查詢速率。

2. 索引及其優缺點

2.1 索引概述

MySQL官方對索引的定義為：索引（Index）是幫助MySQL高效獲取數據的數據結構。
索引的本質：索引是數據結構。你可以簡單理解為“排好序的快速查找數據結構”，滿足特定查找演算法。 這些數據結構以某種方式指向數據， 這樣就可以在這些數據結構的基礎上實現 高級查找演算法 。
索引是在存儲引擎中實現的，因此每種存儲引擎的索引不一定完全相同，並且每種存儲引擎不一定支持所有索引類型。同時，存儲引擎可以定義每個表的 最大索引數和 最大索引長度。所有存儲引擎支持每個表至少16個索引，總索引長度至少為256位元組。有些存儲引擎支持更多的索引數和更大的索引長度。

2.2 優點

（1）類似大學圖書館建書目索引，提高數據檢索的效率，降低 資料庫的IO成本 ，這也是創建索引最主 要的原因。
（2）通過創建唯一索引，可以保證資料庫表中每一行 數據的唯一性 。
（3）在實現數據的 參考完整性方面，可以 加速表和表之間的連接 。換句話說，對於有依賴關係的子表和父表聯合查詢時， 可以提高查詢速度。
（4）在使用分組和排序子句進行數據查詢時，可以顯著 減少查詢中分組和排序的時間 ，降低了CPU的消耗。

2.3 缺點

增加索引也有許多不利的方面，主要表現在如下幾個方面：
（1）創建索引和維護索引要 耗費時間 ，並 且隨著數據量的增加，所耗費的時間也會增加。
（2）索引需要占 磁碟空間 ，除了數據表占數據空間之 外，每一個索引還要占一定的物理空間， 存儲在磁碟上 ，如果有大量的索引，索引文件就可能比數據文 件更快達到最大文件尺寸。
（3）雖然索引大大提高了查詢速度，同時卻會 降低更新表的速度 。當對錶 中的數據進行增加、刪除和修改的時候，索引也要動態地維護，這樣就降低了數據的維護速度。 因此，選擇使用索引時，需要綜合考慮索引的優點和缺點。
因此，選擇使用索引時，需要綜合考慮索引的優點和缺點。

提示：
索引可以提高查詢的速度，但是會影響插入記錄的速度。這種情況下，最好的辦法是先刪除表中的索引，然後插入數據，插入完成後再創建索引。

3. InnoDB中索引的推演

3.1 索引之前的查找

先來看一個精確匹配的例子：

SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;

1. 在一個頁中的查找

假設目前表中的記錄比較少，所有的記錄都可以被存放到一個頁中，在查找記錄的時候可以根據搜索條件的不同分為兩種情況：

  • 以主鍵為搜索條件
    可以在頁目錄中使用 二分法 快速定位到對應的槽，然後再遍歷該槽對用分組中的記錄即可快速找到指定記錄。
  • 以其他列作為搜索條件
    因為在數據頁中並沒有對非主鍵列簡歷所謂的頁目錄，所以我們無法通過二分法快速定位相應的槽。這種情況下只能從 最小記錄 開始 依次遍歷單鏈表中的每條記錄， 然後對比每條記錄是不是符合搜索條件。很顯然，這種查找的效率是非常低的。

2. 在很多頁中查找

在很多頁中查找記錄的活動可以分為兩個步驟：

  1. 定位到記錄所在的頁。
  2. 從所在的頁內中查找相應的記錄。

在沒有索引的情況下，不論是根據主鍵列或者其他列的值進行查找，由於我們並不能快速的定位到記錄所在的頁，所以只能 從第一個頁沿著雙向鏈表 一直往下找，在每一個頁中根據我們上面的查找方式去查 找指定的記錄。因為要遍歷所有的數據頁，所以這種方式顯然是 超級耗時 的。如果一個表有一億條記錄呢？此時 索引 應運而生。

3.2 設計索引

建一個表：

mysql> CREATE TABLE index_demo(
  -> c1 INT,
  -> c2 INT,
  -> c3 CHAR(1),
  -> PRIMARY KEY(c1)
  -> ) ROW_FORMAT = Compact;

這個新建的 index_demo 表中有2個INT類型的列，1個CHAR(1)類型的列，而且我們規定了c1列為主鍵， 這個表使用 Compact 行格式來實際存儲記錄的。這裡我們簡化了index_demo表的行格式示意圖：

image.png

我們只在示意圖裡展示記錄的這幾個部分：

  • record_type ：記錄頭信息的一項屬性，表示記錄的類型， 0 表示普通記錄、 2 表示最小記 錄、 3 表示最大記錄、 1 暫時還沒用過，下麵講。
  • mysql> CREATE TABLE index_demo( -> c1 INT, -> c2 INT, -> c3 CHAR(1), -> PRIMARY KEY(c1) -> ) ROW_FORMAT = Compact; next_record ：記錄頭信息的一項屬性，表示下一條地址相對於本條記錄的地址偏移量，我們用 箭頭來表明下一條記錄是誰。
  • 各個列的值 ：這裡只記錄在 index_demo 表中的三個列，分別是 c1 、 c2 和 c3 。
  • 其他信息 ：除了上述3種信息以外的所有信息，包括其他隱藏列的值以及記錄的額外信息。

將記錄格式示意圖的其他信息項暫時去掉並把它豎起來的效果就是這樣：

image.png

把一些記錄放到頁里的示意圖就是：

image.png

1. 一個簡單的索引設計方案

我們在根據某個搜索條件查找一些記錄時為什麼要遍歷所有的數據頁呢？因為各個頁中的記錄並沒有規律，我們並不知道我們的搜索條件匹配哪些頁中的記錄，所以不得不依次遍歷所有的數據頁。所以如果我們 想快速的定位到需要查找的記錄在哪些數據頁 中該咋辦？我們可以為快速定位記錄所在的數據頁而建立一個目錄 ，建這個目錄必須完成下邊這些事：

  • 下一個數據頁中用戶記錄的主鍵值必須大於上一個頁中用戶記錄的主鍵值。
    假設：每個數據結構最多能存放3條記錄（實際上一個數據頁非常大，可以存放下好多記錄）。
INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');

那麼這些記錄以及按照主鍵值的大小串聯成一個單向鏈表了，如圖所示：

image.png

從圖中可以看出來， index_demo 表中的3條記錄都被插入到了編號為10的數據頁中了。此時我們再來插入一條記錄

INSERT INTO index_demo VALUES(4, 4, 'a');

因為 頁10 最多只能放3條記錄，所以我們不得不再分配一個新頁：

image.png

註意：新分配的 數據頁編號可能並不是連續的。它們只是通過維護者上一個頁和下一個頁的編號而建立了 鏈表 關係。另外，頁10中用戶記錄最大的主鍵值是5，而頁28中有一條記錄的主鍵值是4，因為5>4，所以這就不符合下一個數據頁中用戶記錄的主鍵值必須大於上一個頁中用戶記錄的主鍵值的要求，所以在插入主鍵值為4的記錄的時候需要伴隨著一次 記錄移動，也就是把主鍵值為5的記錄移動到頁28中，然後再把主鍵值為4的記錄插入到頁10中，這個過程的示意圖如下：

image.png

這個過程表明瞭在對頁中的記錄進行增刪改查操作的過程中，我們必須通過一些諸如 記錄移動 的操作來始終保證這個狀態一直成立：下一個數據頁中用戶記錄的主鍵值必須大於上一個頁中用戶記錄的主鍵值。這個過程稱為 頁分裂。

  • 給所有的頁建立一個目錄項。

由於數據頁的 編號可能是不連續 的，所以在向 index_demo 表中插入許多條記錄後，可能是這樣的效果：

image.png

我們需要給它們做個 目錄，每個頁對應一個目錄項，每個目錄項包括下邊兩個部分：

1）頁的用戶記錄中最小的主鍵值，我們用 key 來表示。

2）頁號，我們用 page_on 表示。

image.png

以 頁28 為例，它對應 目錄項2 ，這個目錄項中包含著該頁的頁號 28 以及該頁中用戶記錄的最小主 鍵值 5 。我們只需要把幾個目錄項在物理存儲器上連續存儲（比如：數組），就可以實現根據主鍵 值快速查找某條記錄的功能了。比如：查找主鍵值為 20 的記錄，具體查找過程分兩步：

  1. 先從目錄項中根據 二分法 快速確定出主鍵值為 20 的記錄在 目錄項3 中（因為 12 < 20 < 209 ），它對應的頁是 頁9 。
  2. 再根據前邊說的在頁中查找記錄的方式去 頁9 中定位具體的記錄。

至此，針對數據頁做的簡易目錄就搞定了。這個目錄有一個別名，稱為 索引 。

2. InnoDB中的索引方案

① 迭代1次：目錄項紀錄的頁

InnoDB怎麼區分一條記錄是普通的 用戶記錄 還是 目錄項記錄 呢？使用記錄頭信息里的 record_type 屬性，它的各自取值代表的意思如下：

  • 0：普通的用戶記錄
  • 1：目錄項記錄
  • 2：最小記錄
  • 3：最大記錄

我們把前邊使用到的目錄項放到數據頁中的樣子就是這樣：

image.png

從圖中可以看出來，我們新分配了一個編號為30的頁來專門存儲目錄項記錄。這裡再次強調 目錄項記錄 和普通的 用戶記錄 的不同點：

  • 目錄項記錄 的 record_type 值是1，而 普通用戶記錄 的 record_type 值是0。
  • 目錄項記錄只有 主鍵值和頁的編號 兩個列，而普通的用戶記錄的列是用戶自己定義的，可能包含 很多列 ，另外還有InnoDB自己添加的隱藏列。
  • 瞭解：記錄頭信息里還有一個叫 min_rec_mask 的屬性，只有在存儲 目錄項記錄 的頁中的主鍵值最小的 目錄項記錄 的 min_rec_mask 值為 1 ，其他別的記錄的 min_rec_mask 值都是 0 。

相同點：兩者用的是一樣的數據頁，都會為主鍵值生成 Page Directory （頁目錄），從而在按照主鍵值進行查找時可以使用 二分法 來加快查詢速度。

現在以查找主鍵為 20 的記錄為例，根據某個主鍵值去查找記錄的步驟就可以大致拆分成下邊兩步：

  1. 先到存儲 目錄項記錄 的頁，也就是頁30中通過 二分法 快速定位到對應目錄項，因為 12 < 20 < 209 ，所以定位到對應的記錄所在的頁就是頁9。
  2. 再到存儲用戶記錄的頁9中根據 二分法 快速定位到主鍵值為 20 的用戶記錄。
② 迭代2次：多個目錄項紀錄的頁

image.png

從圖中可以看出，我們插入了一條主鍵值為320的用戶記錄之後需要兩個新的數據頁：

  • 為存儲該用戶記錄而新生成了 頁31 。
  • 因為原先存儲目錄項記錄的 頁30的容量已滿 （我們前邊假設只能存儲4條目錄項記錄），所以不得 不需要一個新的 頁32 來存放 頁31 對應的目錄項。

現在因為存儲目錄項記錄的頁不止一個，所以如果我們想根據主鍵值查找一條用戶記錄大致需要3個步驟，以查找主鍵值為 20 的記錄為例：

  1. 確定 目錄項記錄頁 我們現在的存儲目錄項記錄的頁有兩個，即 頁30 和 頁32 ，又因為頁30表示的目錄項的主鍵值的 範圍是 [1, 320) ，頁32表示的目錄項的主鍵值不小於 320 ，所以主鍵值為 20 的記錄對應的目 錄項記錄在 頁30 中。
  2. 通過目錄項記錄頁 確定用戶記錄真實所在的頁 。 在一個存儲 目錄項記錄 的頁中通過主鍵值定位一條目錄項記錄的方式說過了。
  3. 在真實存儲用戶記錄的頁中定位到具體的記錄。
③ 迭代3次：目錄項記錄頁的目錄頁

如果我們表中的數據非常多則會產生很多存儲目錄項記錄的頁，那我們怎麼根據主鍵值快速定位一個存儲目錄項記錄的頁呢？那就為這些存儲目錄項記錄的頁再生成一個更高級的目錄，就像是一個多級目錄一樣，大目錄里嵌套小目錄，小目錄里才是實際的數據，所以現在各個頁的示意圖就是這樣子：

image.png

如圖，我們生成了一個存儲更高級目錄項的 頁33 ，這個頁中的兩條記錄分別代表頁30和頁32，如果用 戶記錄的主鍵值在 [1, 320) 之間，則到頁30中查找更詳細的目錄項記錄，如果主鍵值 不小於320 的 話，就到頁32中查找更詳細的目錄項記錄。

我們可以用下邊這個圖來描述它：

image.png

這個數據結構，它的名稱是 B+樹 。

④ B+Tree

一個B+樹的節點其實可以分成好多層，規定最下邊的那層，也就是存放我們用戶記錄的那層為第 0 層， 之後依次往上加。之前我們做了一個非常極端的假設：存放用戶記錄的頁 最多存放3條記錄 ，存放目錄項 記錄的頁 最多存放4條記錄 。其實真實環境中一個頁存放的記錄數量是非常大的，假設所有存放用戶記錄 的葉子節點代表的數據頁可以存放 100條用戶記錄 ，所有存放目錄項記錄的內節點代表的數據頁可以存 放 1000條目錄項記錄 ，那麼：

  • 如果B+樹只有1層，也就是只有1個用於存放用戶記錄的節點，最多能存放 100 條記錄。
  • 如果B+樹有2層，最多能存放 1000×100=10,0000 條記錄。
  • 如果B+樹有3層，最多能存放 1000×1000×100=1,0000,0000 條記錄。
  • 如果B+樹有4層，最多能存放 1000×1000×1000×100=1000,0000,0000 條記錄。相當多的記錄！

你的表裡能存放 100000000000 條記錄嗎？所以一般情況下，我們用到的 B+樹都不會超過4層 ，那我們通過主鍵值去查找某條記錄最多只需要做4個頁面內的查找（查找3個目錄項頁和一個用戶記錄頁），又因為在每個頁面內有所謂的 Page Directory （頁目錄），所以在頁面內也可以通過 二分法 實現快速 定位記錄。

3.3 常見索引概念

索引按照物理實現方式，索引可以分為 2 種：聚簇（聚集）和非聚簇（非聚集）索引。我們也把非聚集 索引稱為二級索引或者輔助索引。

1. 聚簇索引

聚簇索引並不是一種單獨的索引類型，而是一種數據存儲方式（所有的用戶記錄都存儲在了葉子結點），也就是所謂的 索引即數據，數據即索引。

術語"聚簇"表示當前數據行和相鄰的鍵值聚簇的存儲在一起

特點：

  • 使用記錄主鍵值的大小進行記錄和頁的排序，這包括三個方面的含義：
    • 頁內 的記錄是按照主鍵的大小順序排成一個 單向鏈表 。
    • 各個存放 用戶記錄的頁 也是根據頁中用戶記錄的主鍵大小順序排成一個 雙向鏈表 。
    • 存放 目錄項記錄的頁 分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的主鍵大小順序排成一個 雙向鏈表 。
  • B+樹的 葉子節點 存儲的是完整的用戶記錄。
    所謂完整的用戶記錄，就是指這個記錄中存儲了所有列的值（包括隱藏列）。

我們把具有這兩種特性的B+樹稱為聚簇索引，所有完整的用戶記錄都存放在這個聚簇索引的葉子節點處。這種聚簇索引並不需要我們在MySQL語句中顯式的使用INDEX 語句去創建， InnDB 存儲引擎會 自動 的為我們創建聚簇索引。

優點：

  • 數據訪問更快 ，因為聚簇索引將索引和數據保存在同一個B+樹中，因此從聚簇索引中獲取數據比非聚簇索引更快
  • 聚簇索引對於主鍵的 排序查找 和 範圍查找 速度非常快
  • 按照聚簇索引排列順序，查詢顯示一定範圍數據的時候，由於數據都是緊密相連，資料庫不用從多 個數據塊中提取數據，所以 節省了大量的io操作 。

缺點：

  • 插入速度嚴重依賴於插入順序 ，按照主鍵的順序插入是最快的方式，否則將會出現頁分裂，嚴重影響性能。因此，對於InnoDB表，我們一般都會定義一個自增的ID列為主鍵
  • 更新主鍵的代價很高 ，因為將會導致被更新的行移動。因此，對於InnoDB表，我們一般定義主鍵為不可更新
  • 二級索引訪問需要兩次索引查找 ，第一次找到主鍵值，第二次根據主鍵值找到行數據

2. 二級索引（輔助索引、非聚簇索引）

如果我們想以別的列作為搜索條件該怎麼辦？肯定不能是從頭到尾沿著鏈表依次遍歷記錄一遍。

答案：我們可以多建幾顆B+樹，不同的B+樹中的數據採用不同的排列規則。比方說我們用c2列的大小作為數據頁、頁中記錄的排序規則，再建一課B+樹，效果如下圖所示：

image.png

這個B+樹與上邊介紹的聚簇索引有幾處不同：

image.png

**概念：回表 **

我們根據這個以c2列大小排序的B+樹只能確定我們要查找記錄的主鍵值，所以如果我們想根 據c2列的值查找到完整的用戶記錄的話，仍然需要到 聚簇索引 中再查一遍，這個過程稱為 回表 。也就 是根據c2列的值查詢一條完整的用戶記錄需要使用到 2 棵B+樹！

問題：為什麼我們還需要一次 回表 操作呢？直接把完整的用戶記錄放到葉子節點不OK嗎？

回答：

如果把完整的用戶記錄放到葉子結點是可以不用回表。但是太占地方了，相當於每建立一課B+樹都需要把所有的用戶記錄再都拷貝一遍，這就有點太浪費存儲空間了。

因為這種按照非主鍵列建立的B+樹需要一次回表操作才可以定位到完整的用戶記錄，所以這種B+樹也被稱為二級索引，或者輔助索引。由於使用的是c2列的大小作為B+樹的排序規則，所以我們也稱這個B+樹為c2列簡歷的索引。

非聚簇索引的存在不影響數據在聚簇索引中的組織，所以一張表可以有多個非聚簇索引。

image.png

小結：聚簇索引與非聚簇索引的原理不同，在使用上也有一些區別：

  1. 聚簇索引的葉子節點存儲的就是我們的數據記錄, 非聚簇索引的葉子節點存儲的是數據位置。非聚簇索引不會影響數據表的物理存儲順序。
  2. 一個表只能有一個聚簇索引，因為只能有一種排序存儲的方式，但可以有多個非聚簇索引，也就是多個索引目錄提供數據檢索。
  3. 使用聚簇索引的時候，數據的查詢效率高，但如果對數據進行插入，刪除，更新等操作，效率會比非聚簇索引低。

3.聯合索引

我們也可以同時以多個列的大小作為排序規則，也就是同時為多個列建立索引，比方說我們想讓B+樹按 照 c2和c3列 的大小進行排序，這個包含兩層含義：

  • 先把各個記錄和頁按照c2列進行排序。
  • 在記錄的c2列相同的情況下，採用c3列進行排序

為c2和c3建立的索引的示意圖如下：

image.png

如圖所示，我們需要註意以下幾點：

  • 每條目錄項都有c2、c3、頁號這三個部分組成，各條記錄先按照c2列的值進行排序，如果記錄的c2列相同，則按照c3列的值進行排序
  • B+樹葉子節點處的用戶記錄由c2、c3和主鍵c1列組成

註意一點，以c2和c3列的大小為排序規則建立的B+樹稱為 聯合索引 ，本質上也是一個二級索引。它的意 思與分別為c2和c3列分別建立索引的表述是不同的，不同點如下：

  • 建立 聯合索引 只會建立如上圖一樣的1棵B+樹。
  • 為c2和c3列分別建立索引會分別以c2和c3列的大小為排序規則建立2棵B+樹。

3.4 InnoDB的B+樹索引的註意事項

1. 根頁面位置萬年不動

實際上B+樹的形成過程是這樣的：

  • 每當為某個表創建一個B+樹索引（聚簇索引不是人為創建的，預設就有）的時候，都會為這個索引創建一個 根結點 頁面。最開始表中沒有數據的時候，每個B+樹索引對應的 根結點 中即沒有用戶記錄，也沒有目錄項記錄。
  • 隨後向表中插入用戶記錄時，先把用戶記錄存儲到這個根節點 中。
  • 當根節點中的可用 空間用完時 繼續插入記錄，此時會將根節點中的所有記錄複製到一個新分配的頁，比如 頁a 中，然後對這個新頁進行 頁分裂 的操作，得到另一個新頁，比如頁b 。這時新插入的記錄根據鍵值（也就是聚簇索引中的主鍵值，二級索引中對應的索引列的值）的大小就會被分配到 頁a 或者 頁b 中，而 根節點 便升級為存儲目錄項記錄的頁。

這個過程特別註意的是：一個B+樹索引的根節點自誕生之日起，便不會再移動。這樣只要我們對某個表建議一個索引，那麼它的根節點的頁號便會被記錄到某個地方。然後凡是 InnoDB 存儲引擎需要用到這個索引的時候，都會從哪個固定的地方取出根節點的頁號，從而來訪問這個索引。

2. 內節點中目錄項記錄的唯一性

我們知道B+樹索引的內節點中目錄項記錄的內容是 索引列 + 頁號 的搭配，但是這個搭配對於二級索引來說有點不嚴謹。還拿 index_demo 表為例，假設這個表中的數據是這樣的：

image.png

如果二級索引中目錄項記錄的內容只是 索引列 + 頁號 的搭配的話，那麼為 c2 列簡歷索引後的B+樹應該長這樣：

image.png

如果我們想新插入一行記錄，其中 c1 、c2 、c3 的值分別是: 9、1、c, 那麼在修改這個為 c2 列建立的二級索引對應的 B+ 樹時便碰到了個大問題：由於 頁3 中存儲的目錄項記錄是由 c2列 + 頁號 的值構成的，頁3 中的兩條目錄項記錄對應的 c2 列的值都是1，而我們 新插入的這條記錄 的 c2 列的值也是 1，那我們這條新插入的記錄到底應該放在 頁4 中，還是應該放在 頁5 中？答案：對不起，懵了

為了讓新插入記錄找到自己在那個頁面，我們需要保證在B+樹的同一層頁節點的目錄項記錄除頁號這個欄位以外是唯一的。所以對於二級索引的內節點的目錄項記錄的內容實際上是由三個部分構成的：

  • 索引列的值
  • 主鍵值
  • 頁號

也就是我們把主鍵值也添加到二級索引內節點中的目錄項記錄，這樣就能保住 B+ 樹每一層節點中各條目錄項記錄除頁號這個欄位外是唯一的，所以我們為c2建立二級索引後的示意圖實際上應該是這樣子的：

image.png

這樣我們再插入記錄(9, 1, 'c') 時，由於 頁3 中存儲的目錄項記錄是由 c2列 + 主鍵 + 頁號 的值構成的，可以先把新紀錄的 c2 列的值和 頁3 中各目錄項記錄的 c2 列的值作比較，如果 c2 列的值相同的話，可以接著比較主鍵值，因為B+樹同一層中不同目錄項記錄的 c2列 + 主鍵的值肯定是不一樣的，所以最後肯定能定位唯一的一條目錄項記錄，在本例中最後確定新紀錄應該被插入到 頁5 中。

3. 一個頁面最少存儲 2 條記錄

一個B+樹只需要很少的層級就可以輕鬆存儲數億條記錄，查詢速度相當不錯！這是因為B+樹本質上就是一個大的多層級目錄，每經過一個目錄時都會過濾掉許多無效的子目錄，直到最後訪問到存儲真實數據的目錄。那如果一個大的目錄中只存放一個子目錄是個啥效果呢？那就是目錄層級非常非常多，而且最後的那個存放真實數據的目錄中只存放一條數據。所以 InnoDB 的一個數據頁至少可以存放兩條記錄。

4. MyISAM中的索引方案

B樹索引使用存儲引擎如表所示：

索引 / 存儲引擎 MyISAM InnoDB Memory
B-Tree索引 支持 支持 支持

即使多個存儲引擎支持同一種類型的索引，但是他們的實現原理也是不同的。Innodb和MyISAM預設的索 引是Btree索引；而Memory預設的索引是Hash索引。

MyISAM引擎使用 B+Tree 作為索引結構，葉子節點的data域存放的是 數據記錄的地址 。

4.1 MyISAM索引的原理

image.png

image.png

image.png

image.png

同樣也是一顆B+Tree，data域保存數據記錄的地址。因此，MySAM中索引檢索的演算法為：首先按照B+Tree搜素演算法搜索索引，如果指定的Key存在，則取出其data域的值，然後以data域的值為地址，讀取相應的數據記錄。

4.2 MyISAM 與 InnoDB對比

MyISAM的索引方式都是“非聚簇”的，與InnoDB包含1個聚簇索引是不同的。小結兩種引擎中索引的區別：

① 在InnoDB存儲引擎中，我們只需要根據主鍵值對 聚簇索引 進行一次查找就能找到對應的記錄，而在 MyISAM 中卻需要進行一次 回表 操作，意味著MyISAM中建立的索引相當於全部都是 二級索引 。

② InnoDB的數據文件本身就是索引文件，而MyISAM索引文件和數據文件是 分離的 ，索引文件僅保存數 據記錄的地址。

③ InnoDB的非聚簇索引data域存儲相應記錄 主鍵的值 ，而MyISAM索引記錄的是 地址 。換句話說， InnoDB的所有非聚簇索引都引用主鍵作為data域。

④ MyISAM的回表操作是十分 快速 的，因為是拿著地址偏移量直接到文件中取數據的，反觀InnoDB是通 過獲取主鍵之後再去聚簇索引里找記錄，雖然說也不慢，但還是比不上直接用地址去訪問。

⑤ InnoDB要求表 必須有主鍵 （ MyISAM可以沒有 ）。如果沒有顯式指定，則MySQL系統會自動選擇一個 可以非空且唯一標識數據記錄的列作為主鍵。如果不存在這種列，則MySQL自動為InnoDB表生成一個隱 含欄位作為主鍵，這個欄位長度為6個位元組，類型為長整型。

小結：

image.png

image.png

5. 索引的代價

索引是個好東西，可不能亂建，它在空間和時間上都會有消耗：

  • 空間上的代價
    每建立一個索引都要為它建立一棵B+樹，每一棵B+樹的每一個節點都是一個數據頁，一個頁預設會 占用 16KB 的存儲空間，一棵很大的B+樹由許多數據頁組成，那就是很大的一片存儲空間。
  • 時間上的代價
    每次對錶中的數據進行 增、刪、改 操作時，都需要去修改各個B+樹索引。而且我們講過，B+樹每 層節點都是按照索引列的值 從小到大的順序排序 而組成了 雙向鏈表 。不論是葉子節點中的記錄，還 是內節點中的記錄（也就是不論是用戶記錄還是目錄項記錄）都是按照索引列的值從小到大的順序 而形成了一個單向鏈表。而增、刪、改操作可能會對節點和記錄的排序造成破壞，所以存儲引擎需 要額外的時間進行一些 記錄移位 ， 頁面分裂 、 頁面回收 等操作來維護好節點和記錄的排序。如果 我們建了許多索引，每個索引對應的B+樹都要進行相關的維護操作，會給性能拖後腿。

一個表上索引建的越多，就會占用越多的存儲空間，在增刪改記錄的時候性能就越差。為了能建立又好又少的索引，我們得學學這些索引在哪些條件下起作用的。

6. MySQL數據結構選擇的合理性

image.png

6.1 全表查詢

這裡都懶得說了。

6.2 Hash查詢

image.png

加快查找速度的數據結構，常見的有兩類：

(1) 樹，例如平衡二叉搜索樹，查詢/插入/修改/刪除的平均時間複雜度都是 O(log2N);

(2)哈希，例如HashMap，查詢/插入/修改/刪除的平均時間複雜度都是 O(1); (key, value)

image.png
image.png

image.png

上圖中哈希函數h有可能將兩個不同的關鍵字映射到相同的位置，這叫做 碰撞 ，在資料庫中一般採用 鏈 接法 來解決。在鏈接法中，將散列到同一槽位的元素放在一個鏈表中，如下圖所示：

image.png

實驗：體會數組和hash表的查找方面的效率區別

// 演算法複雜度為 O(n)
@Test
    public void test1(){
    int[] arr = new int[100000];
    for(int i = 0;i < arr.length;i++){
        arr[i] = i + 1;
    }
    long start = System.currentTimeMillis();
    for(int j = 1; j<=100000;j++){
        int temp = j;
        for(int i = 0;i < arr.length;i++){
            if(temp == arr[i]){
                break;
            }
        }
    }
    long end = System.currentTimeMillis();
    System.out.println("time： " + (end - start)); //time： 823
}

// 演算法複雜度為 O(1)
@Test
    public void test2(){
    HashSet<Integer> set = new HashSet<>(100000);
    for(int i = 0;i < 100000;i++){
        set.add(i + 1);
    }
    long start = System.currentTimeMillis();
    for(int j = 1; j<=100000;j++) {
        int temp = j;
        boolean contains = set.contains(temp);
    }
    long end = System.currentTimeMillis();
    System.out.println("time： " + (end - start)); //time： 5
}

Hash結構效率高，那為什麼索引結構要設計成樹型呢？

image.png

Hash索引適用存儲引擎如表所示：

索引 / 存儲引擎 MyISAM InnoDB Memory
HASH索引 不支持 不支持 支持

Hash索引的適用性：

image.png

image.png

採用自適應 Hash 索引目的是方便根據 SQL 的查詢條件加速定位到葉子節點，特別是當 B+ 樹比較深的時 候，通過自適應 Hash 索引可以明顯提高數據的檢索效率。

我們可以通過 innodb_adaptive_hash_index 變數來查看是否開啟了自適應 Hash，比如：

mysql> show variables like '%adaptive_hash_index';

6.3 二叉搜索樹

如果我們利用二叉樹作為索引結構，那麼磁碟的IO次數和索引樹的高度是相關的。

1. 二叉搜索樹的特點

  • 一個節點只能有兩個子節點，也就是一個節點度不能超過2
  • 左子節點 < 本節點; 右子節點 >= 本節點，比我大的向右，比我小的向左

2. 查找規則

image.png

image.png

但是特殊情況，就是有時候二叉樹的深度非常大，比如：

image.png

為了提高查詢效率，就需要 減少磁碟IO數 。為了減少磁碟IO的次數，就需要儘量 降低樹的高度 ，需要把 原來“瘦高”的樹結構變的“矮胖”，樹的每層的分叉越多越好。

6.4 AVL樹

image.png

image.png

`每訪問一次節點就需要進行一次磁碟 I/O 操作，對於上面的樹來說，我們需要進行 5次 I/O 操作。雖然平衡二叉樹的效率高，但是樹的深度也同樣高，這就意味著磁碟 I/O 操作次數多，會影響整體數據查詢的效率。

針對同樣的數據，如果我們把二叉樹改成 M 叉樹 （M>2）呢？當 M=3 時，同樣的 31 個節點可以由下麵 的三叉樹來進行存儲：

image.png

你能看到此時樹的高度降低了，當數據量 N 大的時候，以及樹的分叉樹 M 大的時候，M叉樹的高度會遠小於二叉樹的高度 (M > 2)。所以，我們需要把 `樹從“瘦高” 變 “矮胖”。

6.5 B-Tree

B 樹的英文是 Balance Tree，也就是 多路平衡查找樹。簡寫為 B-Tree。它的高度遠小於平衡二叉樹的高度。

B 樹的結構如下圖所示：

image.png

image.png

一個 M 階的 B 樹（M>2）有以下的特性：

  1. 根節點的兒子數的範圍是 [2,M]。
  2. 每個中間節點包含 k-1 個關鍵字和 k 個孩子，孩子的數量 = 關鍵字的數量 +1，k 的取值範圍為 [ceil(M/2), M]。
  3. 葉子節點包括 k-1 個關鍵字（葉子節點沒有孩子），k 的取值範圍為 [ceil(M/2), M]。
  4. 假設中間節點節點的關鍵字為：Key[1], Key[2], …, Key[k-1]，且關鍵字按照升序排序，即 Key[i]<Key[i+1]。此時 k-1 個關鍵字相當於劃分了 k 個範圍，也就是對應著 k 個指針，即為：P[1], P[2], …, P[k]，其中 P[1] 指向關鍵字小於 Key[1] 的子樹，P[i] 指向關鍵字屬於 (Key[i-1], Key[i]) 的子樹，P[k] 指向關鍵字大於 Key[k-1] 的子樹。
  5. 所有葉子節點位於同一層。

上面那張圖所表示的 B 樹就是一棵 3 階的 B 樹。我們可以看下磁碟塊 2，裡面的關鍵字為（8，12），它 有 3 個孩子 (3，5)，(9，10) 和 (13，15)，你能看到 (3，5) 小於 8，(9，10) 在 8 和 12 之間，而 (13，15) 大於 12，剛好符合剛纔我們給出的特征。

然後我們來看下如何用 B 樹進行查找。假設我們想要 查找的關鍵字是 9 ，那麼步驟可以分為以下幾步：

  1. 我們與根節點的關鍵字 (17，35）進行比較，9 小於 17 那麼得到指針 P1；
  2. 按照指針 P1 找到磁碟塊 2，關鍵字為（8，12），因為 9 在 8 和 12 之間，所以我們得到指針 P2；
  3. 按照指針 P2 找到磁碟塊 6，關鍵字為（9，10），然後我們找到了關鍵字 9。

你能看出來在 B 樹的搜索過程中，我們比較的次數並不少，但如果把數據讀取出來然後在記憶體中進行比 較，這個時間就是可以忽略不計的。而讀取磁碟塊本身需要進行 I/O 操作，消耗的時間比在記憶體中進行 比較所需要的時間要多，是數據查找用時的重要因素。 B 樹相比於平衡二叉樹來說磁碟 I/O 操作要少 ， 在數據查詢中比平衡二叉樹效率要高。所以 只要樹的高度足夠低，IO次數足夠少，就可以提高查詢性能 。

image.png

再舉例1：

image.png

6.6 B+Tree

image.png

  • MySQL官網說明：

image.png

B+ 樹和 B 樹的差異在於以下幾點：

  1. 有 k 個孩子的節點就有 k 個關鍵字。也就是孩子數量 = 關鍵字數，而 B 樹中，孩子數量 = 關鍵字數 +1。
  2. 非葉子節點的關鍵字也會同時存在在子節點中，並且是在子節點中所有關鍵字的最大（或最 小）。
  3. 非葉子節點僅用於索引，不保存數據記錄，跟記錄有關的信息都放在葉子節點中。而 B 樹中， 非 葉子節點既保存索引，也保存數據記錄 。
  4. 所有關鍵字都在葉子節點出現，葉子節點構成一個有序鏈表，而且葉子節點本身按照關鍵字的大 小從小到大順序鏈接。

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Java的運行時數據區域
    本文從概念上介紹 Java 虛擬機記憶體的各個區域，講解這些區域的作用、服務對象以及其中可能產生的問題。 Java 虛擬機在執行 Java 程式的過程中會把它所管理的記憶體劃分為若幹個不同的數據區域。這些區域有各自的用途，以及創建和銷毀的時間，有些區域隨著虛擬機進程的啟動而一直存在，有些區域則是依賴用戶 ...
  • 【代碼設計】C# 實現 AOP 面向切麵編程
    簡單記錄一下對AOP的認識，正文為3個部分 一、AOP由來 二、用DispatchProxy動態代理實現AOP 三、通過特性標記，處理多種不同執行前、執行後的邏輯編排 一、AOP 由來 IUserHelper userHelper = new CommonUserHelper(); // commo ...
  • dmesg 時間誤差現象
    案例現象 這天收到監控平臺發來的告警，說有台機器程式崩潰了 因為以前也有過相關的錯誤，根據經驗，用 dmesg命令看下內核信息 發現有點不對勁，報錯信息的時間跟告警時間不一致，正常來講報錯時間應該跟告警時間一致 使用 date 命令查看一下當前系統時間 然後我們查看一下系統日誌 由上面的輸出可以看到 ...
  • Neovim，要嘗一口不？
    Neovim 風評很好，我機器上其實早裝了它來替代 vim。只不過這兩年用 vscode 較多，冷落了它，除了偶爾改改配置文件，很少用。難得大過年的有點兒空，就來倒騰它一下子，最終效果如下。 基礎配置 從 0.5 版開始，Neovim 允許使用 Lua 代替 VimL 作為配置語言，所以這裡也直接從 ...
  • win10計劃任務程式庫實現定時任務的自動執行程式及問題解決。
    win10計劃任務程式庫可以實現按照規則頻率執行腳本的功能。現在將設置方法記錄如下： 創建任務步驟 1、右鍵點擊我的電腦，選擇管理，依次點擊：系統工具-》任務計劃程式-》任務計劃程式庫。 2、點擊最右側操作中的創建基本任務，打開下麵的彈窗。 3、創建任務的基本信息，下一步選擇任務執行的頻率和開始時間 ...
  • 讀SQL進階教程筆記07_EXISTS謂詞
    1. 特點 1.1. 將多行數據作為整體來表達高級的條件 1.2. 使用關聯子查詢時性能仍然非常好 1.3. EXISTS的參數不像是單一值 1.3.1. 參數是行數據的集合 2. 什麼是謂詞 2.1. 一種特殊的函數，返回值是真值 2.2. 返回值都是true、false或者unknown 2.2 ...
  • MYSQL基礎知識之DDL語句
    一、DDL概念 DDL（Data Definition Language）語言：數據定義語言，用來定義資料庫對象，如資料庫、數據表和數據欄位，主要是進行定義/改變表的結構、數據類型、表之間的鏈接等操作。常用的語句關鍵字有 CREATE、DROP、ALTER 等。 二、資料庫操作 2.1、linux環 ...
  • MySQL使用DROP TABLE命令刪除表怎麼恢復？
    軟體下載地址：（如果連接失效，請公眾號內私聊獲取） 鏈接：https://pan.baidu.com/s/10KQ0-N9iYz5PDdaNBWqHVA 提取碼：1234 解壓後如下： 勾選項如下： 破解和漢化操作步驟： 1、軟體已經正確安裝，首次啟動如圖，先點擊試用： 2、啟動會讓你選擇一個主題， ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類