本文導讀
本篇文章部落客對索引做了一個較為初步地概述，主要有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索引樹上的話。可以直接提供查詢結果而不傳回表，這個查詢,索引覆寫了我們的查詢需求，我們稱之為覆寫索引。
![D. Ehab the Xorcist(構造+思維)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)