文獻參考連接:https://www.cnblogs.com/wuzhenzhao/p/10341114.html
最近在找工作中，復(fù)習(xí)了下mysql索引相關(guān)知識, 整理的比較雜亂:
首先說下一常用的索引類型:一般是B-tree和Hash

B-tree簡要說明

每一個子節(jié)點都包含指向下一個子節(jié)點的指針躬它，從而方便葉子節(jié)點的范圍遍歷
B-tree索引通常意味著所有的值都是按順序存儲的,而且每一個葉子節(jié)點到根的距離相同

平衡多路查找樹（B-Tree）

B-tree是為磁盤等外部存儲設(shè)備設(shè)計的一種平衡查找樹腾啥，因此先講一下磁盤的基礎(chǔ)知識.
系統(tǒng)從磁盤讀取數(shù)據(jù)到內(nèi)存是以磁盤塊(block)為基本單位，位于同一個磁盤塊中的數(shù)據(jù)會被一次性取出來冯吓，而不是需要什么就取什么倘待。InnoDB存儲引擎中有頁(Page)的概念，頁是其磁盤管理的最小單位桑谍。InnoDB 存儲引擎的每個頁默認大小為16KB延柠，通過innodb_page_size將頁的大小設(shè)置為4k、8k锣披、16k,在mysql中可以通過如下命令取查看大小: show variables like 'innodb_page_size';
而系統(tǒng)的磁盤塊的存儲空間往往一個沒有這么大贞间，InnoDB在把磁盤數(shù)據(jù)讀入到磁盤時會以頁為基本單位增热，在查詢數(shù)據(jù)時如果一個頁中的每條數(shù)據(jù)都能有助于定位數(shù)據(jù)記錄的位置，這將會減少磁盤I/O次數(shù)，提高查詢效率朝蜘。
B-tree結(jié)構(gòu)的數(shù)據(jù)可以讓系統(tǒng)高效的找到數(shù)據(jù)所在的磁盤塊副渴。為了描述B-tree，首先自定義一條記錄為一個二元數(shù)組[key,data]，key為記錄的鍵值漩符，對應(yīng)表中的主鍵值，data作為一行數(shù)據(jù)中除主鍵外的數(shù)據(jù)。對于不同的記錄戳粒，key值互不相同苹祟。一顆m階的B-tree有如下特性:

1. 每個節(jié)點最多有m個孩子
2. 除了根節(jié)點和葉子節(jié)點外，其它每個節(jié)點至少有Ceil(m/2)個孩子耐薯。
3. 若根節(jié)點不是葉子節(jié)點，則至少有2個孩子
4. 所有葉子節(jié)點都在同一層，且不包含其它關(guān)鍵字信息
5. 每個非終端節(jié)點包含n個關(guān)鍵字信息（P0,P1,…Pn, k1,…kn）
6. 關(guān)鍵字的個數(shù)n滿足：ceil(m/2)-1 <= n <= m-1
7. ki(i=1,…n)為關(guān)鍵字，且關(guān)鍵字升序排序彩届。
8. Pi(i=1,…n)為指向子樹根節(jié)點的指針寨辩。P(i-1)指向的子樹的所有節(jié)點關(guān)鍵字均小于ki甸怕，但都大于k(i-1)

B-Tree中的每個節(jié)點根據(jù)實際情況可以包含大量的關(guān)鍵字信息和分支式曲，如下圖所示為一個3階的B-Tree:

3階的B-Tree

每個節(jié)點占用一個盤塊的磁盤空間敦腔，一個節(jié)點上有兩個升序排序的關(guān)鍵字和三個指向子樹根節(jié)點的指針判族，指針存儲的是子節(jié)點所在磁盤塊的地址辩撑。兩個關(guān)鍵詞劃分成的三個范圍域?qū)?yīng)三個指針指向的子樹的數(shù)據(jù)的范圍域水慨。以根節(jié)點為例，關(guān)鍵字為17和35砌滞，P1指針指向的子樹的數(shù)據(jù)范圍為小于17打掘，P2指針指向的子樹的數(shù)據(jù)范圍為17~35，P3指針指向的子樹的數(shù)據(jù)范圍為大于35。模擬查找關(guān)鍵字29的過程：

1. 根據(jù)根節(jié)點找到磁盤塊1，讀入內(nèi)存落君∥圃【磁盤I/O操作第1次】
2. 比較關(guān)鍵字29在區(qū)間（17,35），找到磁盤塊1的指針P2。
3. 根據(jù)P2指針找到磁盤塊3，讀入內(nèi)存强挫「┎常【磁盤I/O操作第2次】
4. 比較關(guān)鍵字29在區(qū)間（26,30）柜蜈，找到磁盤塊3的指針P2。
5. 根據(jù)P2指針找到磁盤塊8，讀入內(nèi)存至壤⌒┚伲【磁盤I/O操作第3次】

6. 在磁盤塊8中的關(guān)鍵字列表中找到關(guān)鍵字29。
   分析上面過程，發(fā)現(xiàn)需要3次磁盤操作I/O操作绒怨，和3次內(nèi)存查找操作纺酸。由于內(nèi)存關(guān)鍵字是一個有序表結(jié)構(gòu)窖逗，可以利用二分法提高查找效率。B-Tree為了保證絕對平衡他有自己的機制餐蔬，比如每個節(jié)點上的關(guān)鍵字個數(shù)=路數(shù)（階數(shù)-1）碎紊，如下圖：

   
   
   分裂
   
   

   可以看到添加節(jié)點后違反了原有的規(guī)則，這個時候會進行分裂樊诺。結(jié)果就會形成一根最新的樹仗考，（如果分裂過程中23 333 這個節(jié)點頁不滿足了會繼續(xù)向上分裂）：

   
   
   image.png
   
   所以建立合適的索引是很重要的 ，不宜多词爬，當(dāng)加一條數(shù)據(jù)秃嗜，整棵樹會進行重組

b+tree

B+Tree是在B-Tree基礎(chǔ)上的一種優(yōu)化，使其更適合實現(xiàn)外存儲索引結(jié)構(gòu)，InnoDB存儲引擎就是用B+Tree實現(xiàn)其索引結(jié)構(gòu)锅锨。
從 B-Tree 結(jié)構(gòu)圖中可以看到每個節(jié)點中不僅包含數(shù)據(jù)的key值叽赊，還有data值。而每一個頁的存儲空間是有限的必搞，如果data數(shù)據(jù)較大時將會導(dǎo)致每個節(jié)點（即一個頁）能存儲的key的數(shù)量很小必指，當(dāng)存儲的數(shù)據(jù)量很大時同樣會導(dǎo)致B-Tree的深度較大，增大查詢時的磁盤I/O次數(shù)恕洲，進而影響查詢效率塔橡。在B+Tree中，所有數(shù)據(jù)記錄節(jié)點都是按照鍵值大小順序存放在同一層的葉子節(jié)點上霜第，而非葉子節(jié)點上只存儲key值信息葛家，這樣可以大大加大每個節(jié)點存儲的key值數(shù)量，降低B+Tree的高度泌类。
B+Tree相對于B-Tree有幾點不同：

1. B+節(jié)點關(guān)鍵字搜索采用閉合區(qū)間
2. B+非葉節(jié)點不保存數(shù)據(jù)相關(guān)信息癞谒，只保存關(guān)鍵字和子節(jié)點的引用
3. B+關(guān)鍵字對應(yīng)的數(shù)據(jù)保存在葉子節(jié)點中
4. B+葉子節(jié)點是順序排列的，并且相鄰節(jié)點具有順序引用的關(guān)系

將B-Tree優(yōu)化末誓，由于B+Tree的非葉子節(jié)點只存儲鍵值信息扯俱，假設(shè)每個磁盤塊能存儲4個鍵值及指針信息，則變成B+Tree后其結(jié)構(gòu)如下圖所示：

b+tree

通常在B+Tree上有兩個頭指針喇澡，一個指向根節(jié)點迅栅，另一個指向關(guān)鍵字最小的葉子節(jié)點，而且所有葉子節(jié)點（即數(shù)據(jù)節(jié)點）之間是一種鏈?zhǔn)江h(huán)結(jié)構(gòu)晴玖。因此可以對B+Tree進行兩種查找運算：一種是對于主鍵的范圍查找和分頁查找读存，另一種是從根節(jié)點開始，進行隨機查找呕屎。

在數(shù)據(jù)庫中让簿，B+Tree的高度一般都在2~4層。mysql 的InnoDB存儲引擎在設(shè)計時是將根節(jié)點常駐內(nèi)存的秀睛，也就是說查找某一鍵值的行記錄時最多只需要1~3次磁盤I/O操作尔当。數(shù)據(jù)庫中的B+Tree索引可以分為聚集索引（clustered index）和輔助索引（secondary index）。上面的B+Tree示例圖在數(shù)據(jù)庫中的實現(xiàn)即為聚集索引蹂安，聚集索引的B+Tree中的葉子節(jié)點存放的是整張表的行記錄數(shù)據(jù)椭迎。輔助索引與聚集索引的區(qū)別在于輔助索引的葉子節(jié)點并不包含行記錄的全部數(shù)據(jù)，而是存儲相應(yīng)行數(shù)據(jù)的聚集索引鍵田盈，即主鍵畜号。當(dāng)通過輔助索引來查詢數(shù)據(jù)時，InnoDB存儲引擎會遍歷輔助索引找到主鍵允瞧，然后再通過主鍵在聚集索引中找到完整的行記錄數(shù)據(jù)简软。

B+Tree在MYSQL中采用的是 左閉合區(qū)間蛮拔，MYSQL推崇使用ID作為索引，由于ID是自增的數(shù)字類型痹升，只會增大建炫，所以采用向右拓展的一個方式，從根節(jié)點進行比對疼蛾，由于枝節(jié)點不保存數(shù)據(jù)踱卵，無所謂命不命中，都要繼續(xù)走到葉子節(jié)點才能加載數(shù)據(jù)据过。

B+Tree在兩大引擎中如何體現(xiàn)：

那么在 MYSQL中比較主流的兩大引擎是：Myisam 跟 innoDB，存儲引擎是建立在表上面的妒挎，在建立表的時候可以指定所需要的搜索引擎绳锅。例如下列的創(chuàng)建語句中就指定了搜索引擎為：ENGINE=InnoDB，不指定就使用默認的InnoDB
CREATE TABLE 'USER' (
'id' int(11) not NUll,
'name' varchr(50) default NUll,
PRIMARY KEY ('id')
) ENGINE=innodb DEFAULT CHARSET=utf8;
　B+Tree 在 Myisam 中的體現(xiàn)：

在創(chuàng)建好表結(jié)構(gòu)并且指定搜索引擎為 Myisam之后酝掩，會在數(shù)據(jù)目錄生成3個文件鳞芙，分別是table_name.frm(表結(jié)構(gòu)文件)，table_name.MYD（數(shù)據(jù)保存文件）,table_name.MYI（索引保存文件）期虾。

myisam

兩個文件分別保存了數(shù)據(jù)及索引原朝，由于B+Tree中只有葉子節(jié)點保存數(shù)據(jù)區(qū)，在Myisam中镶苞，數(shù)據(jù)區(qū)中保存的是數(shù)據(jù)的引用地址喳坠，就比如說ID為101的數(shù)據(jù)信息所保存到物理磁盤地址為 0x123456,在索引中的節(jié)點數(shù)據(jù)去中所保存的就是這個磁盤地址指針。當(dāng)掃描到這個指針位置茂蚓，就可以通過這個磁盤指針講數(shù)據(jù)加載出來

在Myisam中B+Tree的實現(xiàn)中比如現(xiàn)在不用ID作為索引了壕鹉，要用name，那么他的一個展現(xiàn)形式有事怎么樣的呢聋涨？其實他與ID作為索引是一樣的晾浴，也是保存他指定的磁盤位置指針，他們是平級的牍白。如下圖:

myisam

B+Tree 在 InnoDB 中的體現(xiàn)：
在創(chuàng)建好表結(jié)構(gòu)并且指定搜索引擎為Innodb之后脊凰，會在數(shù)據(jù)目錄生成2個文件，分別是table_name.frm(表結(jié)構(gòu)文件)茂腥，table_name.idb（數(shù)據(jù)與索引保存文件）狸涌。
在 InnoDB中，因為設(shè)計之初就是認為主鍵是非常重要的础芍。是以主鍵為索引來組織數(shù)據(jù)的存儲杈抢，當(dāng)我們沒有顯示的建立主鍵索引的時候，搜索引擎會隱式的為我們建立一個主鍵索引以組織數(shù)據(jù)存儲仑性。數(shù)據(jù)庫表行中數(shù)據(jù)的物理順序與鍵值的邏輯（索引）順序相同惶楼，InnoDB就是以聚集索引來組織數(shù)據(jù)的存儲的，在葉子節(jié)點上，保存了數(shù)據(jù)的所有信息歼捐。如果這個時候建立了name字段的索引：

Innodb

會產(chǎn)生一個輔助索引何陆，即name字段的索引，而此刻葉子節(jié)點上所保存的數(shù)據(jù)為 聚集索引（ID索引）的關(guān)鍵字的值豹储，基于輔助索引找到ID索引的值贷盲，再通過ID索引區(qū)獲取最終的數(shù)據(jù)。這個做法的好處是在于產(chǎn)生數(shù)據(jù)遷移的時候只要ID沒發(fā)生變法剥扣，那么輔助索引不需要重新生成巩剖，不這么做的話，如果存儲的是磁盤地址的話钠怯，在數(shù)據(jù)遷移后所有輔助索引都需要重新生成佳魔。

索引知識：

找出離散性最好的列：

越大離散型越好 count(distinct col):count(col) 理解為差異性。結(jié)論：離散性越高選擇性就越好

最左匹配原則：

1. 經(jīng)常用的列優(yōu)先 【最左匹配原則】晦炊。
2. 選擇性（離散度）高的列優(yōu)先【離散度高原則】鞠鲜。
3. 寬度小的列優(yōu)先【最少空間原則】。

覆蓋索引：

果查詢列可通過索引節(jié)點中的關(guān)鍵字直接返回断国，則該索引稱之為覆蓋索引贤姆。覆蓋索引可減少數(shù)據(jù)庫IO，將隨機IO變?yōu)轫樞騃O稳衬，可提高查詢性能霞捡。比說所建立了一個聯(lián)合索引 reate index idx_name_phoneNum on users(name,phoneNum);而此刻有sql select name phoneNum from 。薄疚。弄砍。。這個就是覆蓋索引

總結(jié)及驗證：

索引列的數(shù)據(jù)長度能少則少输涕。索引一定不是越多越好音婶，越全越好，一定是建合適的莱坎。查詢條件上有計算函數(shù)無法命中索引衣式。

匹配列前綴：like 9999%（最原則上按照左匹配上來說是可以的，但是不一定能用到索引檐什，當(dāng)離散性太差的時候就不行）碴卧，like %9999%（不行）、like %9999（不行）用不到索引乃正；

Where 條件中 not in 和 <>操作無法使用索引住册；匹配范圍值，order by 也可用到索引瓮具；多用指定列查詢荧飞，只返回自己想到的數(shù)據(jù)列凡人，少用select *；

聯(lián)合索引中如果不是按照索引最左列開始查找叹阔，無法使用索引挠轴；

聯(lián)合索引中精確匹配最左前列并范圍匹配另外一列可以用到索引；比如聯(lián)合索引【name耳幢，phoneNum】岸晦，當(dāng)SQL為：select .....where name='1' and phoneNum>xxxxxxx.

聯(lián)合索引中如果查詢中有某個列的范圍（大于小于）查詢，則其右邊的所有列都無法使用索引睛藻；