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 全文檢索（待續……）

標籤：MySQL

上一篇：左匹配原則，聚集索引，回表查詢，索引覆寫 你真的懂了嗎

下一篇：求助：一列資料中某一個是其他資料之和