[TOC] ## InnoDB存儲引擎索引概述 InnoDB 存儲引擎索引有 (1)B+ 樹索引 (2)全文索引 (3)哈希索引 ### B+樹 B+樹和二叉樹、平衡二叉樹一樣，都是經典的數據結構。B+樹由B樹和索引順序訪問方法（ISAM，是不是很熟悉？對，這也是MyISAM引擎最初參考的數據結構）演化而來，但是在實際使用過程中幾乎已經沒有使用B樹的情況了。 B+樹的定義十分復雜，因此只簡要地介紹B+樹：B+樹是為磁盤或其他直接存取輔助設備而設計的一種平衡查找樹，在B+樹中，所有記錄節點都是按鍵值的大小順序存放在同一層的葉節點中，各葉節點指針進行連接。  我們先來看一個B+樹，其高度為2，每頁可存放4條記錄，扇出（fan out）為5。 可以看出，所有記錄都在葉節點中，并且是順序存放的，如果我們從最左邊的葉節點開始順序遍歷，可以得到所有鍵值的順序排序：5、10、15、20、25、30、50、55、60、65、75、80、85、90。 B+樹的插入操作 B+樹的插入必須保證插入后葉節點中的記錄依然排序，同時需要考慮插入B+樹的三種情況，每種情況都可能會導致不同的插入算法，如表5-1所示。  我們用實例來分析B+樹的插入，我們插入28這個鍵值，發現當前Leaf Page和Index Page都沒有滿，我們直接插入就可以了。  這次我們再插入一條70這個鍵值，這時原先的Leaf Page已經滿了，但是Index Page還沒有滿，符合表5-1的第二種情況，這時插入Leaf Page后的情況為50、55、60、65、70。我們根據中間的值60拆分葉節點。  因為圖片顯示的關系，這次我沒有能在各葉節點加上雙向鏈表指針。最后我們來插入記錄95，這時符合表5-1討論的第三種情況，即Leaf Page和Index Page都滿了，這時需要做兩次拆分。  可以看到，不管怎么變化，B+樹總是會保持平衡。但是為了保持平衡，對于新插入的鍵值可能需要做大量的拆分頁（split）操作，而B+樹主要用于磁盤，因此頁的拆分意味著磁盤的操作，應該在可能的情況下盡量減少頁的拆分。因此，B+樹提供了旋轉（rotation）的功能。 旋轉發生在Leaf Page已經滿了、但是其左右兄弟節點沒有滿的情況下。這時B+樹并不會急于去做拆分頁的操作，而是將記錄移到所在頁的兄弟節點上。通常情況下，左兄弟被首先檢查用來做旋轉操作，這時我們插入鍵值70，其實B+樹并不會急于去拆分葉節點，而是做旋轉，50，55，55旋轉。  可以看到，采用旋轉操作使B+樹減少了一次頁的拆分操作，而這時B+樹的高度依然還是2。 B+樹的刪除操作 B+樹使用填充因子（fill factor）來控制樹的刪除變化，50%是填充因子可設的最小值。B+樹的刪除操作同樣必須保證刪除后葉節點中的記錄依然排序，同插入一樣，B+樹的刪除操作同樣需要考慮如表5-2所示的三種情況，與插入不同的是，刪除根據填充因子的變化來衡量。  首先，刪除鍵值為70的這條記錄，該記錄符合表5-2討論的第一種情況，刪除后。  接著我們刪除鍵值為25的記錄，這也是表5-2討論的第一種情況，但是該值還是Index Page中的值，因此在刪除Leaf Page中25的值后，還應將25的右兄弟節點的28更新到Page Index中，最后可得到圖。  最后我們來看刪除鍵值為60的情況，刪除Leaf Page中鍵值為60的記錄后，填充因子小于50%，這時需要做合并操作，同樣，在刪除Index Page中相關記錄后需要做Index Page的合并操作，最后得到圖。  ---- ## InnoDB的B+樹索引 B+樹索引其本質就是B+樹在數據庫中的實現，但是B+索引在數據庫中有一個特點就是其高扇出性，因此在數據庫中，B+樹的高度一般都在2～3層，也就是對于查找某一鍵值的行記錄，最多只需要2到3次IO，這倒不錯。因為我們知道現在一般的磁盤每秒至少可以做100次IO，2～3次的IO意味著查詢時間只需0.02～0.03秒。 數據庫中的B+樹索引可以分為聚集索引（clustered index）和輔助聚集索引（secondary index）輔助聚集索引有時也稱非聚集索引（non-clustered index）。 但是不管是聚集還是非聚集的索引，其內部都是B+樹的，即高度平衡的，葉節點存放著所有的數據。聚集索引與非聚集索引不同的是，葉節點存放的是否是一整行的信息。 ### 聚集索引 InnoDB存儲引擎表是索引組織表，即表中數據按照主鍵順序存放。而聚集索引就是按照每張表的主鍵構造一顆B+樹，并且葉節點中存放著整張表的行記錄數據，因此也讓聚集索引的葉節點成為數據頁。聚集索引的這個特性決定了索引組織表中數據也是索引的一部分。同B+樹數據結構一樣，每個數據頁都通過一個雙向鏈表來進行鏈接。 由于實際的數據頁只能按照一顆B+樹進行排序，因此每張表只能擁有一個聚集索引。在許多情況下，查詢優化器非常傾向于采用聚集索引，因為聚集索引能夠讓我們在索引的葉節點上直接找到數據。此外，由于定義了數據的邏輯順序，聚集索引能夠特別快地訪問針對范圍值的查詢。查詢優化器能夠快速發現某一段范圍的數據頁需要掃描。 現在我們來看一張表，我們以人為的方式讓其每個頁只能存放兩個行記錄，如： ~~~~ MySQL [qiushibaike]> create table t( -> a int not null, -> b varchar(8000), -> c int not null, -> primary key (a), -> key idx_c(c) -> )engine=INNODB; ~~~~ ~~~~ insert into t select 1,repeat('a',7000),-1; insert into t select 2,repeat('a',7000),-2; insert into t select 3,repeat('a',7000),-3; insert into t select 4,repeat('a',7000),-4; ~~~~ 可以看到，我們表的定義和插入方式使得目前每個頁只能存放兩個行記錄，我們用py_innodb_page_info工具來分析表空間，可得：py_innodb_page_info.py-v mytest/t.ibd page level為0000的即是數據頁。我們要分析的是page level為0001的頁，該頁是B+樹的根，我們來看看索引的根頁中存放的數據。 我們直接通過頁尾的Page Directory來分析，從00 63可以知道該頁中行開始的位置。接著通過Recorder Header來分析，0xc063開始的值為69 6e 66 69 6d 75 6d 00，就代表infimum偽行記錄。之前的5個字節01 00 02 00 1b就是Recorder Header，分析第4位到第8位的值1代表該行記錄中只有一個記錄（需要記住的是，InnoDB的Page Directory是稀疏的），即infimum記錄本身。我們通過Recorder Header中最后的兩個字節00 1b來判斷下一條記錄的位置，即c063+1b=c073，讀取鍵值可得80 01，就是主鍵為1的鍵值（我們制定的INT是無符號的，因此二進制是0x8001，而不是0x0001），80 01后值00 00 00 04代表指向數據頁的頁號。以同樣的方式，可以找到80 02和80 04這兩個鍵值以及它們指向的數據頁。 通過以上對于非數據頁節點的分析，我們發現數據頁上存放的是完整的行記錄，而在非數據頁的索引頁中，存放的僅僅是鍵值以及指向數據頁的偏移量，而不是一個完整的行記錄。因此我們構造的這顆二叉樹大致如圖5-14所示。  許多數據庫的文檔會這樣告訴讀者：聚集索引按照順序物理地存儲數據。但是試想，如果聚集索引必須按照特定順序存放物理記錄的話，則維護成本即顯得非常之高了。所以，聚集索引的存儲并不是物理上的連續，相反是邏輯上連續的。這其中有兩點：一是我們前面說過的頁通過雙向鏈表鏈接，頁按照主鍵的順序排列。另一點是每個頁中的記錄也是通過雙向鏈表進行維護，物理存儲上可以同樣不按照主鍵存儲。 聚集索引的另一個好處是，它對于主鍵的排序查找和范圍查找速度非常快。葉節點的數據就是我們要查詢的數據，如我們要查詢一張注冊用戶的表，查詢最后注冊的10位用戶，由于B+樹索引是雙向鏈表的，我們可以快速找到最后一個數據頁，并取出10條記錄，我們用Explain進行分析，可得： `explain select * from Profile order by id limit 10;` 另一個是范圍查詢（range query），如果要查找主鍵某一范圍內的數據，通過葉節點的上層中間節點就可以得到頁的范圍，之后直接讀取數據頁即可，又如： `explain select * from Profile where id＞10 and id＜10000;` Explain得到了MySQL的執行計劃（execute plan），并且rows列給出了一個查詢結果的預估返回行數。要注意的是，rows代表的是一個預估值，不是確切的值，如果我們實際進行這句SQL的查詢，可以看到實際上只有9 946行記錄： `select count(*) from Profile where id＞10 and id＜10000; ` ### 輔助索引 對于輔助索引（也稱非聚集索引），葉級別不包含行的全部數據。葉節點除了包含鍵值以外，每個葉級別中的索引行中還包含了一個書簽（bookmark），該書簽用來告訴InnoDB存儲引擎，哪里可以找到與索引相對應的行數據。因為InnoDB存儲引擎表是索引組織表，因此InnoDB存儲引擎的輔助索引的書簽就是相應行數據的聚集索引鍵。顯示了InnoDB存儲引擎中輔助索引與聚集索引的關系。  輔助索引的存在并不影響數據在聚集索引中的組織，因此每張表上可以有多個輔助索引。當通過輔助索引來尋找數據時，InnoDB存儲引擎會遍歷輔助索引并通過葉級別的指針獲得指向主鍵索引的主鍵，然后再通過主鍵索引來找到一個完整的行記錄。舉例來說，如果在一顆高度為3的輔助索引樹中查找數據，那么需要對這顆輔助索引遍歷3次找到指定主鍵；如果聚集索引樹的高度同樣為3，那么還需要對聚集索引進行3次查找，才能最終找到一個完整的行數據所在的頁，因此一共需要6次邏輯IO來訪問最終的一個數據頁。 對于其他的一些數據庫，如Microsoft SQL Server數據庫，其表類型有一種不是索引組織表，稱為堆表。在數據的存放按插入順序方面，與MySQL的MyISAM存儲引擎有些類似。堆表的特性決定了堆表上的索引都是非聚集的，但是堆表沒有主鍵。因此這時書簽是一個行標識符（row identifier，RID），可以用如“文件號：頁號：槽號”的格式來定位實際的行。 堆表的非聚集索引既然不需要再通過主鍵對聚集索引進行查找，那不是速度會更快嗎？答案是也許，在某些只讀的情況下，書簽為行標識符方式的非聚集索引可能會比書簽為主鍵方式的非聚集索引快。但是考慮在OLTP（OnLine Transaction Processing，在線事務處理）應用的情況下，表可能還需要發生插入、更新、刪除等DML操作。當進行這類操作時，書簽為行標識符方式的非聚集索引可能需要不斷更新行標識符所指向數據頁的位置，這時的開銷可能就會大于書簽為主鍵方式的非聚集索引了。 Microsoft SQL Server數據庫DBA問過這樣的問題，為什么在SQL Server上還要使用索引組織表？堆表的書簽性使得非聚集查找可以比主鍵書簽方式更快，并且非聚集可能在一張表中存在多個，我們需要對多個非聚集索引的查找。而且對于非聚集索引的離散讀取，索引組織表上的非聚集索引會比堆表上的聚集索引慢一些。當然，在一些情況下，使用堆表的確會比索引組織表更快，但是我覺得大部分是由于存在于OLAP（On-Line Analytical Processing，在線分析處理）的應用。其次就是前面提到的，表中數據是否需要更新，并且更新會否影響到物理地址的變更。此外另一個不能忽視的是對于排序和范圍查找，索引組織表可以通過B+樹的中間節點就找到要查找的所有頁，然后進行讀取，而堆表的特性決定了這對其是不能實現的。最后，非聚集索引的離散讀，的確是存在上述情況，但是一般的數據庫都通過實現預讀（read ahead）技術來避免多次的離散讀操作。因此，具體是建堆表還是索引組織表，這取決于你的應用，不存在哪個更優的情況。這和InnoDB存儲引擎好還是MyISAM存儲引擎好的問題是一樣的，具體情況具體分析。 接下來，我們通過閱讀表空間文件來分析InnoDB存儲引擎的非聚集索引，我們還是分析上一小節所用的表t。 不同的是，在表t上再建立一個列c，并對列c創建非聚集索引： ~~~~ alter table t add c int not null; update t set c=0-a; alter table t add key idx_c(c); show index from t; select a,c from t; ~~~~ 然后用py_innodb_page_info工具來分析表空間，可得：py_innodb_page_info.py-v t.ibd 對比前一次我們的分析，可以看到這次多了一個頁。分析page offset為4的頁，該頁為非聚集索引所在頁，通過工具hexdump分析可得： 因為只有4行數據，并且列c只有4個字節，因此在一個非聚集索引頁中即可完成，整理分析可得下圖所示的關系：  顯示了表t中輔助索引idx_c和聚集索引的關系。可以看到輔助索引的葉節點中包含了列c的值和主鍵的值。這里鍵值因為我特意設為負值，你會發現-1以7f ff ff ff的方式進行內部存儲。7（0111）最高位為0，代表負值，實際的值應該取反后，加1，即得-1。 ### B+樹索引的管理 索引的創建和刪除可以通過兩種方法，一種是ALTER TABLE，另一種是CREATE/DROP INDEX。ALTER TABLE創建索引的語法為： ~~~~ ALTER TABLE tbl_name |ADD{INDEX|KEY}[index_name] [index_type] (index_col_name，……) [index_option]…… ALTER TABLE tbl_name DROP PRIMARY KEY |DROP {INDEX|KEY} index_name CREATE/DROP INDEX的語法同樣很簡單： CREATE [UNIQUE] INDEX index_name [index_type] ON tbl_name（index_col_name，……） DROP INDEX index_name ON tbl_name ~~~~ 索引可以索引整個列的數據，也可以只索引一個列的開頭部分數據，如前面我們創建的表t，b列為varchar(8000)，但是我們可以只索引前100個字段，如： `alter table t add key idx_b (b(100));` 目前MySQL數據庫存在的一個普遍問題是，所有對于索引的添加或者刪除操作，MySQL數據庫是先創建一張新的臨時表，然后把數據導入臨時表，刪除原表，再把臨時表重名為原來的表名。因此對于一張大表，添加和刪除索引需要很長的時間。對于從Microsoft SQL Server或Oracle數據庫的DBA來說，MySQL數據庫的索引維護始終讓他們非常苦惱。 InnoDB存儲引擎從版本InnoDB Plugin開始，支持一種稱為快速索引創建方法。當然這種方法只限定于輔助索引，對于主鍵的創建和刪除還是需要重建一張表。對于輔助索引的創建，InnoDB存儲引擎會對表加上一個S鎖。在創建的過程中，不需要重建表，因此速度極快。但是在創建的過程中，由于上了S鎖，因此創建的過程中該表只能進行讀操作。刪除輔助索引操作就更簡單了，只需在InnoDB存儲引擎的內部視圖更新下，將輔助索引的空間標記為可用，并刪除MySQL內部視圖上對于該表的索引定義即可。 查看表中索引的信息可以使用SHOW INDEX語句。如我們來分析表t，之前先加一個聯合索引，可得： `alter table t add key idx_a_b(a,c);` `show index from t;`  因為在表t上有3個索引：一個主鍵索引，c列上的索引，和b列前100個字節構成的索引。 接著我們來具體講解每個列的含義： **Table**：索引所在的表名。 **Non_unique**：非唯一的索引，可以看到primary key是0，因為必須是唯一的。 **Key_name**：索引的名稱，我們可以通過這個名稱來DROP INDEX。 **Seq_in_index**：索引中該列的位置，如果看聯合索引idx_a_b就比較直觀了。 **Column_name**：索引的列 **Collation**：列以什么方式存儲在索引中。可以是'A'或者NULL。B+樹索引總是A，即排序的。如果使用了Heap存儲引擎，并且建立了Hash索引，這里就會顯示NULL了。因為Hash根據Hash桶來存放索引數據，而不是對數據進行排序。 **Cardinality**：非常關鍵的值，表示索引中唯一值的數目的估計值。Cardinality/表的行數應盡可能接近1，如果非常小，那么需要考慮是否還需要建這個索引。 **Sub_part**：是否是列的部分被索引。如果看idx_b這個索引，這里顯示100，表示我們只索引b列的前100個字符。如果索引整個列，則該字段為NULL。 **Packed**：關鍵字如何被壓縮。如果沒有被壓縮，則為NULL。 **Null**：是否索引的列含有NULL值。可以看到idx_b這里為Yes。因為我們定義的b列允許NULL值。 **Index_type**：索引的類型。InnoDB存儲引擎只支持B+樹索引，所以這里顯示的都是BTREE。 **Comment**：注釋。 **Cardinality**值非常關鍵，優化器會根據這個值來判斷是否使用這個索引。但是這個值并不是實時更新的，并非每次索引的更新都會更新該值，因為這樣代價太大了。因此這個值是不太準確的，只是一個大概的值。上面顯示的結果主鍵的Cardinality為2，但是很顯然我們表中有4條記錄，這個值應該是4。如果需要更新索引Cardinality的信息，可以使用ANALYZE TABLE命令。如： **`analyze table t;`** **`show index from t;`** 這時的Cardinality的值就對了。不過，在每個系統上可能得到的結果不一樣，因為ANALYZE TABLE現在還存在一些問題，可能會影響得到最后的結果。 另一個問題是MySQL數據庫對于Cardinality計數的問題，在運行一段時間后，可能會看到下面的結果： `show index from Profile;` Cardinality為NULL，在某些情況下可能會發生索引建立了、但是沒有用到，或者explain兩條基本一樣的語句，但是最終出來的結果不一樣。一個使用索引，另外一個使用全表掃描，這時最好的解決辦法就是做一次ANALYZE TABLE的操作。因此我建議在一個非高峰時間，對應用程序下的幾張核心表做ANALYZE TABLE操作，這能使優化器和索引更好地為你工作。 **** ## Cardinality值 ### 什么是Cardinality值 不是所有的查詢條件出現的列都需要添加索引。對于什么時候添加B+樹索引。一般的經驗是，在訪問表中很少一部分時使用B+樹索引才有意義。對于性別字段、地區字段、類型字段，他們可取值范圍很小，稱為低選擇性。如 SELECT * FROM student WHERE sex='M' 按性別進行查詢時，可取值一般只有M、F。因此SQL語句得到的結果可能是該表50%的數據(加入男女比例1:1)這時添加B+樹索引是完全沒有必要的。相反，如果某個字段的取值范圍很廣，幾乎沒有重復，屬于高選擇性。則此時使用B+樹的索引是最合適的。例如對于姓名字段，基本上在一個應用中不允許重名的出現 怎樣查看索引是否有高選擇性？通過SHOW INDEX結果中的列Cardinality來觀察。非常關鍵，表示所以中不重復記錄的預估值，需要注意的是Cardinality是一個預估值，而不是一個準確值基本上用戶也不可能得到一個準確的值，在實際應用中，Cardinality/n_row_in_table應盡可能的接近1，如果非常小,那用戶需要考慮是否還有必要創建這個索引。故在訪問高選擇性屬性的字段并從表中取出很少一部分數據時，對于字段添加B+樹索引是非常有必要的。如 SELECT * FROM member WHERE usernick='David'; 表member大約有500W行數據,usernick字段上有一個唯一索引。這是如果查找用戶名為David的用戶，將得到如下執行計劃  可以看到使用了usernick這個索引。這也符合之前提到的高可選擇性，即SQL語句取表中較少行的原則 ### InnoDB存儲引擎的Cardinality統計 建立索引的前提是高選擇性。這對數據庫來說才具有實際意義，那么數據庫是怎樣統計Cardinality的信息呢?因為MySQL數據庫中有各種不同的存儲引擎，而每種存儲引擎對于B+樹索引的實現又各不相同。所以對Cardinality統計時放在存儲引擎層進行的 在生成環境中，索引的更新操作可能非常頻繁。如果每次索引在發生操作時就對其進行Cardinality統計，那么將會對數據庫帶來很大的負擔。另外需要考慮的是，如果一張表的數據非常大，如一張表有50G的數據，那么統計一次Cardinality信息所需要的時間可能非常長。這樣的環境下，是不能接受的。因此，數據庫對于Cardinality信息的統計都是通過采樣的方法完成 在InnoDB存儲引擎中，Cardinality統計信息的更新發生在兩個操作中：insert和update。InnoDB存儲引擎內部對更新Cardinality信息的策略為: ***表中1/16的數據已發生了改變*** ***stat_modified_counter>2000 000 000*** 第一種策略為自從上次統計Cardinality信息后，表中的1/16的數據已經發生過變化，這是需要更新Cardinality信息 第二種情況考慮的是，如果對表中某一行數據頻繁地進行更新操作，這時表中的數據實際并沒有增加，實際發生變化的還是這一行數據，則第一種更新策略就無法適用這種情況，故在InnoDB存儲引擎內部有一個計數器start_modified_counter,用來表示發生變化的次數,當start_modified_counter>2 000 000 000 時，則同樣更新Cardinality信息 接著考慮InnoDB存儲引擎內部是怎樣進行Cardinality信息統計和更新操作呢？同樣是通過采樣的方法。默認的InnoDB存儲引擎對8個葉子節點Leaf Page進行采用。采用過程如下 取得B+樹索引中葉子節點的數量，記為A 隨機取得B+樹索引中的8個葉子節點，統計每個頁不同記錄的個數，即為P1，P2....P8 通過采樣信息給出Cardinality的預估值: **Cardinality=(P1+P2+...+P8)\*A/8** 根據上述的說明可以發現，在InnoDB存儲引擎中，Cardinality值通過對8個葉子節點預估而得的。而不是一個實際精確的值。再者，每次對Cardinality值的統計，都是通過隨機取8個葉子節點得到的，這同時有暗示了另外一個Cardinality現象，即每次得到的Cardinality值可能不同的，如 `SHOW INDEX FROM OrderDetails` 上述SQL語句會觸發MySQL數據庫對于Cardinality值的統計，第一次運行得到的結果如圖5-20  在上述測試過程中，并沒有通過INSERT、UPDATE這類的操作來改變OrderDetails中的內容，但是當第二次運行SHOW INDEX FROM OrderDetails語句是，發生了變化，如圖5-21  可以看到，當第二次運行SHOW INDEX FROM OrderDetails語句時，表OrderDetails索引中的Cardinality值發生了變化，雖然表OrderDetails本身并沒有發生任何變化，但是由于Cardinality是隨機取8個葉子節點進行分析，所以即使表沒有發生變化，用戶觀察到索引Cardinality值還是會發生變化，這本身不是Bug,而是隨機采樣而導致的結果 當然，有一種情況可以使得用戶每次觀察到的索引Cardinality值是一樣的。那就是表足夠小，表的葉子節點樹小于或者等于8個。這時即使隨機采樣，也總是會采取倒這些頁，因此每次得到的Cardinality值是相同的 在InnoDB1.2版本之前，可以通過innodb_stats_sample_pages用來設置統計Cardinality時每次采樣頁的數量，默認為8.同時，參數innodb_stats_method用來判斷如何對待索引中出現NULL值記錄。該參數默認值為nulls_equal,表示將NULL值記錄為相等的記錄。其有效值還nulls_unequal,nulls_ignored,分別表示將NULL值記錄視為不同的記錄和忽略NULL值記錄。例如某夜中索引記錄為NULL、NULL、1、2、2、3、3、3,在參數innodb_stats_method默認設置下，該頁的Cardinality為4；若參數innodb_stats_method為nulls_unequal,則該頁的Cardinality為5，若參數innodb_stats_method為nulls_ignored，則Cardinality值為3 當執行ANALYZE TABLE、SHOW TABLE STATUS、SHOW INDEX 以及訪問INFORMATION_SCHEMA架構下的表TABLES和STATISTICS時會導致InnoDB存儲引擎會重新計算索引Cardinality值，若表中的數據量非常大，并且表中存在多個輔助索引時，執行上述操作可能會非常慢，雖然用戶可能并不希望去更新Cardinality值 InnoDB1.2版本提供了更多參數對Cardinality進行設置。如表  ***** ## B+樹索引的使用 并不是在所有的查詢條件下出現的列都需要添加索引。對于什么時候添加B+樹索引，我的經驗是訪問表中很少一部分行時，使用B+樹索引才有意義。對于性別字段、地區字段、類型字段，它們可取值的范圍很小，即低選擇性。 對于性別，可取值的范圍只有'M'、'F'。對上述SQL語句得到的結果可能是該表50%的數據（我們假設男女比例1：1），這時添加B+樹索引是完全沒有必要的。相反，如果某個字段的取值范圍很廣，幾乎沒有重復，即高選擇性，則此時使用B+樹索引是最適合的，例如姓名字段，基本上在一個應用中都不允許重名的出現。 因此，當訪問高選擇性字段并從表中取出很少一部分行時，對這個字段添加B+樹索引是非常有必要的。但是如果出現了訪問字段是高選擇性的，但是取出的行數據占表中大部分的數據時，這時MySQL數據庫就不會使用B+樹索引了。 ## 聯合索引 聯合索引 運用的是多個索引列。 創建方法跟單個索引一樣。 這么做的好處就是 第一：是使用了B+樹索引  第二：已經對第二個鍵值進行排序了 **注意：但是對于單個列查詢是不引起聯合索引。** 關聯查詢的查詢語句: select * from 表名 where id = *** and user= *** ~~~~ create table buy_log( userid int unsigned not null, buy_date date )engine=InnoDB; insert into buy_log values(1,'2009-01-01'); insert into buy_log values(2,'2009-01-01'); insert into buy_log values(3,'2009-01-01'); insert into buy_log values(1,'2009-02-01'); insert into buy_log values(3,'2009-02-01'); insert into buy_log values(1,'2009-03-01'); insert into buy_log values(1,'2009-04-01'); insert into buy_log values(1,'2009-05-01'); alter table buy_log add key (userid); alter table buy_log add key (userid,buy_date); ~~~~ 只對userid查詢 `explain select * from buy_log where userid=2`  possible_keys 說明有兩個索引可以用 userid,userid_2 但是優化器選擇了userid `explain select * from buy_log where userid=1 order by buy_date limit 3`  這里運用到了兩個字段 所以優化器會選擇userid_2 因為聯合索引userid_2 已經排序好 buy_date 也可以 (a,b,c)當做聯合索引但是如: `select * from buy_log where a=*** order by c` 這個情況就運行不了聯合索引 因為c并不需要排序 ### 覆蓋索引 InnoDB在1.0之后 或者 MySQL 在5.0或者以下的不支持覆蓋索引。 就是從輔助索引中查詢的記錄，而不需要查詢聚集索引中的記錄。 好處就是輔助索引不包含整個行記錄的所有信息，骨氣大小遠小于聚集索引。因此可以減少大量的IO操作。 `explain select count(*) from buy_log;`  **Using index：表示使用索引，如果只有 Using index，說明他沒有查詢到數據表，只用索引表就完成了這個查詢，這個叫覆蓋索引。** `explain select count(*) from buy_log where buy_date >= '2011-01-01' and buy_date <'2011-02-01'`  **如果同時出現Using where，代表使用索引來查找讀取記錄， 也是可以用到索引的，但是需要查詢到數據表。** ### 優化器選擇不使用索引的情況 當執行 explain命令進行sql語句分析時,就會發現優化器并沒有選擇索引去查找數據,而是通過掃描聚集索引,也就是直接進行全表的掃描來得到的數據。 這種情況多發生與范圍查找、JOIN鏈接操作等情況下。 可以通過`show index from 表名`查詢索引  可以看出該表是有使用(OrderID,ProductID)的聯合主鍵,此外還有OrderID的單個索引. `select * from 表名 where orderid > 10000 and orderid<10200;`  選擇的是聚集索引而非輔助索引,原因是:OrderID索引不能覆蓋到我們要查詢的信息。雖然OrderID索引數據是順序存放，但是再次進行書簽查找數據是無序的，因此變為磁盤上離散讀操作。如果要求訪問的數據量小，則優化器還是會選擇輔助索引，但是數據大的時候（一般20%左右），優化器會選擇通過聚集索引來查找數據。因為順序讀比離散讀快，但是如果是固態硬盤，隨機讀猜中非常快，同時自信確定使用輔助索引可以帶來更好的性能 可以使用關鍵詞 `FORCE INDEX` 來強制使用摸個索引,如:`select * from 表名 force index(OrderID) where orderid > 10000 and orderid<10200;`  **`USE INDEX`:這個指令只是建議優化器使用這個索引 而 `FORCE INDEX` 來強制使用摸個索引** ### Multi-Range Read 優化 MySQL5.6版本開始 支持 Multi-Range Read (MRR)優化。其目的是為了減少磁盤的隨機訪問，并且將隨機訪問轉化為順序的數據訪問 這對 IO-bound類型的SQL查詢語句可帶來性能極大的提升。MRR適用于range，ref，eq_ref類型的查詢。 MRR優化有以下幾個好處： （1）MRR使數據訪問變得較為順序。在查詢輔助索引時，首先根據得到的查詢結果，按照主鍵進行排序，并按照主鍵排序的順序進行書簽查找。 （2）減少緩沖池中頁被替換的次數。 （3）批量處理對鍵值的查詢操作。 對InnoDB和MyISAM存儲引擎的范圍查詢和JOIN查詢操作MRR工作方式如下： （1）講查詢得到的輔助索引鍵值存放在一個緩存中，這時緩存重點數據是根據輔助索引鍵值排序的。 （2）將緩存中的鍵值根據RowID進行排序。 （3）根據RowID的排序順序來訪問實際的數據文件。 此外 混吃次不是足夠大，不能放下一張表中的所有數據，此時離散讀操作會導致緩存中的頁被替換出緩沖池，然后又不斷讀入換沖池。若是安裝主鍵訪問，則可以將此重復行為降為最低。 `select * from t where key_part1 >=1000 and key_part1 <2000 and key_part2 =10000` 表中 ( key_part1,key_part2)的聯合索引,因此索引根據key_part1,key_part2的位置關系排序 沒有 MRR查詢類型為Range,sql優化器會先將key_part1大于1000 且小于2000的數據都取出,即使key_part2不等于10000。取出后進行過濾。這導致無用數據被取出。 如果啟用MRR 會使其性能大大的提升。 優化器會將查詢條件拆分為（1000,10000）（1001,10000），....，（1999,10000），最后進行數據的查詢。 速度也是相差很大的。 啟動方法:optimizer_switch 中的標記(flag)來控制。 總是開啟MRR。 `SET @@optimizer_switch = 'mrr=on,mrr_cost_based=off';` read_rnd_buffer_size 用來控制鍵值的緩沖區大小,默認為256k; 查看命令: `select @@read_rnd_buffer_size\G`; ### Index Condition Pushdown( ICP )優化 需要在MySQL5.6版本支持這種根據索引進行查詢的優化方式.之前的MySQL版本不支持Index Condition Pushdown, 首先是根據索引來查找記錄,然后在根據where條件來過濾記錄。 在支持Index Condition Pushdown后，MySQL數據庫會取出索引的同時，判斷是否進行where條件的過濾，也就是將where的部分過濾操作放在存儲引擎層。在某些查詢下，可以大大減少上層SQL層對記錄的索取（fetch），從而提高數據庫的整體性能。 Index Condition Pushdown( ICP )優化支持range，ref，eq_ref，ref_or_null類型的查詢。當前支持MyISAM和InnoDB存儲引擎。  **** Extra表示附加信息，常見的有如下幾種（也按查詢效率從高到低排列）： Using index：表示使用索引，如果只有 Using index，說明他沒有查詢到數據表，只用索引表就完成了這個查詢，這個叫覆蓋索引。如果同時出現Using where，代表使用索引來查找讀取記錄， 也是可以用到索引的，但是需要查詢到數據表。 Using where：表示條件查詢，如果不讀取表的所有數據，或不是僅僅通過索引就可以獲取所有需要的數據，則會出現 Using where。如果type列是ALL或index，而沒有出現該信息，則你有可能在執行錯誤的查詢：返回所有數據。 Using filesort：不是“使用文件索引”的含義！filesort是MySQL所實現的一種排序策略，通常在使用到排序語句ORDER BY的時候，會出現該信息。 Using temporary：表示為了得到結果，使用了臨時表，這通常是出現在多表聯合查詢，結果排序的場合。 **如果EXPLAIN出現后面兩個信息（Using filesort，Using temporary），而rows又比較大，通常意味著你需要調整查詢語句，或者需要添加索引，總之需要盡量消除這兩個信息。** ## 哈希算法 ### 哈希表 哈希表 也稱為散列表,用一個數組(即直接尋址表)T[0..m-1]表示動態集合,其中每個位置(或稱槽或者桶)對應全域U中的一個關鍵字。圖說明了這個方法k指向集合中的一個關鍵字為K的元素。如果集合中沒有關鍵詞k的元素 則T[k]=NULL; 元素h（k）利用哈希函數h，根據關鍵字k計算出槽位置。函數h將關鍵詞域U映射到哈希T[0..m-1]的槽位上。但是兩個關鍵詞可能映射到同一個槽上。這種情況稱為碰撞。鏈接法解決碰撞問題。 :-:  一般使用除法散列法：哈希函數：h（k）=k mod m；  ### 哈希索引 哈希索引只能通過 等值條件查找如:`select * from 表名 where id_x=1;` 通過 `show engine innodb status\G;`  通過參數 innodb_adaptive_hash_index來禁用和啟動特性,默認為開啟。 ## 全文檢索 全文檢索(full_test search)是將存儲于數據庫中的整本書或者整篇文章中的任意內容信息查找出來的技術。它可以根據需要獲取全文中有關的章、節、段、句等信息，也可以進行各種統計和分析。 InnoDB在1.2.X開始之前支持全文檢索，其支持MyISAM存儲引擎的全部功能，并且還支持其他的一些特性。 如：`select * from 表名 where title like '中午%';` 這個語句是可以通過 B+樹索引進行查詢 如：`select * from 表名 where title like '%中午%';` 這個就不能用B+樹能夠更好的工作了 ### 倒排索引 全文檢索通常使用倒排索引（inverted index）來實現。倒排索引在輔助表（auxiliary table） 中存儲了單詞與單詞自身在一個或者多個文檔中所在位置之間的映射。利用相關數組實現，其擁有兩種表現形式： （1） inverted file index，其表現形式為{ 單詞,單詞所在的文檔的ID} （2）full inverted index,其表現形式為{ 單詞,( 單詞,單詞所在的文檔的位置)}  對 inverted file index 其僅存文檔id,而full inverted index存儲的是對(pair),即(DocumentId,Position),因此存儲的倒排索引如下圖：  full inverted index存儲了單詞所在的位置信息,但是同時也暫用了更多的空間,但是能更好的的定位數據。 ### InnoDB全文檢索 將(DocumentId,Position)視為一個“ilist”。因此全文檢索的表中，有一個是word 字，另一個是ilist字段，并且word字段上設有索引。 由于Innodb 存儲引擎在ilist 字段中存放了Position信息，故可以進行Proximity Search（鄰近搜索），而MyISAM存儲不支持改特性。 在InnoDB存儲引擎中，為了提高全文檢索的并行性能，共有6張Auxiliary Table（輔助表），目前每張表根據word的Latin編碼進行分區 Auxiliary Table（輔助表）是持久表，存放磁盤上。在全文索引中，還有另一個重要的概念FTS Index Cache（全文索引索引緩存）來聽全文檢索的性能。 FTS Index Cache是一個紅黑樹結構，其中根據（word，ilist）進行排序。意味著插入的數據已經更新到對應的表，但是全文索引更新可能在分詞操作后還在FTS Index Cache中，Auxiliary Table 可能沒有更新。 InnoDB存儲索引會批量對Auxiliary Table 進行更新，而不是每次插入就更新一次Auxiliary Table。當對全文檢索進行查詢時，Auxiliary Table首先會對FTS Index Cache 中對應的word 字段合并到Auxiliary Table中在查詢. 這種合并提高了InnoDB存儲引擎的性能,并且由于紅黑樹排序后進行批量插入,其產生Auxiliary Table相對較小。 Innodb運行用戶查看置頂倒排索引的Auxiliary Table種的分詞信息，可以通過參數設置innodb_ft_aux_table 來觀察倒排索引的Auxiliary Table。 test 架構下表fts_a的Auxiliary Table; `set global innodb_ft_aux_table = 'test/fts_a';` 查詢test架構下的表fts_a的分詞信息`select * from information_schema.INNODB_FT_INDEX_TABLE;` 參數innodb_ft_cache_size 控制FTS Index Cache的大小,默認值為32M。當該緩存滿時，會將掐中的（word，ilist）分詞信息同步到磁盤的Auxiliary Table中。增大參該參數可以提高全文檢索的性能，但是在宕機時，未同步到磁盤重點索引信息可能需要更長的時間恢復。 FTS Document ID 是另一種概念。Innodb存儲引擎中，為了支持全文檢索，必須有一個列與word進行映射，這個列為FTS_DOS_ID，類型必須是 BIGINT UNSIGNED NOT NULL,并且Innodb引擎會加入名為FTS_DOC_ID_INDEX 的Unique Index. 上述操作是有Innodb引擎自己完成的。 用戶也可以自己在建表時自動添加FTS_DOC_ID，已經對應的Unique Index。但是類型必須是 BIGINT UNSIGNED NOT NULL 文檔分詞的插入是事務提交時完成的，而對于刪除操作，其在事務提交時，不刪除磁盤Auxiliary Table重點記錄,而只是刪除FTS Cache index中的記錄,對于Auxiliary Table中被刪除的記錄,FTS Document ID,并將其保存在DELETED auxiliary table中.在 innodb_ft_aux_table設置之后,可以訪問information_schema價格下的表innodb_ft_deleted 中觀察刪除的FTS Document ID。文檔的DML操作并不能刪除索引中的數據，相反還會在對應的DELETED表中插入記錄，因此隨著應用程序的允許，索引會變得非常大，用戶可以手工將已經刪除的記錄從索引中徹底刪除，改命令是OPTIMIZE TABLE。該命令可以做其他的操作 所以可以通過參數innodb_optimize_ _onle進行設置。如: set global innodb_optimize_fulltext_onlt=1; optimize tablefts_a; 可以通過innodb_ft_num_wird_optimize 進行限制分詞數量。默認為2000。 當InnoDB存儲引擎的全文檢索還存在以下的限制： **（1）一個表只能有一個全文檢索的索引。 （2）有多列組成的全文檢索的索引列必須使用相同的字符集與排序規則。 （3）不支持沒有單詞界定符（delimiter） 的語言。如中文、日語、韓語等。** #### 全文檢索 MySQL 5.6.4里才添加了InnoDB引擎的Full-Text索引支持。 設置全文搜索: ~~~~ ALTER TABLE `表名` ADD FULLTEXT ( `字段名` ) ~~~~ MySQL數據庫之前全文檢索(Full-Text Search)的查詢，其語法為： ~~~~ MATCH (col1,col2,....) AGAINST (expr [search_modifier]) search_modifier: { IN NATURAL LANGUAGE MODE | IN NATURAL LANGUAGE MODE WITH QUERY EXPANSION | IN BOOLEAN MODE |WITH QUERY EXPANSION } ~~~~ MySQL 數據庫通過MATCH()...AGAINST()語法支持全文檢索的查詢,MATCH指定了需要被查詢的列,AGAINST指定了使用何種方法去進行查詢。下面將對各種查詢模式進行詳細的介紹。 1.Natural Language 全文檢索溝通過MATCH函數進行查詢，默認采用Natural Language模式，其表示查詢帶有指定word的文檔。對于創建的表fts_a，查詢body 字段中帶有pease的文檔，若不使用全文索引技術，則允許使用下述sql語句： `select * from fts_a where body like '%Pease%’;` 顯然上述sql語句不能使用B+樹索引.若采用全文檢索技術,可以用下面的sql語句進行查詢: ~~~~ select * from fts_a where match(body) against ('Pottidge' in natural language mode); ~~~~ 默認是in natural languagemode 所以可以省略:`select * from cco_images where match(label) against ('Romanesco');` 查詢計劃`explain select * from cco_images where match(label) against ('Romanesco');`:  可以看到 type這列顯示的是fulltext,即表示使用全文檢索技術。同時，若表沒有創建倒排索引，則只需match 函數會拋出類錯誤：**Can't find FULLTEXT index matching the column list** 意思是:"找不到與列列表匹配的FULLTEXT索引"。 如果使用innodb搜索引擎里的mysql版本低于3.6.4時回報：**the used table type doesn't support fulltest indexes** 翻譯是：“使用的表類型不支持完整索引” 查詢的范圍結果是根據相關性（relevance）進行降序排序的，即相關性最高的結果放在第一位。相關性的值是一個非負的浮點數字，0表示沒有任何的相關性。根據mysql官方文檔可知，相關性計算根據以下四個條件： （1）word是否在文檔中出現。 （2）word在文檔中出現的次數。 （3）word在索引列中的數量。 （4）多少個文檔包含該word。  該查詢沒有經過相關性的排序 所以該查詢的速度比常規的 match查詢速度要快。 對于InnoDB存儲引擎的全文檢索，還需要考慮以下的因素： （1）查詢的word在stopword列中。忽略該字符串的查詢。 （2）查詢的word的字符串長度是否在區間【innodb_ft_min_token_size,innodb_ft_max_token_size】內 InnoDB存儲引擎中，參數innodb_ft_min_token_size默認是3，innodb_ft_max_token_size默認是84 **如果不在范圍內 這會忽略** #### Boolean MySQL數據庫允許使用IN BOOLEAN MODE修飾符來進行全文檢索。當使用該修飾符時，查詢字符串的前后字符會有特殊的含義，例如下面的語句要求查詢有字符串Vitaminhaltig但沒有Romanesco的文檔，其中+和-分別表示這個單詞必須出現，或者一定不存在。 `select * fromselect * from cco_images where match(label) against ('-Romanesco +Vitaminhaltig ' in boolean mode);` Boolean 全文檢索支持一下幾種操作符: （1）+表示該word必須存在。 （2）-表示該word必須被排除 （3）（no operator）表示該word是可選的，但是如果出現，其相關性會更高 （4）@distance 表示查詢的多個單詞之間的距離是否在distance之內，distance的單位是字節。這種全文檢索的查詢也稱為Proximity Search。 如MATCH(label) AGAINST ('"Pease pot"@30' IN BOOLEAN MODE) 表示字符串Peace和pot之間的距離需在30字節以內。 （5）>表示出現該單詞時增加相關性。 （6）<表示出現該單詞時降低相關性。 （7）~表示允許出現該單詞，但是出現是相關性為負（全文檢索查詢運行負相關性）。 （8）* 表示以該單詞開頭的單詞，如lik*，表示可以是lik、like，又或者likes。 （9） " 表示短語。 如果在against（里面添加上“”這表示該兩個單詞是一個短語） 如下：  #### query Expansion mysql數據庫支持擴展查詢。 這種查詢在查詢的關鍵詞太短，用戶需要implied knowledge（隱含知識）時進行。 通過查詢短句中添加with query expansion 或 in natural languange mode with query expansion 可以開啟blind query expamsoin（又稱 automaticrelevance feedback）。該查詢分為兩個階段。 （1）第一階段 根據單詞進行全文索引查詢。 （2）第二階段：根據第一階段產生的分詞再進行一次全文檢索的查詢。