索引是對資料庫表中一列或多列的值進行排序的一種結構，使用索引可快速訪問資料庫表中的特定資訊，可以將資料庫索引和書的目錄進行類比，通過書的目錄我們可以快速查找到章節位置，如果沒有目錄就只能一頁頁翻書查找了，

索引資料結構

可以用于提升查詢效率的索引結構很多，常見的有B樹索引、哈希索引和B+樹索引，接下來我們會對這些索引一一進行介紹，并說明InnoDB為什么采用B+樹作為索引，

磁盤IO

檔案是存盤在硬碟上面的，當下硬碟的讀取速度十分有限，所以在進行查詢定位某個資料的時候，應該盡可能地減少磁盤I/O次數，

磁盤預讀

由于存盤介質的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百分之一，因此為了提高效率，要盡量減少磁盤I/O，為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個位元組，磁盤也會從這個位置開始，順序向后讀取一定長度的資料放入記憶體，這樣做的理論依據是計算機科學中著名的區域性原理：當一個資料被用到時，其附近的資料也通常會馬上被使用，程式運行期間所需要的資料通常比較集中，

區域性原理：CPU訪問存盤器時，無論是存取指令還是存取資料，所訪問的存盤單元都趨于聚集在一個較小的連續區域中，

預讀的長度一般為頁（page）的整倍數，頁是計算機管理存盤器的邏輯塊，硬體及作業系統往往將主存和磁盤存盤區分割為連續的大小相等的塊，每個存盤塊稱為一頁（在許多作業系統中，頁的大小通常為4k），主存和磁盤以頁為單位交換資料，當程式要讀取的資料不在主存中時，會觸發一個缺頁例外，此時系統會向磁盤發出讀盤信號，磁盤會找到資料的起始位置并向后連續讀取一頁或幾頁載入記憶體中，然后例外回傳，程式繼續運行，

合理利用磁盤預讀

一般來說，索引本身也很大，不可能全部存盤在記憶體中，因此索引往往以索引檔案的形式存盤的磁盤上，這樣的話，索引查找程序中就要產生磁盤I/O消耗，相對于記憶體存取，I/O存取的消耗要高幾個數量級，所以評價一個資料結構作為索引的優劣最重要的指標就是在查找程序中磁盤I/O操作次數，換句話說，索引的結構組織要盡量減少查找程序中磁盤I/O的存取次數，

如果我們能合理使用磁盤預讀的特性，使每次磁盤IO讀到的頁中的資料都是有用的，就可以大大提升資料的查詢效率，

B樹索引

B樹可以看作是對二叉查找樹的一種擴展，B樹允許每個節點有M-1個子節點，B樹有以下特點：

1. 根節點至少有兩個子節點；
2. 每個節點包含M-1條資料，節點中的資料安裝索引遞增順序排序；
3. 節點中有最多有M個指標指向下一層節點，這些指標位于節點的多個資料之間，下一層節點的所有資料值大于指標左側的資料，小于指標右側的資料；
4. 每個節點至少包含M/2條資料；

接下來我們用下表示例的用戶資料來構建B樹，如表所示，用戶資料包含姓名、性別、年齡三個欄位，我們把用戶年齡作為資料庫主鍵(假設年齡具有唯一性)，那么構建出來的B樹的結構如下圖所示，

|||||||||||
|--|--|--|--|--|--|--|--|--|--|--|
|姓名|陳爾|張散|李思|王舞|趙流|孫期|周跋|吳酒|鄭史|
|性別|男|男|女|女|男|男|男|女|男|
|年齡|5|10|20|28|35|56|25|80|90|

![B樹索引]

相比較與常見的二叉樹，B樹的一個節點中存放了更多的資料，這樣做可以有效的減少一次資料查找程序中的磁盤IO次數：

• 二叉樹每個節點只存放一個資料，節點之間用指標關聯，節點之間的空間是離散的，所以每個節點都對應一次磁盤IO，查找一次資料的IO次數為O($log_2$N)；
• B樹的節點可以存放M-1個資料，如果這M-1個資料剛好可以放到一個頁中，那么B樹查找一次資料的IO次數為O($log_M$N)；

哈希索引

哈希索引基于哈希表實作，只有精確匹配索引所有列的查詢才有效，哈希表是一種以鍵-值(Key-Value)存盤資料的結構，用戶可以在O(1)時間復雜度內按照Key查找到對應的Value，

哈希表通常是一個陣列，資料在陣列中的位置可以按照索引的值安裝哈希演算法進行計算，如果兩個資料的索引值計算出來的位置相同，那么通常可以采用鏈地址法解決沖突（其它解決地址沖突的方法還有開放定制法，鏈地址法，公共溢位區法，再散列法等），

如下表資料所示，我們依舊按照用戶的年齡為用戶資料建立索引(假設用戶年齡不會相同)，我們采用的哈希演算法為 addr=age%10，我們可以建立長度為10的陣列作為哈希表，按照哈希函式一一把用戶放入哈希表，按照用戶年齡查找用戶時，可以直接計算出用戶所在的位置，從而得到用戶資訊，最終得到的哈希表以及查詢流程如下圖所示，

哈希索引有以下優點：

1. 占用的額外空間小，為資料新建一個哈希索引需要的額外空間為O(N)，和索引欄位長度無關；
2. 查詢速度極快，哈希函式合理的情況下，程式可以在O(1)的磁盤IO次數內查找到資料；

哈希索引有以下缺點：

1. 無法進行范圍查詢，哈希程序中已經丟失了索引的順序性；
2. 無法對資料進行排序查找，比如查找年齡最大的用戶；
3. 無法使用部分索引查找，比如前綴查詢等；
4. 哈希函式不合理的情況下，會導致哈希沖突問題，造成查詢效率變低；

B+樹索引

InnoDB使用的索引的資料結構是B+樹，資料庫表定義中的每一個索引對應一顆B+樹，默認的聚簇索引也是一顆B+樹，B+樹有以下特征：

1. 所有節點關鍵字是按遞增次序排列，并遵循左小右大原則；
2. 非葉節點的子節點數在1到M之間(下圖中M為3)，空樹除外；
3. 非葉節點的索引數目大于等于ceil(M/2)個且小于等于M個；
4. 所有葉子節點均在同一層，葉子節點之間有從左到右的指標；
5. 資料存盤在葉子節點，非葉子節點只存盤索引；

接下來我們用幾條示例的用戶資料來構建B+樹，如表所示，用戶資料包含姓名、性別、年齡三個欄位，我們把用戶年齡作為資料庫主鍵(假設年齡具有唯一性)，那么構建出來的B+樹的結構如下圖所示，

B+樹索引資料結構有以下列出的幾種優勢：

1. 查詢性能穩定，查詢一條資料需要的IO次數往往是樹的高度次；
2. 范圍查詢效率高，安裝索引范圍查詢時，可以先查找的第一個滿足要求的資料，然后向后遍歷，直到第一個不滿足條件的資料為止，中間的資料都符合要求；
3. 查詢效率高，往往一次資料查詢只需要2~3次磁盤IO；
4. 葉子節點存盤所有資料，不需要去B+樹之外找資料；

InnoDB為什么采用B+樹

在InnoDB引擎中，我們為資料庫創建的索引都是以B+樹的形式存在，為什么InnoDB不采用哈希索引或者B樹索引呢？主要是基于以下原因：

• 資料庫查詢經常會出現非等值查詢，哈希索引在這種情況下無法作業；
• 相比于B樹，B+樹索引非葉子節點不存放資料，從而磁盤一次IO可以讀取更多的索引資料，有效減少磁盤IO次數；
• 資料庫查詢經常會出現范圍查詢，B+樹底層的葉子節點之間按照順序排列，可以更有效的實作范圍查詢；

自增主鍵

通過上文我們知道，B+樹需要維護索引的有序性，

1. 當用戶向B+樹插入資料，如果插入點對應的節點有空余位置，那么只需要挪動節點中的資料，并把需要插入的資料放入B+樹即可；
2. 當用戶向B+樹插入資料，如果插入點對應的節點沒有空余位置，那么就需要生成一個新的節點，并把一部分資料挪過去；這種情況不僅會影響插入效率，由于分裂出來的節點只有部分資料，所以會導致空間的利用率降低；
3. 當用戶洗掉B+樹中的資料時，如果節點或相鄰節點的資料量很少，那么只需要直接洗掉資料，并按挪動節點中的其它資料即可；
4. 當用戶洗掉B+樹中的資料時，如果節點和相鄰節點的資料量很少，那么在洗掉之后，可能需要把節點和相鄰節點合并，從而提高空間利用率；

基于B+樹需要維護索引有序性的特點，我們對索引欄位提出以下建議：

1. 對于資料插入比較多的場景，主鍵索引欄位最好是遞增的，遞增的主鍵每次插入一條新記錄，都是追加操作，都不涉及到挪動其他記錄，也不會觸發葉子節點的分裂，
2. 主鍵索引的長度應當盡量小，主鍵長度越小，普通索引的葉子節點就越小，普通索引占用的空間也就越小，

在InnoDB中，我們應當盡量使用自增主鍵，自增主鍵有插入效率高、占用空間小等優勢，

資料空洞與重建索引

資料空洞

當你對InnoDB進行修改操作時，例如洗掉一些行，這些行只是被標記為“已洗掉”，而不是真的從索引中物理洗掉了，因而空間也沒有真的被釋放回收，InnoDB的Purge執行緒會異步的來清理這些沒用的索引鍵和行，但是依然沒有把這些釋放出來的空間還給作業系統重新使用，因而會導致頁面中存在很多空洞，如果表結構中包含動態長度欄位，那么這些空洞甚至可能不能被InnoDB重新用來存新的行，因為空間空間長度不足，

資料空洞帶來的問題：

1. 洗掉表中的資料后，表占用的空間不會變小，造成空間浪費；
2. 會降低資料查詢的速度，因為空洞會占用頁空間；

我們可以通過以下SQL來查看資料庫中的空洞大小，執行陳述句如下所示，回傳結果中的DATA_FREE表示表中空閑資料塊的大小，

select data_length,data_free from information_schema.tables where table_schema='test' and table_name='test';

重建索引

當一張表的索引中的資料空洞過多時，會影響SQL陳述句的執行效率，此時我們就需要清理這些資料空洞，

清理資料空洞比較好的辦法是重建索引，因為重建索引的程序中，會按照索引的大小排序后建立索引，建立出來的索引比較緊湊，

有什么辦法可以重建索引呢？我們比較直觀的想法肯定是先洗掉索引，再重建索引，然而不論是洗掉主鍵還是創建主鍵，都會將整個表重建，所以連著執行這兩個陳述句的話，第一個陳述句就白做了，

alter table user_info drop primary key;
alter table user_info add primary key(id);

InnoDB中可以通過以下轉換資料引擎的陳述句來重建表的所有索引，這是因為在轉換資料引擎（即使沒有真正轉換）的程序中，會讀取表中所有的資料，再重新寫入，這個程序中，會釋放空洞，需要注意的是，通過這種方法重建索引耗時比較長，

alter table test engine=innodb

本文最先發布至微信公眾號，著作權所有，禁止轉載！

標籤：Java

上一篇：執行緒池使用

下一篇：十七、JDK8 新特性（完結）