為什么需要索引？
一句話概括：索引的出現其實就是為了提高數據查詢的效率。

一、索引常見模型

模型： 哈希表、有序數組和搜索樹

哈希表

• 哈希表是一種以鍵 - 值（key-value）存儲數據的結構，我們只要輸入待查找的鍵即 key，就可以找到其對應的值即 Value。哈希的思路很簡單，把值放在數組里，用一個哈希函數把 key 換算成一個確定的位置，然后把 value 放在數組的這個位置。
  時間復雜度：0(1)
• 畫重點：如果索引的值有重復的話，會發生hash碰撞，雖然可以解決hash沖突，但是導致查詢效率降低。
• 場景： 哈希表這種結構適用于只有等值查詢的場景，不適用于查找范圍的。類似 redis Memcached 及其他一些 NoSQL 引擎。

搜索樹

在了解搜索樹之前我們需要先知道 二叉樹、平衡二叉樹、B樹、B+樹

推薦一個工具可以清晰的理解樹的原理： https://www.cs.usfca.edu/~gal...

二叉樹

二叉樹特性： 左子樹的鍵值小于根的鍵值，右子樹的鍵值大于根的鍵值。

如下圖就是一個二叉樹

當前二叉樹的插入順序是： 3 2 4 1 5

如果我們按1 2 3 4 5 的順序來插入的化， 我們得到的二叉樹就是如下圖所示

如果是這種二叉樹查詢效率就太低了。若想二叉樹的查詢效率盡可能高，需要二叉樹是平衡的從而引出新的定義 - 平衡二叉樹或稱AVL樹。

平衡二叉樹

平衡二叉樹特點：

• 滿足二叉樹的特性
• 任何節點的兩個子樹的高度最大差為1

如上兩個組合之后就是平衡二叉樹，如下圖

中插入樹的順序為：1 2 3 4 5 6 7 8 時候生成的是如圖所示的內容，和圖二完成不一樣， 在通過工具生成這個圖的時候明顯可以看到不管如何插入節點數據都能滿足平衡二叉樹的特點2。

當刪除一個節點之后同樣能滿足avl樹，如下圖刪除圖3中的5節點之后展示如下。

總結一下 平衡二叉樹的優點

• a 不錯的查找性能（O（logn）), 不存在極端的低效查找的情況。
• b 可以實現范圍查找、數據排序。

看起來 AVL 樹作為數據查找的數據結構確實很不錯，但是 AVL 樹并不適合做 MySQL 數據庫的索引數據結構，因為考慮一下這個問題：

數據庫查詢數據的瓶頸在于磁盤 IO，如果使用的是 AVL 樹，我們每一個樹節點只存儲了一個數據，我們一次磁盤 IO 只能取出來一個節點上的數據加載到內存里，那比如查詢 id=8 這個數據我們就要進行磁盤 IO 三次，這是多么消耗時間的。所以我們設計數據庫索引時需要首先考慮怎么盡可能減少磁盤 IO 的次數。

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

B-樹

B樹的特點：

• 所有健值分布在整棵樹中
• 搜索有可能在非葉子節點結束
• 根節點至少有2個子樹
• 所有葉子節點都在同一層
• 分叉數（路數）永遠比關鍵字數多 1
• 節點存儲key和value

演示 B樹索引分裂合并

比如 Max Degree（路數）是 3 的時候，我們插入數據 1、2、3，在插入 3 的時候， 本來應該在第一個磁盤塊，但是如果一個節點有三個關鍵字的時候，意味著有 4 個指針， 子節點會變成 4 路，所以這個時候必須進行分裂。把中間的數據 2 提上去，把 1 和 3 變 成 2 的子節點。

如果刪除節點，會有相反的合并的操作。 注意這里是分裂和合并，跟 AVL 樹的左旋和右旋是不一樣的。 我們繼續插入 4 和 5，B Tree 又會出現分裂和合并的操作。

從這個里面我們也能看到，在更新索引的時候會有大量的索引的結構的調整，節點的分裂和合并，其實就是 InnoDB 頁的分裂和合并。

B+樹

B+樹是在B樹上做的一個優化工作

• B+樹每個節點可以包含更多的節點內容，為什么這么做呢？第一：降低樹的高度 第二：將數據范圍變為多個區間，區間越多 檢索速度就越快
• 非葉子節點存的是key, 葉子節點存的是key和數據
• 葉子節點指針相連，順序查找速度更快

B 樹和 B+樹有什么不同呢？

第一，B 樹一個節點里存的是key和數據，而 B+樹存儲的是索引（地址），所以 B 樹里一個節點存不了很多個數據，但是 B+樹一個節點能存很多索引，B+樹葉子節點存所有的數據。

第二，B+樹的葉子節點是數據階段用了一個鏈表串聯起來，便于范圍查找。

通過 B 樹和 B+樹的對比我們看出，B+樹節點存儲的是索引，在單個節點存儲容量有限的情況下，單節點也能存儲大量索引，使得整個 B+樹高度降低，減少了磁盤 IO。其次，B+樹的葉子節點是真正數據存儲的地方，葉子節點用了鏈表連接起來，這個鏈表本身就是有序的，在數據范圍查找時，更具備效率。因此 Mysql 的索引用的就是 B+樹，B+樹在查找效率、范圍查找中都有著非常不錯的性能。

綜上所述mysql innodb 索引選擇了B+樹。

思考問題

1、B+樹葉子節點存的詩所有數據，如果1000萬數據，那這個鏈表太大 ，不會影響性能嗎？

可以利用數據頁，下面有重點分析

2、InnoDB一棵B+樹可以存放多少行數據？

B+Tree 的根節點和枝節點中都不會存儲數據，只有葉子節點才存儲數據。搜索 到關鍵字不會直接返回，會到最后一層的葉子節點。比如我們搜索 id=3，雖然在第一 層直接命中了，但是全部的數據在葉子節點上面，所以我還要繼續往下搜索，一直到葉 子節點。
舉個例子：假設一條記錄是 1K，一個葉子節點（一頁）可以存儲 16 條記錄。非葉 子節點可以存儲多少個指針？
假設索引字段是 bigint 類型，長度為 8 字節。指針大小在 InnoDB 源碼中設置為 6 字節，這樣一共 14 字節。非葉子節點（一頁）可以存儲 1024*16 / 14 = 1170 個這樣的 單元（鍵值+指針），代表有 1170 個指針。
樹深度為 2 的時候， 有 1170^2 個葉子節點 ，可以存儲的數據為：
1170 * 1170 * 16 = 21902400 2000萬
在查找數據時一次頁的查找代表一次 IO，也就是說，一張 2000 萬左右的表，查詢數據最多需要訪問 3 次磁盤。 所以在 InnoDB 中 B+ 樹深度一般為 1-3 層，它就能滿足千萬級的數據存儲。

二、innodb的索引分析

在 InnoDB 中，表都是根據主鍵順序以索引的形式存放的，這種存儲方式的表稱為索引組織表。

上述中我們從不同維度分析了最終InnoDB 使用了 B+ 樹索引模型，所以數據都是存儲在 B+ 樹中的。

每一個索引在 InnoDB 里面對應一棵 B+ 樹。假設，我們有一個主鍵列為 ID 的表，表中有字段 k，并且在 k 上有普通索引。

這個表的建表語句是：

create table user(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;

表中 第一行到第五行 的 (ID,k) 值分別為 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，兩棵樹的示例示意圖如下。

上圖為：主健索引

上圖為：普通索引

根據上面的索引結構說明，我們來討論一個問題：基于主鍵索引和普通索引的查詢有什么區別？

如果語句是 select * from T where ID=500，即主鍵查詢方式，則只需要搜索 ID 這棵 B+ 樹；

如果語句是 select * from T where k=5，即普通索引查詢方式，則需要先搜索 k 索引樹，得到 ID 的值為 500，再到 ID 索引樹搜索一次。這個過程稱為回表。也就是說，基于非主鍵索引的查詢需要多掃描一棵索引樹。因此，我們在應用中應該盡量使用主鍵查詢。

B+ 樹為了維護索引有序性，在插入新值的時候需要做必要的維護。以上面這個圖為例，如果插入新的行 ID 值為 700，則只需要在 R5 的記錄后面插入一個新記錄。如圖

如果新插入的 ID 值為 400，就相對麻煩了，需要邏輯上挪動后面的數據，空出位置，如圖。

而更糟的情況是，如果 R5 所在的數據頁已經滿了，根據 B+ 樹的算法，這時候需要申請一個新的數據頁，然后挪動部分數據過去。這個過程稱為頁分裂。在這種情況下，性能自然會受影響。

除了性能外，頁分裂操作還影響數據頁的利用率。原本放在一個頁的數據，現在分到兩個頁中，整體空間利用率降低大約 50%。當然有分裂就有合并。

當相鄰兩個頁由于刪除了數據，利用率很低之后，會將數據頁做合并。合并的過程，可以認為是分裂過程的逆過程。

三、innodb 數據頁

在上述中我們提到數據頁，數據頁的概念，它是MySQL管理存儲空間的基本單位，一個頁的大小一般是16KB，并且我們知道了記錄其實是被存放在頁中的，如果記錄占用的空間太大還可能造成行溢出現象，這會導致一條記錄被分散存儲在多個頁中。

頁的本質就是一塊16KB大小的存儲空間，InnoDB為了不同的目的而把頁分為不同的類型，其中用于存放記錄的頁也稱為數據頁，我們先看看這個用于存放記錄的頁長什么樣。數據頁代表的這塊16KB大小的存儲空間可以被劃分為多個部分，不同部分有不同的功能，各個部分如圖所示：

從圖中可以看出，一個InnoDB數據頁的存儲空間被劃分成了7個部分，每個部分又可以被劃分為若干小部分。

下面用數據頁來分析innodb索引數據.

我們已主鍵索引為例子，每一頁默認大小16k， 當我們第一頁用戶數據區域頁滿了的時候 就會進行申請新的頁也就是第二頁 然后有新的數據插入時候會在第二頁中存入我們的用戶數據比如如圖中的R4，涉及到這種數據的檢索頁內的數據是類似一個鏈表，頁與頁之間也是鏈表，當數據量大的時候其實性能比較差的，這個時候我們需要引入頁目錄的概念。

當有了頁目錄之后檢索性能會提升很多，但是如果頁很多的時候其實性能也會存在弊端，那這個時候需要如何處理呢，這個時候我們需要在上層在加入頁目錄的一個鏈表。

原文：
https://segmentfault.com/a/1190000040278249