1. MySQL索引為什麼使用B+樹資料結構，而不是B樹，紅黑樹等？
1.1 二叉查找樹/二叉搜尋樹
下圖b為二叉查找樹的典型結構，其特點為：
- 任意節點左子樹不為空,則左子樹的值均小于根節點的值
- 任意節點右子樹不為空,則右子樹的值均大于于根節點的值
- 任意節點的左右子樹也分别是二叉查找樹
- 沒有鍵值相等的節點
局限性： 如果資料排序好插入二叉查找樹時，會退化為連結清單，此時時間複雜度為O（n），最好的情況是O（log n）。
1.2 AVL 樹（Adelson-Velsky and Landis Tree，平衡二叉樹）
由于二叉查找樹的局限性，引入了AVL樹，在插入資料時，調整這棵樹，讓它的節點盡可能均勻分布。該樹節點左右子樹深度之差隻能是0，1，-1. 如果插入資料後，不滿足平衡性，會通過旋轉來實作平衡，具體的通過旋轉保證平衡的四種操作參見專欄https://www.bilibili.com/read/cv8748171。
局限性：旋轉是非常耗時的，故而AVL樹适合用于插入删除次數比較少，但查找多的情況。
1.3 紅黑樹
紅黑樹是平衡二叉樹的一種變體。紅黑樹確定沒有一條路徑會比其它路徑長出兩倍。它是一種弱平衡二叉樹(由于是弱平衡，可以推出，相同的節點情況下，AVL樹的高度低于紅黑樹)，相對于要求嚴格的AVL樹來說，它的旋轉次數少，是以對于搜尋、插入、删除操作較多的情況下，就用紅黑樹。Java8中，hashmap底層資料結構是基于數組和連結清單（紅黑樹 ）來實作的，它之是以有相當快的查詢速度主要是因為它是通過計算散列碼來決定存儲的位置。通過key值計算hash碼值，将其傳遞進數組，若hash碼值沖突則采用連結清單連接配接，若該hashmap容量大于64且該連結清單長度大于8則将該連結清單轉化為紅黑樹，若連結清單長度減少到6時候，則将紅黑樹轉化回連結清單。
紅黑樹的特征：
- 每個節點非紅即黑
- 根節點是黑的
- 每個葉節點(葉節點即樹尾端NULL指針或NULL節點)都是黑的
- 如果一個節點是紅的,那麼它的兩兒子都是黑的
- 對于任意節點而言，其到葉子點樹NULL指針的每條路徑都包含相同數目的黑節點
- 高度始終保持在h = logn紅黑樹的查找、插入、删除的時間複雜度最壞為O(log n)
同樣的通過旋轉保證平衡的操作參見專欄 https://www.bilibili.com/read/cv8748171。
為什麼檔案系統和資料庫常使用B樹及其變體B+樹存儲資料索引呢？
紅黑樹每個節點最多隻有兩個子節點，而B樹，B+樹是多路查找樹，分支多則層數變少。檔案系統和資料庫的索引都是存放在磁盤上。磁盤IO次數與樹的深度相同，由于磁盤特殊的結構，磁盤的存取速度往往是主存的幾百分之一，是以為了提高效率，要盡量減少磁盤I/O，即降低樹的深度。故而不使用紅黑樹。
那可否設計為無限多路樹，即退化為有序數組？
檔案系統和資料庫的索引都是存在硬碟上的，并且如果資料量大的話，不一定能一次性加載到記憶體中。B+樹的多路存儲允許每次加載B+樹的一個結點，而後一步步往下找。
1.4 B樹和B+樹
B樹和B+樹的典型結構如下圖所示，關于其特性可以參考部落格 https://blog.csdn.net/herr_kun/article/details/80550652：
B樹
B+ 樹
這裡讨論的是，為什麼使用B+樹資料結構存儲索引（幫助MySQL高效擷取資料的資料結構）？
- 磁盤讀寫代價更低 B+樹的内部結點并沒有指向關鍵字（root中的5，28，65）具體資訊的指針。是以其内部結點相對于B樹更小。如果把所有同一内部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。一次性讀入記憶體中需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。
- 周遊資料更加友善 多數時候需要從資料庫中select多條資料，好比按照id進行排序後選100條。若是是多條的話，B樹須要作局部的中序周遊，可能要跨層通路。而B+樹因為全部資料都在葉子結點不用跨層，同時因為有連結清單結構，隻須要找到首尾，經過連結清單橫向周遊即可。為了提高效率，要盡量減少磁盤I/O。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使隻需要一個位元組，磁盤也會從這個位置開始，順序向後讀取一定長度的資料放入記憶體（不需要尋道時間，隻需很少的旋轉時間）。這樣做的理論依據是計算機科學中著名的局部性原理：當一個資料被用到時，其附近的資料也通常會馬上被使用。
- 查詢效率更加穩定 非終結點并不是最終指向檔案内容的結點，而隻是葉子結點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當
2. B+樹索引
B+樹索引在資料庫中有一個特點是高扇出（指該子產品直接調用的下級子產品的個數）性，B+樹的高度一般都在2~4層，即查詢某一鍵值的行記錄時最多隻需要2到4次IO，查詢時間在0.02~0.04秒。B+樹索引可以分為聚集索引和輔助索引。
2.1 聚集索引
InnoDB存儲引擎是索引組織表，即表中資料按照主鍵順序存放。聚集索引（clustered index）就是按照每張表的主鍵構造一棵B+樹，同時葉子節點中存放的即為整張表的行記錄資料，也将聚集索引的葉子節點稱為資料頁。
資料頁上存放的是完整的每行的記錄，而在非資料頁的索引頁中，存放的僅僅是鍵值及指向資料頁的偏移量。聚集索引的存儲并不是實體上連續的，而是邏輯上連續的。
聚集索引對于主鍵的排序查找和範圍查找速度非常快。如果查找主鍵某一範圍内的資料，通過葉子節點的上層中間節點就可以找到頁的範圍，之後直接讀取資料頁即可。
2.2 輔助索引
對于輔助索引（secondary index），葉子節點并不包含行記錄的全部資料。葉子節點除了包含鍵值以外，每個葉子節點中的索引行中還包含了一個書簽（bookmark，相應行資料的聚集索引鍵）。該書簽用來告訴InnoDB存儲引擎哪裡可以找到與索引相對應的行資料。 當通過輔助索引來尋找資料時，InnoDB存儲引擎會周遊輔助索引并通過葉級别的指針獲得指向主鍵索引的主鍵，然後再通過主鍵索引來找到一個完整的行記錄。
2.3 索引的建立與删除
2.4 Fast Index Creation
MySQL資料庫對主鍵的添加和删除過程為：
- 首先建立一張新的臨時表，表結構通過指令ALTER TABLE新定義的結構
- 然後把原表中資料導入到臨時表
- 接着删除原表
- 最後把臨時表重命名為原來的表名
對于輔助索引的建立，InnoDB存儲引擎會對建立索引的表加上一個S鎖。在建立過程中，不需要重建表，故而速度更快。删除輔助索引時，InnoDB存儲引擎隻需要更新内部視圖，并将輔助索引的空間标記為可用，同時删除MySQL資料庫内部視圖上對該表的索引定義即可。
3. Cardinality 值
如果某個字段的取值範圍很廣，幾乎沒有重複，既屬于高選擇性，最适合用于B+樹索引。Cardinality值表示索引中不重複記錄數量的預估值。Cardinality/n_rows_in_table應盡可能接近1.
4. B+樹索引的使用
4.1 聯合索引
聯合索引對表上的多個列進行索引。聯合索引也是一顆B+樹。
對于查詢SELECT * FROM TABLE WHERE a=xxx and b=xxx/ SELECT * FROM TABLE WHERE a=xxx ORDER BY b 可以使用（a,b）聯合索引。
對于查詢SELECT * FROM TABLE WHERE a=xxx，也可以使用聯合索引。
但是對于SELECT * FROM TABLE WHERE b=xxx，不能使用聯合索引，因為b列不是排好序的。
4.2 覆寫索引
InnoDB存儲引擎支援覆寫索引，即從輔助索引中就可以得到查詢的記錄，而不需要查詢聚集索引中的記錄。使用覆寫索引的一個好處是輔助索引不包含整行記錄的所有資訊，故其大小要遠小于聚集索引，是以可以減少大量的IO操作。
對于InnoDB存儲引擎的輔助索引，由于其包含了主鍵資訊，是以其葉子節點存放的資料為（primary key1, primary key2, ..., key 1, key2, ...）例如，下面語句可使用一次覆寫索引完成：
SELECT key2 FROM table WHERE key1 = xxx
SELECT primary key2, key2 FROM table WHERE key1=xxx
SELECT primary key1, key2 FROM table WHERE key1=xxx
SELECT primary key1, primary key2, key2 FROM table WHERE key1=xxx
4.3 優化器選擇不使用索引的情況
在某些情況下，當執行EXPLAIN指令進行SQL語句分析時，會發現優化器并沒有選擇索引去查找資料，而是通過掃描聚集索引，也即是直接進行全表掃描來得到資料。這種情況多發生于範圍查找、JOIN連結操作等情況。例如：
SELECT * FROM orderdetails WHERE orderid>10000 and orderid<102000;
上述掃描可以通過orderid輔助索引來進行掃描，但是實際優化器使用聚集索引進行掃描。
這時因為使用者選取的資料是整行資訊，而OderID索引查詢到指定資料，還需要進行一次書簽通路來查找整行資料資訊。雖然OderID索引中資料是順序存放的，但是再進行一次書簽查找的資料則是無序的，即磁盤上的離散讀操作。如果要求通路的資料量很小，則優化器還是會選擇輔助索引，但是當通路的資料占整個表中資料超過20%左右，優化器會選擇聚集索引來查找資料。但是若使用的磁盤是固态硬碟，随機讀操作很快，可以通過使用FORCE INDEX來強制使用某個索引：
SELECT * FROM orderdetails FORCE INDEX（OrderID）WHERE orderid>10000 and orderid<102000;
4.4 索引提示
MySQL資料庫支援索引提示，顯式地告訴優化器使用哪個索引，有兩種情況可能用到INDEX HINT：
- MySQL資料庫地優化器錯誤的選擇了某個索引，導緻查詢很慢。這種情況較為少見，大多數時候優化器工作的非常有效
- 某SQL語句可以選擇的索引非常多，這時優化器進行各個執行路徑地成本分析開銷可能會大于SQL語句本身。DBA或開發人員分析最優的索引選擇，然後通過FORCE INDEX來強制優化器按指定索引完成查詢
4.5 Multi-Range Read優化
MRR地好處：
- MRR使資料通路變得較為順序。在查詢輔助索引時，首先根據得到的查詢結果，按照主鍵進行排序，并按照主鍵排序地順序進行書簽查找
- 減少緩沖池中頁被替換地次數
- 批量處理對鍵值的查詢操作
對于InnoDB和MyISAM存儲引擎的範圍查詢和JOIN查詢操作，MRR工作方式為：
- 将查詢得到的輔助索引鍵值存放于一個緩存中，這時緩存中的資料根據輔助索引鍵值排序的
- 将緩存中的鍵值根據RowID進行排序
- 根據RowID的排序順序來通路實際地資料檔案
此外，MRR還可以将某些範圍查詢，拆分為鍵值對，以此來進行批量的資料查詢。例如：SELECT * FROM t WHERE key_part1 >= 1000 AND key_part1<2000 AND key_part2 = 10000.
若沒有MRR，此時查詢類型為range，SQL優化器會先将key_part1大于1000且小于2000的資料都取出，然後再按key_part2的條件進行過濾。
若啟用了MRR優化，優化器會先将查詢條件進行拆分（（1000，1000），（1001,1000）（1002,1000）...（1999,1000）），然後再進行資料查詢。
4.6 Index Condition Pushdown (ICP) 優化
在進行索引查詢時，首先根據索引查找記錄，然後判斷是否可以進行WHERE條件的過濾，也就是将WHERE的部分過濾操作放在了存儲引擎層。在某些查詢下，可以大大減少上層SQL層對記錄的索取，進而提高資料庫的整體性能。
ICP優化支援range，ref, eq_ref, ref_or_null類型的查詢，當優化器選擇ICP優化時，可在執行計劃的列Extra看到Using Index Condition提示。
5. hash索引
hash索引進行字典類型的資料查詢（SELECT * FROM TABLE WHERE index_col='xxx'）的時間複雜度為O（1）。但是對于範圍查找卻無能為力。
6. 全文檢索
6.1 概述
下面的SQL語句可以查詢部落格内容以xxx開頭的文章，并且隻要content添加了B+樹索引，就能利用索引進行快速查詢。
SELECT * FROM blog WHERE content like 'xxx%'
然而，更多的時候，使用者需要查詢的是部落格内容包含單詞xxx的文章，即：
SELECT * FROM blog WHERE content like '%xxx%'
全文檢索（full-text search）是将存儲于資料庫中的整本書或整篇文章中的任意内容資訊查找出來的技術。它可以根據需要獲得全文中有關章、節、段、句、詞等資訊，也可以進行各種統計和分析。
6.2 反向索引
反向索引也是一種索引結構。它在輔助表中存儲了單詞與單詞自身在一個或多個文檔中所在位置之間的映射。有兩種表現形式：
- inverted file index {單詞，單詞所在文檔ID}
- full inverted index {單詞，（單詞所在文檔的ID，在文檔中的位置）}
6.3 InnoDB 全文檢索
在InnoDB存儲引擎中，将（documentid， position）視為一個ilist。是以，在全文檢索的表中，有兩個列，一個是Word段，一個是ilist段，這個表稱為Auxiliary Table（輔助表），存放于磁盤上。FTS Index Cache（全文檢索索引緩存）是一個紅黑樹結構，用來提高全文檢索的性能。參數innodb_ft_cache_size用來控制FTS Index Cache的大小，預設值是32M。當該緩存滿時，會将其中的（word，ilist）分詞資訊同步到磁盤的Auxiliary Table中。增大該參數可以提高全文檢索的性能，但是在當機時，未同步到磁盤中的索引資訊需要更多時間來回複。
stopword清單表示該清單中的Word不需要對其進行索引分詞操作，例如單詞the。
InnoDB 全文檢索存在以下限制：
- 每張表隻能有一個全文檢索的索引
- 由多列組合而成的全文檢索的索引列必須使用相同的字元集與排序規則
- 不支援沒有單詞界定符的語言，如中文，日語，韓語等
6.4 全文檢索
文法為：
正負表示這個單詞一定出現或者一定不存在。