本篇文章主要學習了MySQL的索引的數(shù)據(jù)結(jié)構(gòu)的認識，做一個大概的了解即可。

一、索引

在關(guān)系數(shù)據(jù)庫中，索引是一種單獨的、物理的對數(shù)據(jù)庫表中一列或多列的值進行排序的一種存儲數(shù)據(jù)結(jié)構(gòu)，它是某個表中一列或若干列值的集合和相應(yīng)的指向表中物理標識這些值的數(shù)據(jù)頁的邏輯指針清單。索引的作用相當于圖書的目錄，可以根據(jù)目錄中的頁碼快速查找到所需的內(nèi)容。

在MySQL中，存儲引擎用類似的方法使用索引，先在索引中找到對應(yīng)值，然后根據(jù)匹配的索引記錄找到對應(yīng)的行。

首先說明下MySQL的索引主要是基于Hash表或者B 樹。

二、索引數(shù)據(jù)結(jié)構(gòu)

了解索引就需要從索引常見的數(shù)據(jù)結(jié)構(gòu)開始了解學習，這里有集中常見的的索引數(shù)據(jù)結(jié)構(gòu)。

二叉樹（Binary Trees）

二叉樹是每個節(jié)點最多只有兩個分支（即不存在分支度大于2的節(jié)點）的樹結(jié)構(gòu)。通常被稱之為“左子樹”和“右子樹”

左子樹<父節(jié)點<=右子樹

二叉樹的第i層至多有有2^(i-1)個節(jié)點，

深度為K的二叉樹至多總共有個2^k-1節(jié)點（定義根節(jié)點所在深度 k0=0），而總計擁有節(jié)點數(shù)符合的，稱為“滿二叉樹”；

二叉樹通常作為數(shù)據(jù)結(jié)構(gòu)應(yīng)用，典型用法是對節(jié)點定義一個標記函數(shù)，將一些值與每個節(jié)點相關(guān)系。這樣標記的二叉樹就可以實現(xiàn)二叉搜索樹和二叉堆，并應(yīng)用于高效率的搜索和排序。

同時學習數(shù)據(jù)結(jié)構(gòu)，這里還推薦Data Structure Visualizations進行學習，可以非常直觀的看到數(shù)據(jù)結(jié)構(gòu)允許的過程，一步一步的怎么走的都可以很清晰看得到。

找到其中的Binary Search Trees二叉樹

可以直觀的看到二叉樹的數(shù)據(jù)插入過程，如下：

可以看到二叉樹不適合用作當作索引的，數(shù)據(jù)量龐大的話，二叉樹的層數(shù)會很大，查找效率固然也很慢了。

紅黑樹（Red-Black Trees）

是一種自平衡二叉查找樹，典型用途是實現(xiàn)關(guān)聯(lián)數(shù)組。

紅黑樹的結(jié)構(gòu)復雜，但它的操作有著良好的最壞情況運行時間，并且在實踐中高效：它可以在O(log n)時間內(nèi)完成查找，插入和刪除，這里的n是樹中元素的數(shù)目。

紅黑樹遵行以下原則：

1. 節(jié)點是紅色或黑色。
2. 根是黑色。
3. 所有葉子都是黑色（葉子是NIL節(jié)點）。
4. 每個紅色節(jié)點必須有兩個黑色的子節(jié)點。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點。）
5. 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點。

下面是一個具體的紅黑樹的圖例：

這些約束確保了紅黑樹的關(guān)鍵特性：從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。

要知道為什么這些性質(zhì)確保了這個結(jié)果，注意到性質(zhì)4導致了路徑不能有兩個毗連的紅色節(jié)點就足夠了。最短的可能路徑都是黑色節(jié)點，最長的可能路徑有交替的紅色和黑色節(jié)點。因為根據(jù)性質(zhì)5所有最長的路徑都有相同數(shù)目的黑色節(jié)點，這就表明了沒有路徑能多于任何其他路徑的兩倍長。

同樣在Data Structure Visualizations中選擇Red-Black Trees紅黑樹進行插入操作可以直觀的看到紅黑樹的插入過程

同樣紅黑樹也不適用于MySQL的索引，數(shù)據(jù)量龐大之后，數(shù)層也會變大。

其他結(jié)構(gòu)的問題

由于無法裝入內(nèi)存，則必然依賴磁盤（或SSD）存儲。而內(nèi)存的讀寫速度是磁盤的成千上萬倍（與具體實現(xiàn)有關(guān)），因此，核心問題是“如何減少磁盤讀寫次數(shù)”。

首先不考慮頁表機制，假設(shè)每次讀、寫都直接穿透到磁盤，那么：

• 線性結(jié)構(gòu)：讀/寫平均O(n)次
• 二叉搜索樹（BST）：讀/寫平均O(log2(n))次；如果樹不平衡，則最差讀/寫O(n)次
• 自平衡二叉搜索樹（AVL）：在BST的基礎(chǔ)上加入了自平衡算法，讀/寫最大O(log2(n))次
• 紅黑樹（RBT）：另一種自平衡的查找樹，讀/寫最大O(log2(n))次

BST、AVL、RBT很好的將讀寫次數(shù)從O(n)優(yōu)化到O(log2(n))；其中，AVL和RBT都比BST多了自平衡的功能，將讀寫次數(shù)降到最大O(log2(n))。

假設(shè)使用自增主鍵，則主鍵本身是有序的，樹結(jié)構(gòu)的讀寫次數(shù)能夠優(yōu)化到樹高，樹高越低讀寫次數(shù)越少；自平衡保證了樹結(jié)構(gòu)的穩(wěn)定。如果想進一步優(yōu)化，可以引入B樹和B 樹。

B樹（B-Trees）

又稱：多路平衡查找樹。大多數(shù)存儲引擎都支持B樹索引。b樹通常意味著所有的值都是按順序存儲的，并且每一個葉子節(jié)點到根的距離相同。B樹索引能夠加快訪問數(shù)據(jù)的速度，因為存儲引擎不再需要進行全表掃描來獲取數(shù)據(jù)。下圖就是一顆簡單的B樹。

在B樹中，內(nèi)部（非葉子）節(jié)點可以擁有可變數(shù)量的子節(jié)點（數(shù)量范圍預(yù)先定義好）。當數(shù)據(jù)被插入或從一個節(jié)點中移除，它的子節(jié)點數(shù)量發(fā)生變化。為了維持在預(yù)先設(shè)定的數(shù)量范圍內(nèi)，內(nèi)部節(jié)點可能會被合并或者分離。

如下圖所示：

• 葉節(jié)點具有相同的深度，葉節(jié)點的指針為空
• 所有索引元素不重復
• 節(jié)點中的數(shù)據(jù)索引從左到右遞增排列
• 無論中間節(jié)點還是葉子節(jié)點都帶有衛(wèi)星數(shù)據(jù)data（索引元素所指向的數(shù)據(jù)記錄）

只演示了插入的過程，其中可以通過delete、find執(zhí)行刪除和查找操作。直觀的感受到B樹的執(zhí)行過程。

每個節(jié)點存儲了多個Key和子樹，子樹與Key按順序排列。

同二叉搜索樹類似，每個節(jié)點存儲了多個key和子樹，子樹與key按順序排列。

頁表的目錄是擴展外存 加速磁盤讀寫，一個頁（Page）通常4K（等于磁盤數(shù)據(jù)塊block的大小，見inode與block的分析），操作系統(tǒng)每次以頁為單位將內(nèi)容從磁盤加載到內(nèi)存（以攤分尋道成本），修改頁后，再擇期將該頁寫回磁盤?？紤]到頁表的良好性質(zhì)，可以使每個節(jié)點的大小約等于一個頁（使m非常大），這每次加載的一個頁就能完整覆蓋一個節(jié)點，以便選擇下一層子樹；對子樹同理。對于頁表來說，AVL（或RBT）相當于1個key 2個子樹的B樹，由于邏輯上相鄰的節(jié)點，物理上通常不相鄰，因此，讀入一個4k頁，頁面內(nèi)絕大部分空間都將是無效數(shù)據(jù)。

假設(shè)key、子樹節(jié)點指針均占用4B，則B樹節(jié)點最大m * (4 4) = 8m B；頁面大小4KB。則m = 4 * 1024 / 8m = 512，一個512叉的B樹，1000w的數(shù)據(jù)，深度最大 log(512/2)(10^7) = 3.02 ~= 4。對比二叉樹如AVL的深度為log(2)(10^7) = 23.25 ~= 24，相差了5倍以上。震驚！B樹索引深度竟然如此！

那為什么B數(shù)這么厲害了，還有B 樹的出現(xiàn)呢，必然是解決B樹存在的問題

1、為定位行數(shù)

2、無法處理范圍查詢

問題1：為定位行數(shù)

數(shù)據(jù)表的記錄有多個字段，僅僅定位到主鍵是不夠的，還需要定位到數(shù)據(jù)行。有3個方案解決：

1. 直接將key對應(yīng)的數(shù)據(jù)行（可能對應(yīng)多行）存儲子節(jié)點中。
2. 數(shù)據(jù)行單獨存儲；節(jié)點中增加一個字段，定位key對應(yīng)數(shù)據(jù)行的位置。
3. 修改key與子樹的判斷邏輯，使子樹大于等于上一key小于下一key，最終所有訪問都將落于葉子節(jié)點；葉子節(jié)點中直接存儲數(shù)據(jù)行或數(shù)據(jù)行的位置。

方案1直接pass，存儲數(shù)據(jù)行將減少頁面中的子樹個數(shù)，m減小樹高增大。

方案2的節(jié)點中增加了一個字段，假設(shè)是4B的指針，則新的m = 4 * 1024 / 12m = 341.33 ~= 341，深度最大 log(341/2)(10^7) = 3.14 ~= 4。

方案3的節(jié)點m與深度不變，但時間復雜度變?yōu)榉€(wěn)定的O(logm(n))。

方案3可以考慮。

問題2：無法處理范圍查詢

實際業(yè)務(wù)中，范圍查詢的頻率非常高，B樹只能定位到一個索引位置（可能對應(yīng)多行），很難處理范圍查詢。改動較小的是2個方案：

1. 不改動；查詢的時候先查到左界，再查到右界，然后DFS（或BFS）遍歷左界、右界之間的節(jié)點。
2. 在“問題1-方案3”的基礎(chǔ)上，由于所有數(shù)據(jù)行都存儲在葉子節(jié)點，B樹的葉子節(jié)點本身也是有序的，可以增加一個指針，指向當前葉子節(jié)點按主鍵順序的下一葉子節(jié)點；查詢時先查到左界，再查到右界，然后從左界到有界線性遍歷。

乍一看感覺方案1比方案2好——時間復雜度和常數(shù)項都一樣，方案1還不需要改動。但是別忘了局部性原理，不管節(jié)點中存儲的是數(shù)據(jù)行還是數(shù)據(jù)行位置，方案2的好處在于，依然可以利用頁表和緩存預(yù)讀下一節(jié)點的信息。而方案1則面臨節(jié)點邏輯相鄰、物理分離的缺點。

B 樹（B Trees）

主要變動如上所述：

• 修改key與子樹的組織邏輯，將索引訪問都落到葉子節(jié)點
• 按順序?qū)⑷~子節(jié)點串起來（方便范圍查詢）

回顧上一個B樹，一個m階的B樹具有如下幾個特征：

1.根結(jié)點至少有兩個子女。

2.每個中間節(jié)點都包含k-1個元素和k個孩子，其中 m/2 <= k <= m

3.每一個葉子節(jié)點都包含k-1個元素，其中 m/2 <= k <= m

4.所有的葉子結(jié)點都位于同一層。

5.每個節(jié)點中的元素從小到大排列，節(jié)點當中k-1個元素正好是k個孩子包含的元素的值域分劃。

一個m階的B 樹具有如下幾個特征：

1.有k個子樹的中間節(jié)點包含有k個元素（B樹中是k-1個元素），每個元素不保存數(shù)據(jù)，只用來索引，所有數(shù)據(jù)都保存在葉子節(jié)點。

2.所有的葉子結(jié)點包含了全部元素的信息，及指向含這些元素記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接。

3.所有的中間節(jié)點元素都同時存在于子節(jié)點，在子節(jié)點元素中是最大（或最?。┰?。

B 樹特性總結(jié)

B 樹是B樹的升級版，其有如下特性

• 非葉子節(jié)點不存儲data，只存儲索引(冗余)，可以放更多的索引
• 葉子節(jié)點包含所有索引字段
• 葉子節(jié)點用指針連接，提高區(qū)間訪問的性能
• 只有葉子節(jié)點帶有衛(wèi)星數(shù)據(jù)data（索引元素所指向的數(shù)據(jù)記錄）

同樣在Data Structure Visualizations中選擇B TreesB 樹進行插入操作可以直觀的看到插入過程

在動圖中可以看出，B 樹的每一個葉子節(jié)點都有一個指針指向下一個節(jié)點，把所有的葉子節(jié)點串在一起。索引數(shù)據(jù)都存儲在葉子節(jié)點中。

B 樹相比于B樹，有什么優(yōu)勢呢：

1.單一節(jié)點存儲更多的元素，使得查詢的IO次數(shù)更少。

2.所有查詢都要查找到葉子節(jié)點，查詢性能穩(wěn)定。

3.所有葉子節(jié)點形成有序鏈表，便于范圍查詢。

總結(jié)，B 樹相比B樹的優(yōu)勢有三：1.IO次數(shù)更少；2.查詢性能穩(wěn)定；3.范圍查詢簡便。

Hash索引

hash索引基于hash表實現(xiàn)，Hash 索引是將索引鍵通過 Hash 運算之后，將 Hash運算結(jié)果的 Hash 值和所對應(yīng)的行指針信息存放于一個 Hash 表中。只有精準匹配索引所有列的查詢才有效。索引的檢索可以一次定位，不像B-Tree索引需要從根節(jié)點出發(fā)到目標節(jié)點。雖然Hash索引很快，遠高于B-tree索引，但是也有其弊端。

1. Hash索引僅僅能滿足'=','IN','<=>'查詢，也就是等值查詢，不能使用范圍查詢。很受限
2. 由于 Hash 索引比較的是進行 Hash 運算之后的 Hash 值，所以它只能用于等值的過濾，不能用于基于范圍的過濾，因為經(jīng)過相應(yīng)的 Hash 算法處理之后的 Hash 值的大小關(guān)系，并不能保證和Hash運算前完全一樣。
3. 由于Hash索引是通過hash表實現(xiàn)，其本身是沒有排序的。
4. 由于 Hash 索引中存放的是經(jīng)過 Hash 計算之后的 Hash 值，而且Hash值的大小關(guān)系并不一定和 Hash 運算前的鍵值完全一樣，所以數(shù)據(jù)庫無法利用索引的數(shù)據(jù)來避免任何排序運算；
5. Hash索引不能利用部分索引鍵查詢
6. 對于組合索引，Hash索引在計算hash值的時候是組合索引鍵合并后再一起計算hash值，而不是單獨計算hash值，所以通過組合索引的前面一個或幾個索引鍵進行查詢的時候，Hash 索引也無法被利用。
7. Hash 索引在任何時候都不能避免表掃描
8. 前面已經(jīng)知道，Hash 索引是將索引鍵通過 Hash 運算之后，將 Hash運算結(jié)果的 Hash 值和所對應(yīng)的行指針信息存放于一個 Hash 表中，由于不同索引鍵存在相同 Hash 值，所以即使取滿足某個 Hash 鍵值的數(shù)據(jù)的記錄條數(shù)，也無法從 Hash 索引中直接完成查詢，還是要通過訪問表中的實際數(shù)據(jù)進行相應(yīng)的比較，并得到相應(yīng)的結(jié)果。
9. Hash 索引遇到大量Hash值相等的情況后性能并不一定就會比B-Tree索引高。
10. 對于選擇性比較低的索引鍵，如果創(chuàng)建 Hash 索引，那么將會存在大量記錄指針信息存于同一個 Hash 值相關(guān)聯(lián)。這樣要定位某一條記錄時就會非常麻煩，會浪費多次表數(shù)據(jù)的訪問，而造成整體性能低下。

三、MySQL數(shù)據(jù)庫引擎

通過navicat工具查看表設(shè)計選項中，從引擎中可以看到MySQL又這么多引擎。具體細分到每個表，不同的表引擎可以不一樣。

MyISAM

新建一張表t_test_myisam，引擎使用MyISAM，查看原文件可以看到有3個文件

可以看到索引和數(shù)據(jù)是分開的，其中索引文件僅僅保存數(shù)據(jù)記錄的地址，故屬于非聚簇索引。

主鍵索引（Primary Index）

MyISAM引擎使用B Tree作為索引結(jié)構(gòu)，葉節(jié)點的data存放的是數(shù)據(jù)記錄的地址。如下圖是MyISAM主鍵索引的原理圖。

其中Col1為主鍵，可以看出看出MyISAM的索引文件僅保存數(shù)據(jù)記錄的地址。

輔助索引（Secondary Index）

在Col2上建立一個輔助索引，如下圖輔助索引原理圖。

可以看到與主鍵索引沒有任何區(qū)別，只不過主鍵索引的key是唯一的，而輔助索引的key可以重復。

MyISAM中索引檢索的算法為首先按照B Tree搜索算法搜索索引，如果指定的Key存在，則取出其data域的值，然后以data域的值為地址，讀取相應(yīng)數(shù)據(jù)記錄。

InnoDB

新建一張表t_test_innodb，引擎使用InnoDB，查看原文件可以看到有2個文件

主鍵索引（Primary Index）

InnoDB的索引和數(shù)據(jù)在一個文件當中。

按照B Tree組織的一個索引結(jié)構(gòu)。

葉節(jié)點保存了完整的數(shù)據(jù)記錄和索引。這種索引就叫做聚簇索引。

索引的Key是數(shù)據(jù)的主鍵，因此InnoDB表數(shù)據(jù)文件本身就是主索引。

如下圖：

可以看到葉節(jié)點包含了完整的數(shù)據(jù)記錄。

因為InnoDB的數(shù)據(jù)文件本身要按照主鍵聚集，所以InnoDB要求必須有主鍵。如果沒有顯式指定，則MySQL系統(tǒng)會自動選擇一個可以唯一標識數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隱含字段rowid作為主鍵，這個字段長度為6個字節(jié)，類型為長整形。

輔助索引（Secondary Index）

輔助索引，將途中的第二行name，作為索引如圖

聚簇索引這種實現(xiàn)方式使得按照主鍵的搜索十分高效，但是首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄。

由于InnoDB索引的實現(xiàn)特性，推薦使用整形的自增主鍵。

有三點好處：

1. 自增key一般為int等整數(shù)型，key比較緊湊，這樣m可以非常大，而且索引占用空間小。最極端的例子，如果使用50B的varchar（包括長度），那么m = 4 * 1024 / 54m = 75.85 ~= 76，深度最大log(76/2)(10^7) = 4.43 ~= 5，再加上cache缺失、字符串比較的成本，時間成本增加較大。同時，key由4B增長到50B，整棵索引樹的空間占用增長也是極為恐怖的（如果二級索引使用主鍵定位數(shù)據(jù)行，則空間增長更加嚴重）。
2. MySQL索引底層的數(shù)據(jù)比較都是整數(shù)型比較，如果主鍵時字符串類型的，里面還有英文，還得轉(zhuǎn)換ASCII碼進行比較。所以不建議使用uuid作為主鍵。
3. 自增的主鍵使得數(shù)據(jù)行的插入比如落到索引數(shù)的最右側(cè)，發(fā)生節(jié)點分裂的頻率較低。B Tree實際操作插入過程。如果不是非單調(diào)主鍵，插入過程很大程度會發(fā)生節(jié)點重排，不利于索引優(yōu)化的初衷。

InnoDB索引和MyISAM索引的區(qū)別

一是主索引的區(qū)別：InnoDB的數(shù)據(jù)文件本身就是索引文件。而MyISAM的索引和數(shù)據(jù)是分開的。

二是輔助索引的區(qū)別：InnoDB的輔助索引data域存儲相應(yīng)記錄主鍵的值而不是地址。而MyISAM的輔助索引和主索引沒有多大區(qū)別。

四、覆蓋索引

InnoDB存儲引擎支持覆蓋索引，即從輔助索引中就可以得到查詢的記錄，不需要查詢聚簇索引中的記錄了?？梢詼p少大量的IO操作。

如果要查詢輔助索引中不含有的字段，得先遍歷輔助索引，再遍歷聚集索引，而如果要查詢的字段值在輔助索引上就有，就不用再查聚集索引了，這顯然會減少IO操作。

五、聯(lián)合索引

兩個或以上的列上的索引。如下圖聯(lián)合索引的原理圖：

上圖中的聯(lián)合索引有三個，從上到下，嚴格按照排序。

六、優(yōu)化建議

最左前綴匹配

索引可以簡單如一個列(a)，也可以復雜如多個列(a, b, c, d)，即聯(lián)合索引。如果是聯(lián)合索引，那么key也由多個列組成，同時，索引只能用于查找key是否存在（相等），遇到范圍查詢(>、<、between、like左匹配)等就不能進一步匹配了，后續(xù)退化為線性查找。因此，列的排列順序決定了可命中索引的列數(shù)。

如有索引(a, b, c, d)，查詢條件a = 1 and b = 2 and c > 3 and d = 4，則會在每個節(jié)點依次命中a、b、c，無法命中d。也就是最左前綴匹配原則。

=、in自動優(yōu)化順序

不需要考慮=、in等的順序，mysql會自動優(yōu)化這些條件的順序，以匹配盡可能多的索引列。

如有索引(a, b, c, d)，查詢條件c > 3 and b = 2 and a = 1 and d < 4與a = 1 and c > 3 and b = 2 and d < 4等順序都是可以的，MySQL會自動優(yōu)化為a = 1 and b = 2 and c > 3 and d < 4，依次命中a、b、c。

索引列不能參與計算

有索引列參與計算的查詢條件對索引不友好（甚至無法使用索引），如from_unixtime(create_time) = '2014-05-29'。

原因很簡單，如何在節(jié)點中查找到對應(yīng)key？如果線性掃描，則每次都需要重新計算，成本太高；如果二分查找，則需要針對from_unixtime方法確定大小關(guān)系。

因此，索引列不能參與計算。上述from_unixtime(create_time) = '2014-05-29'語句應(yīng)該寫成create_time = unix_timestamp('2014-05-29')。

能擴展就不要新建索引

如果已有索引(a)，想建立索引(a, b)，盡量選擇修改索引(a)為索引(a, b)。

新建索引的成本很容易理解。而基于索引(a)修改為索引(a, b)的話，MySQL可以直接在索引a的B 樹上，經(jīng)過分裂、合并等修改為索引(a, b)。

不需要建立前綴有包含關(guān)系的索引

如果已有索引(a, b)，則不需要再建立索引(a)，但是如果有必要，則仍然需考慮建立索引(b)。