5.3 B+ 樹

B+ 樹是為磁碟或其他直接存儲輔助設備設計的一種平衡查找樹。在B+樹中，所有記錄都是按照鍵值大小順序存放在同一層的葉子節點上，由葉子節點指針進行連接，雙向鏈表連接。

5.3.1 B+ 樹的插入操作

考慮一下三種情況：

可以看到，為了保持平衡對於新插入的鍵值可能需要做大量的拆分頁操作。因為 B+ 樹主要用於磁碟，頁的拆分意味著磁碟的操作，所以，應該在可能的情況下儘量減少頁的拆分。因此，B+ 樹提供了類似平衡二叉樹的旋轉功能（Rotation）。

旋轉發生在Leaf Page滿，但其左右兄弟節點沒有滿的情況下，這時B+樹不是先拆頁，而是將記錄移到所在頁的兄弟節點上。通常情況下，左兄弟會首先被用來檢查做旋轉操作，採用旋轉操作會使B+ 樹減少一次頁的拆分，同時有利於減少B+樹的高度。

5.3.2 B+ 樹的刪除操作

B+樹的刪除操作同樣必須保證刪除後葉子界點依然有序，同時 B+ 樹使用填充因數（fill factor）來控制樹的刪除變化，50%是可控制的最小值。與插入不同的是，刪除根據填充因數的變化來衡量。

5.4 B+ 樹索引

B+ 樹的特點就是高扇出性，因此，在資料庫中，B+ 樹的高度一般在 2~4 層，也就是說查找某一鍵值的行記錄時最多只需要2到4次的IO，大概耗時在 0.02~0.04秒。

5.4.1 聚集索引

聚集索引就是按照每張表的主鍵構造一棵  B+樹，同時葉子節點存放的是整張表的行記錄數據，也將聚集索引的葉子節點稱為數據頁，每個數據頁之間通過一個雙向鏈表進行連接。

數據頁上存放的是完整的每行的記錄，而非數據頁的索引頁中，存放的僅僅是鍵值及指向數據頁的偏移量，而不是完整的行記錄。

聚集索引並不是物理上連續的，而是邏輯連續。即 頁通過雙向鏈表連接，頁按照主鍵的順序排序。另一點是每個頁中的記錄也是通過雙向鏈表韋華的，物理存儲上可以同樣不按照主鍵存儲。

聚集索引對於主鍵的排序查找和範圍查找速度很快。

5.4.2 輔助索引

 輔助索引的葉子節點並不包含行記錄的全部數據。葉子節點除了包含鍵值以外，每個葉子節點中的索引行中還包含一個書簽。該書簽用來告訴 InnoDB哪裡可以找到與索引相對應的行數據。

非聚集索引存在離散讀問題，但一般的資料庫都通過實現預讀（read ahead）技術來避免多次離散讀的問題。

5.4.3 B+ 樹索引的分裂

5.3 中B+樹的分裂是最簡單的一種情況，這和資料庫中B+ 樹索引的情況略有不同。而且5.3中沒有涉及併發，這才是B+樹索引實現最困難的地方。

B+ 樹索引頁的分裂並不總是從頁的中間記錄開始，這樣可能會導致頁空間的浪費，例如自增主鍵的插入。

InnoDB 存儲引擎的Page Header中有以下幾部分用來保存插入的順序信息：

• PAGE_LAST_INSERT
• PAGE_DIRECTION
• PAGE_N_DIRECTION

通過這些信息，InnoDB決定是向左還是向右分裂，同時決定分裂點記錄是哪一個。

若插入是隨機的，則取頁的中間記錄為分裂點

若往同一個方向進行插入的記錄是5，且目前已定位到的記錄之後還有3條記錄，則分裂點為定位到的記錄後的第三條記錄，否則分裂點記錄就是待插入的記錄。

InnoDB 存儲引擎插入時，首先需要進行定位，定位到記錄為待插入記錄的前一條記錄

自增插入時，分裂點就是插入記錄本身，向右分裂。

5.4.4 B+樹索引的管理

1. 索引管理

索引的創建和刪除可以通過兩種方法，alter table 或 create/ drop index

通過 show index from 可以觀察到表的索引。接著闡述 show index結果中每列的含義。

• table ：索引所在的表名
• Non_unique：非唯一的索引，0標識唯一索引，1標識非唯一索引。
• Key_name：索引的名字，用戶可以根據這個名字執行 drop index
• Seq_in_index：索引中該列的位置，一般為聯合索引中列的位置
• Column_name：索引列的名稱
• Collation：列以什麼方式存儲在索引彙總，A或者NULL，B+ 樹索引總是A，標識排序的。
• Cardinality：索引中唯一值的數目的估計值。值越大區分度越大。
• Sub_part：是否是列的部分被索引，例如 add key idx_b(b(100)) ,只對b欄位的前100個字元索引。如果索引整個列，該欄位為NULL
• Packed：關鍵字如何被壓縮，沒有壓縮，為NULL
• Null：索引列是否含有空值
• Index_type：索引類型，InnoDB 只支持B+ Tree，所以這裡都顯示BTREE
• Comment：註釋

2. Fast Index Creation

FIC 在索引創建的過程中對錶加了S鎖，因此在創建的過程中只能對該表進行讀操作。若此時有大量的事務需要對目標表進行寫操作，那麼資料庫的服務同樣不可用。此外，FIC只限定於輔助索引，對主鍵的創建和刪除同樣需要重建表

4. Online DDL

雖然FIC可以讓InnoDB存儲引擎避免創建臨時表，從而提高索引創建的效率，但會阻塞表上的DML 操作。MySQL 5.6 開始支持 Online DDL操作,允許輔助索引創建的同時，還允許其他DML 操作。

此外，不僅是輔助索引，以下幾類操作都是通過”線上“的方式進行操作：輔助索引的創建和刪除；改變自增長值；添加或刪除外鍵約束；列的重命名；

通過新的alter table 語法，用戶可以選擇索引的創建方式：

alter table tbl_name

| ADD {INDEX | KEY} [index_name]

[index_type] (index_col_name……)[index_option]……

ALGORITHM[=]{DEFAULT | INPLACE | COPY}

LOCK[=]{DEFAULT | NONE | SHARED |EXCLUSIVE}

　　ALGORITHM指定了創建或刪除索引的演算法，COPY標識MySQL 5.1 版本之前的工作模式，即創建臨時表的方式。INPLACE 標識索引創建或刪除操作不需要創建臨時表。DEFAULT 標識根據參數 old_alter_table 來判斷是通過 INPLACE 還是 COPY 演算法，該參數的預設值是 OFF，標識採用 INPLACE 的方式。

　　LOCK部分為索引創建或刪除時對標添加鎖的情況，可有的選擇為：

1. NONE：執行索引創建或刪除操作時，對目標表不添加任何的鎖，即事務可以進行讀寫操作，不會收到阻塞。因此，這種模式可以獲得最大的併發度。
2. SHARE：類似FIC，對目標表加S鎖，阻塞寫。如果不支持SHARE模式，會返回一個錯誤的信息。
3. EXCLUSIVE：加X鎖，讀寫事務都不能進行，會阻塞所有的線程，但不需要像COPY那樣創建臨時表
4. DEFAULT：default 模式會首先判斷當前操作是否可以使用NONE模式。若不能，降級到SHARE模式，最後看是否可以使用 EXCLUSIVE模式。也就是說DEFAULT會通過判斷失誤的最大併發度來執行DDL 的模式

InnoDB 存儲引擎實現 Online DDL 的原理是在執行創建或刪除操作的同時，將INSERT、UPDATE、DELETE 這類DML 操作日誌寫入到一個緩存中。待完成索引創建後再將重做應用到表上，以此達到數據的一致性。這意味著在索引創建的過程中，SQL優化器不會選擇正在創建中的索引。

5.5 Cardinality

5.6 B+樹索引的使用

5.6.2 聯合索引

從本質來看，聯合索引也是一棵B+樹。聯合索引是最左首碼匹配。

聯合索引（a,b）其實是根據列a，b進行排序的，因此下列語句可以直接使用聯合索引查詢結果

select * from table where a= xxx order by b

　　然而對於聯合索引（a,b,c）下列語句同樣可以直接使用索引得到結果

select * from table where a = xxx order by b
select * from table where a = xx and b = xx order by c

　　但是下麵的語句不能直接使用聯合索引（a,b,c），因為索引（a,c）並未排序

select * from table where a = xx order by c

5.6.3 覆蓋索引

InnoDB支持覆蓋索引，即從輔助索引中就可以得到查詢的記錄，而不需要查詢聚集索引的記錄。使用覆蓋索引的好處是輔助索引不包含整行記錄的所有信息，故其大小要遠小於聚集索引，因此大量減少IO操作。

覆蓋索引的另一個好處是對於某些統計問題而言，

通常情況下，諸如（a,b）的聯合索引，一般是不可以選擇列b中所謂的查詢條件，但如果是統計，並且是覆蓋索引的，則優化器會進行選擇

select count(*) from  table where b < xxx and b > yyy

5.6.4 優化器選擇不使用索引的情況

某些情況下，當執行 explain 命令進行sql語句分析時，發現優化器並沒有選擇索引去查找數據，而是通過掃描聚集索引，也就是全表掃描。這種情況多發生與範圍查找、JOIN 操作等情況。

即explain分析得到key使用的是 PRIMARY。

因為，用戶要選取的數據是整行信息，即 select * ，而索引並不能覆蓋我們要查詢的信息，因此在對輔助索引查詢到指定數據後，還需要進行一次書簽訪問來查找整行數據的信息。雖然輔助索引中數據是順序排放的，但再一次書簽查找是無序的，因此變為了磁碟的離散讀操作。如果要訪問的數據量小，則優化器會選擇輔助索引，但當訪問的數據量大（一般為20%左右），優化器會選擇聚集索引來查找數據，因為順序讀要遠遠快於離散讀。這是由當前傳統機械硬碟的特性決定的，即利用順序讀代替隨機讀的查找。如果用戶使用的是固態硬碟，隨機讀很快，同時可以確認使用輔助索引可以帶來更好的性能，可以使用 force index 強制使用某個索引

5.6.5 索引提示

MySQL支持索引提示（INDEX HINT），顯示的告訴優化器使用哪個索引。個人總結兩種情況可能使用索引提示：

• MySQL優化器錯誤的選擇某個索引，導致SQL運行慢，較少見
• 某SQL可以選擇的索引非常多，這時優化器選擇執行計劃時間的開銷可能大於SQL本身

5.6.6 Multi—Range READ 優化

MySQL 5.6 開始支持 Multi-Range READ（MRR） 優化，目的是為了減少磁碟的隨機訪問，並將隨機訪問轉化為較為順序的數據訪問，適用於 range、ref、eq_ref類型的查詢。

MRR有以下幾個好處：

1. MRR使數據訪問變得較為順序。在查詢輔助索引時，首先根據得到的查詢結果，按照主鍵進行排序，並按照主鍵排序的順序進行書簽查找
2. 較少緩衝池中頁被替換的速度
3. 批量處理對鍵值的查詢操作

對於InnoDB和MyISAM的範圍查詢和JOIN操作，MRR的工作方式如下：

• 將查詢得到的輔助索引鍵值存放在一個緩衝中，這時緩衝內的數據是根據輔助索引鍵值排序的
• 將緩存中的鍵值根據 ROWID排序
• 根據ROWID的排序順序訪問實際的數據文件。

此外，若InnoDB的緩衝池不是很大，不能放下一張表中的所有數據，此時頻繁的離散讀還會導致緩存中的頁被替換出緩衝池，然後又不斷的讀入緩衝池。若是按照主鍵順序的訪問，則可以將此重覆行為將至最低。如下麵的SQL:

select * from table where salary > 10000 and salary < 44000;

　　salary 有一個輔助索引idx_s，因此除了通過輔助索引查找鍵值外，還需要通過書簽查找來進行對整行的查詢，當不啟用MRR時，執行計劃中的 Extra 顯示 Using index condition，啟用MRR後，Extra 除了有 Using Index Condition 還有 Using MRR，執行時間相差10倍之多。註意：該測試都是在MySQL資料庫剛剛啟動時執行的，確保緩衝池中沒有預熱。

此外，MRR 還可以將某些範圍查詢拆分為鍵值對，以此來進行批量的數據查詢。這樣做的好處是在拆分過程中，可以過濾一些不符合查詢條件的數據。

select * from t 
where key_part1 >= 1000 and key_part1 < 2000 
and key_part2 = 1000

　　表t有（key_part1, key_part2）的聯合索引，如果沒有MRR，則查詢類型為 Range，SQL 優化器會先將key_part1 符合範圍的數據都取出來，即使 key_part2 不等於1000，然後再對數據進行過濾。這就導致無用的數據被取出，如果有大量數據且 key_part2 != 1000,則 MRR 會使性能提升很快。

　　啟用MRR之後，優化器會先對查詢條件進行拆分。就上述語句，會拆分為（1000，1000），（1001， 1000），（1002，1000）……（1999，1000），最後再根據這些拆分出來的條件進行查詢。

    實際例子如下：

select *  from salaries 
where （from_date between '1986-01-01' and '1995-01-01'）
and  (salary between 38000 and 40000)

5.6.7 Index Condition Pushdown (ICP)優化

當進行索引查詢時，首先根據索引來查找記錄，然後再根據where過濾。在支持 ICP後，MySQL會在取出索引的同時，判斷是否可以進行where條件的過濾，也就是將where的部分過濾操作放在了存儲引擎層。

ICP 優化支持 range、ref、eq_ref、ref_or_null類型的查詢。若使用了ICP，可以在執行計劃的Extra列看到 Using Index condition。當然 where 可以過濾的條件是要該索引可以覆蓋到的範圍。

5.7 哈希演算法

5.7.1 哈希表

哈希表也叫散列表，由直接定址表改進而來。哈希表，在哈希方式下，該元素處於h(k)中，即利用哈希函數h，根據關鍵字k計算出槽的位置。哈希表存在碰撞問題，在資料庫中一般採用鏈接法解決碰撞。

5.7.2 InnoDB 中的哈希演算法

InnoDB 使用哈希演算法對字典進行查找，其衝突機制採用鏈表方式，哈希函數採用除法散列方式。對緩衝池頁的哈希表來說，在緩衝池中的Page頁都有一個chain指針，它指向相同哈希函數值的頁。而對於除法散列，m取值為略大於2倍的緩衝池頁數量的質數。

例如，當前參數 innodb_buffer_pool_size為10M，則共有 640 個16KB 的頁。對於緩衝池頁的哈希表來說，需要分配 640 * 2 = 1280 個槽，但1280 不是質數，比1280稍大的質數為 1399，所以在啟動時會分配 1399 個槽的哈希表，用來哈希查詢所在緩衝池中的頁。

那InnoDB 緩衝池對於其中的頁是怎麼查找呢？上面只是給出了一般的演算法，怎麼將要查找的頁轉換成自然數呢？

InnoDB的表空間都有 space id，用戶所要查詢的應該是某個表空間的某個連續的16KB的頁，即偏移量offset。InnoDB將 space_id 左移20位，然後加上space_id和offset，即關鍵字k= space_id << 20 + space_id + offset ,然後通過除法散列。

5.7.3 自適應哈希索引

AHI 是資料庫自身創建並使用的，DBA不能進行干預。哈希索引只能用於等值查詢，不能用於範圍查找。

5.8 全文檢索

5.8.1 概述

B+樹索引對 where a like "%abc%"無能為力，即使對a 添加索引，也是需要進行全表掃描的。

全文檢索（Ful-Text Search）是將存儲於資料庫中的整本書或整個文章中的任意內容信息查找出來的技術，可以根據需要獲取全文中的有關章、節、段、句、詞等信息，也可以用於統計和分析。

從InnoDB 1.2.x開始，InnoDB開始支持全文檢索，其支持 MyISAM存儲引擎的全部功能，並且還支持其他的一些特性。

5.8.2 倒排索引（Inverted index）

全文索引通常使用倒排索引來實現，倒排索引也是一種索引結構，它在輔助表中存儲了單詞與單詞自身在一個或多個文檔中所在位置鍵的映射，通常這利用關聯數組來實現，其擁有兩種表現形式：

• inverted File index：表現形式為{單詞，單詞所在的文檔id}
• full inverted index：表現形式為 {單詞，（單詞所在的文檔id， 在具體文檔中的位置）}

5.8.3 InnoDB全文索引

InnoDB 從1.2.x 開始支持全文索引的技術，並採用 full inverted index 的方式。在 InnoDB 存儲引擎中，將 （單詞所在的文檔id/doucumentId, 在文檔中的具體位置/Position） 視為一個ilist。

在全文檢索的輔助表中，有兩列，分別是 word 列 和 ilist 列。

正如之前所說的，倒排索引需要將word 存放在一張表中，這個表稱為 Auxiliary table（輔助表）。在InnoDB中，為了提高性能，共有6張輔助表，目前每張表根據 word 的Latin 編碼進行分區。

Auxiliary table 是持久性的表，存放在磁碟上。然而在 InnoDB的全文索引中，還有另一個概念，FTS Index Cache（全文檢索索引緩存），用來提高全文檢索性能。

FTS Index Cache 是一個紅黑樹結構，根據（word，ilist）進行排序，這意味著插入的數據已經更新了對應的表，但對全文索引的更新可能在分詞操作後，還在FTS Index cache中，Auxiliary table 可能還沒更新。InnoDB對 Auxiliary 的更新是批量的，當全文檢索時，Auxiliary table 首先會將在 FTS Index Cache中對應的 word 欄位合併到 Auxiliary table 中，然後再查詢。這種merge操作類似 Insert Buffer。

FTS Document ID 是另一個重要概念，InnoDB中，為了支持全文檢索，必須有一個列與 word 進行映射，在 InnoDB中這個列被稱為 FTS_DOC_ID，其類型必須是 BIGINT UNSIGNED NOT NULL，並且InnoDB會自動在該列上加入一個名為 FTS_DOC_ID_INDEX 的 Unsigned Index。這些操作都是InnoDB自動完成的。

stopword 列表（stopword list）是本節最後一個概念，標識該列表中的word不需要對其進行索引分詞操作，例如 the 。InnoDB有一張預設的 stopword list 表，表名為 INNODB_FT_DEFAULT_STOPWORD，預設有36個stopword，用戶可自定義。

當前InnoDB的全文檢索還存在以下問題：

1. 每張表只能有一個全文檢索的索引
2. 由多列組成的全文檢索的索引列必修使用相同的字元集與排列規則
3. 不支持沒有單詞界定次的語言，如中文、日語、韓語等

5.8.4 全文檢索（待續……）