本篇文章博主對索引做了一個較為初步的概述，主要有2種主要的索引的數據結構b+tree和hash的數據結構，B+樹的覆蓋索引和回表進行分析，並對b+樹存放記錄、如何優化B+樹索引的插入性能進行分析。

一、 MySQL索引數據結構模型

眾所周知，資料庫查詢是資料庫的核心功能，索引是加速查詢的重要技術手段。

MySQL對索引的官方定義是存儲引擎用來快速查找記錄的數據結構。一般來說，索引類似於圖書目錄。它以增加寫入和存儲空間為代價，提高了資料庫表上數據檢索操作的速度。您可以根據其中記錄的頁碼快速找到所需內容。

索引是物理數據頁，資料庫頁面大小決定了頁面可以存儲多少索引行，以及存儲指定大小的索引需要多少頁面。索引數據結構選擇的本質是根據當前數據讀寫的硬體環境，選擇一個優秀的數據結構進行數據存儲和遍歷。

索引可以加快檢索速度，但也可以降低插入、刪除和更新索引列的速度。索引同時維護需要一定成本。

資料庫中的大多數索引都是通過B+Tree實現的。當然，還涉及其他數據結構，索引涉及的理論知識包括哈希表和B+樹。

1、B+Tree（B+樹）索引

B+ 樹索引是資料庫中最常見的索引數據結構，為什麼關係資料庫熱衷於支持B+樹索引？

與二叉樹、散列索引、紅黑樹和SkipList相比，在基於磁碟的海量數據存儲效率方面遠不如B+樹索引，因此，上述數據結構通常僅用於內存對象。

對於基於磁碟的數據排序和存儲，最有效的仍然是B+樹索引。B+樹索引的特點是基於磁碟的平衡樹，樹通常為3到4層，可以存儲數千萬到數億的排序數據。樹短意味著訪問效率高。從數千萬或數億數據中查詢一條數據只需要3或4個I/O。

因為SSD（固態硬碟）每秒可以執行至少10000個I/O，所以查詢一段數據只需要0.003到0.004秒，即使數據都在磁碟上。此外，由於B+樹較短，在排序時，它只需要比較3到4次，就能找到需要插入數據的位置。分揀效率非常好。

B+樹索引由根節點、非葉節點和葉節點組成，其中葉節點存儲所有排序的數據。

所有B+樹都從高度為1開始，然後根據數據的插入慢慢增加樹的高度。索引用於對記錄進行排序，高度為1的B+樹索引中存儲的記錄已排序，如果想在葉節點中進行查詢，您可以只通過二進位搜索快速找到數據。

當一個頁面（16K）無法存儲如此多的數據，因此B+樹將分裂。B+樹的高度將變為2。當B+樹高度大於或等於2時，根節點和中間節點存儲由（索引鍵和指針）組成的索引鍵對。索引鍵是已排序的列，指針是指向下一層的地址，這在MySQL的InnoDB存儲引擎中占用了6個字節。

2、Hash 索引

哈希表是資料庫中哈希索引的基礎。它是根據鍵值＜key，value＞存儲數據的結構。

使用哈希函數計算桶或槽的索引列的數組。實際的存儲是根據哈希函數將 key 轉換為確定的存儲位置，並將值存儲在數組位置。訪問時，只需要輸入要搜索的 key ，然後就可以通過哈希函數計算確定的存儲位置並讀取數據。

在 MySQL 中主要是分為三種哈希索引：

• Memory 存儲引擎原生支持的 Hash 索引
• InnoDB 自適應哈希索引
• NDB 集群的哈希索引

3、InnoDB 自適應哈希索引

InnoDB 自適應哈希索引旨在提高查詢效率。

InnoDB 存儲引擎將監視表上每個索引頁的查詢。當 InnoDB 注意到某些索引值被非常頻繁地訪問時，將基於B+樹索引在內存中創建另一個哈希索引，從而使內存中的B+樹具有哈希索引的功能，即可以快速訪問具有固定值的頻繁訪問的索引頁。

為什麼要為B+樹索引頁創建自適應哈希索引？

這是因為B+樹索引的查詢效率取決於B+樹的高度，在資料庫中B+樹的高度通常為3到4層，因此需要執行3到4個查詢才能訪問數據。

哈希索引可以在單個搜索中定位數據（沒有哈希衝突），並且哈希索引在其等效查詢場景中的查詢效率優於B+樹。

自適應散列索引的建立使 InnoDB 存儲引擎能夠根據索引頁訪問的頻率自動為熱點頁創建散列索引，以加快訪問速度。

二、B+ 樹索引理論上每層最多能存放多少行記錄

根節點最多可以存儲鍵值對 = 16K/鍵值對大小（8+6）≈ 1100

葉節點存儲的最大記錄數 = 16K/每條記錄的大小 ≈ 32

總記錄數 = 根節點最多可以存儲以下多個鍵值對 * 葉節點最多可以保存以下多個鍵值對

所以二層是1100*32 = 35200

樹高為3的B+樹索引中可以存儲的最大記錄數為：總記錄數=1100（根節點）*1100（中間節點）*32 = 38720000

樹高為4的B+樹索引中可以存儲的最大記錄數為：總記錄數=1100（根節點）*1100（中間節點）*1100（根節點）*32 = 42592000000

不過，在真實環境中，每個頁利用率並沒有這麼高，還會存在一些碎片的情況，我們假設每個頁的使用率為60%。十億級別的數據量查詢也只需要4次IO。

三、優化 B+ 樹索引的插入性能

1、索引維護原理

為了維持索引的順序，在插入、刪除時需要維護B+樹。

如果是插入，一般有三種情況：

1、只需要在頁記錄之後插入一條新記錄。

2、需要按邏輯移動以下數據以騰出空間

3、需要申請一個新的數據頁，然後將一些數據移到過去（分頁）在這種情況下，性能自然會受到影響。

除性能外，頁拆分還影響數據頁的利用率。原來放在一個頁上的數據現在被分成兩個頁，總體空間利用率降低了約50%。當然，有分裂的地方就有合併。

當由於刪除數據而導致兩個相鄰頁的使用率較低時，數據頁將被合併。合併過程可視為拆分過程的反向過程。

2、每張表儘量使用自增ID主鍵

自增加主鍵的數據插入模式，每次插入新記錄時，都是追加操作，它不涉及移動其他記錄，也不觸發葉節點的拆分，這樣，可以避免最後兩種影響性能的情況。

要確保以業務邏輯為主鍵的欄位的有序插入並不容易，因此寫入數據的成本相對較高。如果將業務邏輯的欄位用作主鍵，通常不容易確保有序插入，因此寫入數據的成本相對較高。

主鍵長度越小，索引的葉節點就越小，而索引占用的空間就越小。因此，從性能和存儲空間的角度來看，自動增長的主鍵往往是一個更合理的選擇。

四、B+樹 覆蓋索引與回表

回到主鍵索引樹搜索過程，稱為回表，查詢結果所需的數據僅在主鍵索引上可用，必須將其返回到表中獲取數據。

如果要執行的語句 select ID from T where，只需要查詢ID值，並且ID值已經在k索引樹上的話。可以直接提供查詢結果而不返回表，這個查詢,索引覆蓋了我們的查詢需求，我們稱之為覆蓋索引。

由於覆蓋索引可以減少樹搜索的數量並顯著提高查詢性能，因此使用覆蓋索引是一種常見的性能優化方法。

如果現在有高頻請求，可以在這個高頻請求上使用覆蓋率索引，無需返回表檢查整行記錄，並減少語句執行時間。當然，索引欄位的維護總是有代價的。因此，在建立冗餘索引以支持覆蓋率索引時，有必要考慮權衡。

總結

本篇文章博主對索引做了一個較為初步地概述，主要有2種主要的索引的數據結構b+tree和hash的數據結構，b+樹的覆蓋索引和回表進行分析，並對b+樹存放記錄、如何優化B+樹索引的插入性能進行分析。

作者：小明Java問道之路
連結：https://juejin.cn/post/7162916666253246478
來源：稀土掘金