第五章索引與演算法（學習筆記）-有解無憂

　　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 全文檢索存在以下限制：