表就是資料庫對不對嗎

作者 | Amazing10

責編 | 屠敏

頭圖 | CSDN 下載自視覺中國

本文為「業餘碼農」投稿

索引的概念基本所有人都會遇到過，就算沒有了解過資料庫中的索引，在生活中也不可避免的接觸到。比方說書籍的目錄，字典的查詢頁，圖書館的科目檢索等等。其實這些都是一種索引，並且所起到的作用大同小異。

而對於資料庫而言，只不過是將索引的概念抽象出來，讓建立索引的過程更為靈活而自由，從而可以在不同的場景下最佳化資料庫的查詢效率。

索引在資料庫的實際應用場景中十分普遍，資料庫的最佳化也離不開對索引的最佳化。同時，索引相關的知識也是面試高頻的考點之一，是應試者理論結合現實最為直接的體現。

因此，本文將從基礎理論出發，介紹 MySQL 按照邏輯角度的索引分類和實現，透過資料結構的實現原理闡述不同結構對建立索引帶來的優劣勢，同時針對物理儲存的方式對索引的組織特點和應用場景進行分析。最後根據不同的應用場景儘可能的探究如何建立起高效能的索引。文章結構如下：

概念

什麼是索引？

索引似乎並沒有十分明確的定義，更多的是一種定性的描述。簡單來講，索引就是一種將資料庫中的記錄按照特殊形式儲存的資料結構。透過索引，能夠顯著地提高資料查詢的效率，從而提升伺服器的效能。

專業一點來說呢，索引是一個排好序的列表，在這個列表中儲存著索引的值和包含這個值的資料所在行的物理地址。在資料庫十分龐大的時候，索引可以大大加快查詢的速度，

這是因為使用索引後可以不用掃描全表來定位某行的資料，而是先透過索引表找到該行資料對應的物理地址然後訪問相應的資料。

說起索引，其實並不是 MySQL 資料庫特有的機制，在關係型資料庫中都會有類似不同的實現。這裡我們也只是討論 MySQL 資料庫中的索引實現。

事實上，說是 MySQL 的索引其實並不準確。因為在 MySQL 中，索引是在儲存引擎層而不是伺服器層實現的。這意味著我們所討論的索引準確來說是 InnoDB 引擎或 MyISAM 引擎或其它儲存引擎所實現的。

所以索引即便是在 MySQL 中也沒有統一的標準，不同儲存引擎的所實現的索引工作方式也並不一樣。不是所有的儲存引擎都支援相同型別的索引，即便是多個引擎支援同一種類型的索引，其底層的實現也可能不同。

為什麼需要索引

說了這麼多，索引似乎就是給資料庫添加了一個「目錄頁」，能夠方便查詢資料。但是索引的作用就僅此而已了嗎，為什麼需要大費周章的建立並最佳化索引？

說個題外話，我其實查字典從來都不喜歡查目錄頁，無論是查中文還是英文。因為覺得那樣很慢，一個個找索引，效率很低。我習慣用的方式就是直接翻開字典，根據翻開的位置進行前後調整。比方說我想找「醬 JIANG」字，會先隨機翻到一頁，可能是「F」開頭，在「J」前面，就往後翻一點；如果隨機翻到「L」，那就往前翻一點。重複直至找到。

這大概就是類似於二分查詢的方式，看起來好像是擺脫了索引的束縛，並且也能夠獲得比較高的查詢效率。但是其實轉念一想，在計算機的執行處理中，「一個個找索引」這個過程其實非常快，不能跟我們手動比對偏旁部首的效率相提並論。同時，為什麼我可以直接翻開字典根據字母進行調整呢，這其實不就是因為我的腦子裡存在一個大概的「索引表」，知道每個字母大概對應於字典的哪一個位置。雖然是模糊的，但卻是真實存在的。（好不容易強行解釋了一波。。。）

如此一來，可以看出索引的一大好處是如其概念中所提及的，使用索引後可以不用掃描全表來定位某行的資料，而是先透過索引表找到該行資料對應的物理地址然後訪問相應的資料。這樣的方式自然減少了伺服器在響應時所需要對資料庫掃描的資料量。

不僅如此，在執行資料庫的範圍查詢時，若不使用索引，那麼MySQL會先掃描資料庫的所有行資料並從中篩選出目標範圍內的行記錄，將這些行記錄進行排序並生成一張臨時表，然後透過臨時表返回使用者查詢的目標行記錄。這個過程會涉及到臨時表的建立和行記錄的排序，當目標行記錄較多的時候，會大大影響範圍查詢的效率。

所以當新增索引時，由於索引本身具有的順序性，使得在進行範圍查詢時，所篩選出的行記錄已經排好序，從而避免了再次排序和需要建立臨時表的問題。

同時，由於索引底層實現的有序性，使得在進行資料查詢時，能夠避免在磁碟不同扇區的隨機定址。使用索引後能夠透過磁碟預讀使得在磁碟上對資料的訪問大致呈順序的定址。這本質上是依據區域性性原理所實現的。

區域性性原理：

當一個數據被用到時，其附近的資料也通常會馬上被使用。程式執行期間所需要的資料通常比較集中。由於磁碟順序讀取的效率很高（不需要尋道時間，只需很少的旋轉時間） ，因此對於具有區域性性的程式來說，磁碟預讀可以提高I/O效率。

磁碟預讀要求每次都會預讀的長度一般為頁的整數倍。而且資料庫系統將一個節點的大小設為等於一個頁，這樣每個節點只需要一次 I/O 就可以完全載入。這裡的頁是透過頁式的記憶體管理所實現的，概念在這裡簡單提一嘴。

分頁機制就是把記憶體地址空間分為若干個很小的固定大小的頁，每一頁的大小由記憶體決定。這樣做是為了從虛擬地址對映到物理地址，提高記憶體和磁碟的利用率。

所以呢，總結一下。索引的存在具有很大的優勢，主要表現為以下三點：

索引大大減少了伺服器需要掃描的資料量

索引可以幫助伺服器避免排序和臨時表

索引可以將隨機 I/O 變成順序 I/O

以上三點能夠大大提高資料庫查詢的效率，最佳化伺服器的效能。因此一般來說，為資料庫新增高效的索引對資料庫進行最佳化的重要工作之一。

不過，凡事都有兩面性。索引的存在能夠帶來效能的提升，自然在其它方面也會付出額外的代價。

索引本身以表的形式儲存，因此會佔用額外的儲存空間；

索引表的建立和維護需要時間成本，這個成本隨著資料量增大而增大；

構建索引會降低資料的修改操作（刪除，新增，修改）的效率，因為在修改資料表的同時還需要修改索引表；

所以對於非常小的表而言，使用索引的代價會大於直接進行全表掃描，這時候就並不一定非得使用索引了。沒辦法，成年人的世界總是這麼的趨利避害。

邏輯分類

從邏輯的角度來對索引進行劃分的話，可以分為單列索引、全文索引、組合索引和空間索引。其中單列索引又可分為主鍵索引、唯一索引和普通索引。這裡的邏輯可以理解為從 SQL 語句的角度，或者是從資料庫關係表的角度。下面就簡單介紹這些索引的作用和用法，以及在修改表的時候如何新增索引。

主鍵索引

即主索引，根據主鍵建立索引，不允許重複，不允許空值；

主鍵：資料庫表中一列或列組合（欄位）的值，可唯一標識表中的每一行。

加速查詢 + 列值唯一（不可以有）+ 表中只有一個

ALTER TABLE 'table_name' ADD PRIMARY KEY pk_index('col');

唯一索引

用來建立索引的列的值必須是唯一的，允許空值。唯一索引不允許表中任何兩行具有相同的索引值。比方說，在 employee 表中職員的姓 name 上建立了唯一索引，那麼就表示任何兩個員工都不能同姓。

加速查詢 + 列值唯一（可以有）

ALTER TABLE 'table_name' ADD UNIQUE index_name('col');

普通索引

用表中的普通列構建的索引，沒有任何限制。

僅加速查詢

ALTER TABLE 'table_name' ADD INDEX index_name('col');

全文索引

用大文字物件的列構建的索引

ALTER TABLE 'table_name' ADD FULLTEXT INDEX ft_index('col');

組合索引

用多個列組合構建的索引，這多個列中的值不允許有空值。

多列值組成一個索引，專門用於組合搜尋，其效率大於索引合併。

ALTER TABLE 'table_name' ADD INDEX index_name('col1','col2','col3');

在對多列組合建立索引時，會遵循「最左字首」原則。

最左字首原則：顧名思義，就是最左優先，上例中我們建立了 （col1， col2， col3） 多列索引，相當於建立了 （col1） 單列索引，（col1， col2） 組合索引以及 （col1， col2， col3） 組合索引。

所以當我們在建立多列索引時，要根據業務場景，將 where 子句中使用最頻繁的一列放在最左邊。

空間索引

對空間資料型別的欄位建立的索引，底層可透過 R 樹實現。只不過使用較少，瞭解即可。

實現原理

我們知道，索引的底層本身就是透過資料結構來進行實現的。那麼根據其底層的結構，常見的索引型別可分為雜湊索引，BTree 索引，B+Tree 索引等。這裡我們就主要來介紹這三種索引背後的實現機制。

雜湊索引

顧名思義，雜湊索引是透過雜湊表實現的。雜湊表的特點在之前的文章「九大資料結構」中已經詳細介紹過。透過雜湊表的鍵值之間的對應關係，能夠在查詢時精確匹配索引的所有列。雜湊索引將所有的根據索引列計算出來的雜湊碼儲存在索引中，同時將指向每個資料行的指標儲存在雜湊表中。

上圖是透過雜湊索引查詢行資料的示意圖，可以發現雜湊索引同樣會發生雜湊衝突，並且是透過鏈地址法解決衝突的。當傳送衝突時，還需要對連結串列進行遍歷對比，才能夠找到最終的結果。

在 MySQL 中，只有 Memory 儲存引擎顯式的支援雜湊索引，而innodb是隱式支援雜湊索引的。

這裡的隱式支援是指，innodb引擎有一個特殊的功能 “自適應雜湊索引”，當innodb注意到一些索引值被使用的非常頻繁時，且符合雜湊特點（如每次查詢的列都一樣），它會在記憶體中基於 B-Tree 索引之上再建立一個雜湊索引。這樣就讓 BTree 索引也具有雜湊索引的一些有點。這是一個完全自動的、內部的行為。

由於雜湊結構的特殊性，其用於非常高的檢索效率，透過雜湊函式的對映可以一步到位。但是同樣也是因為結構的特殊，導致雜湊索引只適用於某些特定的場合。雜湊索引的限制［1］：

不支援範圍查詢，比如 WHERE a > 5；只支援等值比較查詢，包括＝、IN 、<=>

無法被用來避免資料的排序操作；因為經過了雜湊函式的對映過程，使得丟失了雜湊前後的大小關係，從而無法按照索引值的順序儲存。

不支援部分索引列的匹配查詢，因為雜湊索引始終使用索引列的全部內容來計算雜湊值。例如在資料列 （A， B） 上建立雜湊索引，如果查詢只有資料列 A，則無法使用該索引。

無法避免表掃描。因為當出現雜湊衝突的時候，儲存引擎必須遍歷連結串列（拉鍊法）中所有的行指標，逐行進行比較，直到找到所有符合條件的行。

雜湊衝突很多的情況下，其索引維護的代價很高，並且效能並不一定會比 BTree 索引高。

BTree 索引

BTree 實際上是一顆多叉平衡搜尋樹。從名字可以看出，BTree 首先是一顆多叉搜尋樹，這意味著它是具有順序的；其次 BTree 還是平衡的，這意味著它的左右子樹高度差小於等於1。

事實上一顆 BTree 需要滿足以下幾個條件：

每個葉子結點的高度都是一樣的；

每個非葉子結點由 n-1 個 key 和 n 個指標 point 組成，其中 d<=n<=2d， key 和 point 相互間隔，結點兩端一定是 key；

葉子結點指標都為 ；

非葉子結點的key都是 ［key， data］ 二元組，其中 key 表示作為索引的鍵，data 為鍵值所在行的資料；

一顆常見的BTree樹見下圖。

這是一顆三階的BTree，可透過鍵值的大小排序進行資料的查詢和檢索，其中葉子節點的指標都為空，因此省略沒畫。從上圖可以發現，BTree 的樹形狀相較於我們之前常見的二叉樹等結構，更為扁平和矮胖。

之所以這樣設計，還是跟磁碟讀取的特點有關。我們知道在建立索引時，也是需要佔據物理空間的。而實際上當資料量比較大的時候，索引檔案的大小也十分嚇人。考慮到一個表上可能有多個索引、組合索引、資料行佔用更小等情況，索引檔案的大小可能達到物理盤中資料的1/10，甚至可達到1/3。

這就意味著索引無法全部裝入記憶體之中。當透過索引對資料進行訪問時，不可避免的需要對磁碟進行讀寫訪問。同時我們還知道，記憶體的讀寫速度是磁碟的幾個數量級。因此在對索引結構進行設計時要儘可能的減少對磁碟的讀寫次數，也就是所謂的磁碟 I/O 次數。

這也就是索引會採用 BTree 這種扁平樹結構的原因，樹的層數越少，磁碟I/O的次數自然就越少。不僅如此，我們上面提到過磁碟預讀的區域性性原理。根據這個原理再加上頁表機制，能夠在進行磁碟讀取的時候更大化的提升效能。

BTree 相較於其它的二叉樹結構，對磁碟的 I/O 次數已經非常少了。但是在實際的資料庫應用中仍有些問題無法解決。

一是無法定位到資料行。透過 BTree 可以根據主鍵的排序定位出主鍵的位置，但是由於資料表的記錄有多個欄位，僅僅定位到主鍵是不夠，還需要定位到資料行。雖然這個問題可以透過在 BTree 的節點中儲存資料行或者增加定位的欄位，但是這種方式會使得 BTree 的深度大幅度提高，從而也導致 I/O 次數的提高。

二是無法處理範圍查詢。在實際的應用中，資料庫範圍查詢的頻率非常高，而 BTree 只能定位到一個索引位置。雖然可以透過先後查詢範圍的左右界獲得，但是這樣的操作實際上無法很好的利用磁碟預讀的區域性性原理，先後查詢可能會造成透過預讀取的物理地址離散，使得 I/O 的效率並不高。

三是當資料量一大時，BTree的高度依舊會變得很高，搜尋效率還是會大幅度的下降。

問題總是推動改進的前提。基於以上的問題考慮，就出現了對 BTree 的最佳化版本，也就是 B+Tree。

B+Tree索引

B+Tree 一看就是在 BTree 的基礎上做了改進，那麼到底改變了什麼呢。廢話不多說，先上圖。

上圖實際上是一種帶有順序索引的 B+Tree，與最基本的 B+Tree 的區別就在於葉子節點是否透過指標相連。一般資料庫中常用的結構都是這種帶有順序索引的 B+Tree。後文探討的也都是帶順序索引的 B+Tree 結構。

對比 BTree 和 B+Tree，我們可以發現二者主要在以下三個方面上的不同：

非葉子節點只儲存鍵值資訊，不再儲存資料。

所有葉子節點之間都有一個鏈指標，指向下一個葉子節點。

資料都存放在葉子節點中。

看著 B+Tree，像不像是一顆樹與一個有序連結串列的結合體。因而其實 B+Tree 也就是帶有樹和連結串列的部分優勢。樹結構使得有序檢索更為簡單，I/O 次數更少；有序連結串列結構使得可以按照鍵值排序的次序遍歷全部記錄。

B+Tree 在作為索引結構時能夠帶來的好處有：

一，I/O 次數更少。這是因為上文也說過，BTree 的節點是存放在記憶體頁中的。那麼在相同的記憶體頁大小（一般為4k）的情況下，B+Tree 能夠儲存更多的鍵值，那麼整體樹結構的高度就會更小，需要的 I/O 次數也就越小。

二，資料遍歷更為方便。這個優勢很明顯是由有序連結串列帶來的。透過葉子節點的連結，使得對所有資料的遍歷只需要線上性的連結串列上完成，這就非常適合區間檢索和範圍查詢。

三，查詢效能更穩定。這自然是由於只在葉子節點儲存資料，所以所有資料的查詢都會到達葉子節點，同時葉子節點的高度都相同，因此理論上來說所有資料的查詢速度都是一致的。

正是由於 B+Tree 優秀的結構特性，使得常用作索引的實現結構。在 MySQL 中，儲存引擎 MyISAM 和 InnoDB 都分別以 B+Tree 實現了響應的索引設計。

物理儲存

雖說 B+Tree 結構都可以用在 MyISAM 和 InnoDB，但是這二者對索引的在物理儲存層次的實現方式卻不相同。InnoDB 實現的是聚簇索引，而 MyISAM 實現的卻是非聚簇索引。在介紹聚簇索引之前，我們需要先了解以下啥是佩奇，不對，是啥是「主鍵索引」和「輔助索引」。

其實概念很簡單。我們剛剛不是在講 B+Tree 的時候說過，樹的非葉子節點只儲存鍵值。沒錯就是這個鍵值，當這個鍵值是資料表的主鍵時，那麼所建立的就是主鍵索引；當這個鍵值是其它欄位的時候，就是輔助索引。因而可以得出，主鍵索引只能有一個，而輔助索引卻可以有很多個。

聚簇索引和非聚簇索引的區別也就是根據其對應的主鍵索引和輔助索引的不同特點而實現的。

聚簇索引

說回聚簇索引。先丟個定義。

聚簇索引的主鍵索引的葉子結點儲存的是鍵值對應的資料本身；輔助索引的葉子結點儲存的是鍵值對應的資料的主鍵鍵值。

這句話的資訊量挺大的。首先，分析第一句話，主鍵索引的葉子節點儲存的是鍵值對應的資料本身。

我們知道，主鍵索引儲存的鍵值就是主鍵。那麼也就是說，聚簇索引的主鍵索引，在葉子節點中儲存的是主鍵和主鍵對應的資料。資料和主鍵索引是儲存在一起的，一起作為葉子節點的一部分。

然後，分析第二句話，輔助索引的葉子結點儲存的是鍵值對應的資料的主鍵鍵值。

我們又知道，輔助索引儲存的鍵值是非主鍵的欄位。那就也就是說，透過輔助索引，可以找到非主鍵欄位對應的資料行中的主鍵。

重點來了。當然主鍵索引和輔助索引一結合，能幹啥呢。當直接採用主鍵進行檢索時，可透過主鍵索引直接獲得資料；而當採用非主鍵進行檢索時，先需要透過輔助索引來獲得主鍵，然後再透過這個主鍵在主鍵索引中找到對應的資料行。

舉個例子吧。假設有這麼一個數據表。

那麼採用聚簇索引的儲存方式，對應的主鍵索引為：（主鍵為ID）

對應的輔助索引為：（鍵值為Name，大概的意思）：

所以當使用where ID = 7這樣的條件查詢主鍵，則按照B+樹的檢索演算法即可查詢到對應的葉節點，之後獲得行資料。對Name列進行條件搜尋，則需要兩個步驟：第一步在輔助索引B+樹中檢索Name，到達其葉子節點獲取對應的主鍵。第二步使用主鍵在主鍵索引B+樹種再執行一次B+樹檢索操作，最終到達葉子節點即可獲取整行資料。

最後把以上過程整理總結一下，聚簇索引實際上的過程就分為以下兩個過程。現在這個圖應該能夠看懂了吧。

非聚簇索引

學完了聚簇索引，非聚簇索引就簡單多啦。同樣，先上定義。

非聚簇索引的主鍵索引和輔助索引幾乎是一樣的，只是主索引不允許重複，不允許空值，他們的葉子結點都儲存指向鍵值對應的資料的物理地址。

與聚簇索引來對比著看，上面的定義能夠說明什麼呢。首先，主鍵索引和輔助索引的葉子結點都儲存著鍵值對應的資料的物理地址，這說明無論是主鍵索引還是輔助索引都能夠透過直接獲得資料，而不需要像聚簇索引那樣在檢索輔助索引時還得多繞一圈。

同時還說明一個點，葉子結點儲存的是物理地址，那麼表示資料實際上是存在另一個地方的，並不是儲存在B+樹的結點中。這說明非聚簇索引的資料表和索引表是分開儲存的。

同樣，對非聚簇索引的檢索過程來個總結。

無論是主鍵索引還是輔助索引的檢索過程，都只需要透過相應的 B+Tree 進行搜尋即可獲得資料對應的物理地址，然後經過依次磁碟 I/O 就可訪問資料。

對比聚簇索引和非聚簇索引，可以發現二者最主要的區別就是在於是否在 B+Tree 的節點中儲存資料，也就是資料和索引是否儲存在一起。這個區別導致最大的問題就是聚簇索引的索引的順序和資料本身的順序是相同的，而非聚簇索引的順序跟資料的順序沒有啥關係。

索引最佳化

介紹了這麼多的索引，其實最終都是為了建立高效能的索引策略，對資料庫中的索引進行最佳化。索引的最佳化有很多角度，針對特定的業務場景可採用不同的最佳化策略。這裡考慮到文章篇幅，就不具體介紹，下次再出一篇專門講索引最佳化的文章。簡單列舉一下在進行最佳化時可以考慮的幾個方向：

1 獨立的列。索引列不能是表示式的一部分，也不能是函式的引數。

2 字首索引和索引選擇性。這二者實際上是相互制約的關係，制約條件在於字首的長度。一般應選擇足夠長的字首以保證較高的選擇性（保證查詢效率），同時又不能太長以便節省空間。

3 儘量使用覆蓋索引。覆蓋索引是指一個索引包含所有需要查詢的欄位的值，這樣在查詢時只需要掃描索引而無須再去讀取資料行，從而極大的提高效能。

4 使用索引掃描來做排序。要知道，掃描索引本身是很快的，在設計索引時，可儘可能的使用同一個索引既滿足排序，又滿足查詢行資料。

最後，在建立索引時給幾個小貼士：

1 優先使用自增key作為主鍵

2 記住最左字首匹配原則

3 索引列不能參與計算

4 選擇區分度高的列作索引

5 能擴充套件就不要新建索引

總結

索引的概念和原理是我們在瞭解和精通資料庫過程中無法逃避的重點，而事實上建立高效能的索引對實際的應用場景也具有重要意義。本文的目的依舊是由淺入深的介紹索引這麼個東西，從概念到實現再到最終的最佳化策略。

點到為止，學無止境。掌握了基本的理論和概念後，還需要在實際的伺服器開發場景中針對具體的問題和服務進行索引最佳化方案的設計和使用。功力不夠，仍需努力。

Reference

高效能 MySQL，Baron Schwartz 等人著，電子工業出版社

公眾號碼海系列文章：

https：//www。jianshu。com/p/9e9aca844c13

https：//www。runoob。com/mysql/mysql-index。html

https：//www。cnblogs。com/Aiapple/p/5693239。html

https：//blog。csdn。net/tongdanping/article/details/79878302

https：//www。cnblogs。com/igoodful/p/9361500。html