一. 索引優(yōu)化面試題分析

1.1 分析以下幾條sql的索引使用情況

SELECT * FROM titles WHERE emp_no='10001' AND title='Senior Engineer' AND from_date='1986-06-26';
SELECT * FROM titles WHERE title='Senior Engineer' ;
SELECT * FROM titles WHERE emp_no > ‘10001';
SELECT * FROM titles WHERE emp_no > ‘10001' and title='Senior Engineer';
SELECT * FROM titles WHERE emp_no > ‘10001' order BY title;

二. 索引到底是什么

• 索引是幫助MySQL高效獲取數(shù)據(jù)的排好序的數(shù)據(jù)結(jié)構(gòu)
• 索引存儲(chǔ)在文件里
• 索引結(jié)構(gòu)
  • 二叉樹
  • 紅黑樹（相對(duì)于二叉樹多了自動(dòng)平衡）
  • HASH
  • BTREE
  • 數(shù)據(jù)結(jié)構(gòu)教學(xué)網(wǎng)站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

二叉樹：某些特定情況（列遞增）查詢次數(shù)和正常查詢次數(shù)幾乎一樣多
紅黑樹：每一層存儲(chǔ)的數(shù)據(jù)是2的(n-1)次方的數(shù)據(jù)量萍诱，如果有幾百萬數(shù)據(jù)宫静，有20層涨椒，差的數(shù)據(jù)在葉子節(jié)點(diǎn)斑司，下面谴餐，深度太大姻政，查詢速度還是很慢
HASH：可以通過hash計(jì)算到具體的磁盤位置，速度非称裆ぃ快汁展，但是不能范圍計(jì)算(a>10)
BTREE：在節(jié)點(diǎn)的橫向做文章，增大橫向節(jié)點(diǎn)數(shù)據(jù)厌殉，減少高度食绿，層數(shù)，幾百萬的數(shù)據(jù)高度可能控制到3-5層公罕，那么查詢?nèi)魏我粭l數(shù)據(jù)通過索引最多查找5次器紧，大多情況下查3次就完了

0x77 是文件存在磁盤的地址

2.1 索引概述

三. 索引底層數(shù)據(jù)結(jié)構(gòu)與算法

3.1 B-Tree

• 度(Degree)-節(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)個(gè)數(shù)
• 葉節(jié)點(diǎn)具有相同的深度
• 葉節(jié)點(diǎn)的指針為空

• 節(jié)點(diǎn)中的數(shù)據(jù)key從左到右遞增排列

  
  

引入度的概念，相當(dāng)于原來那個(gè)節(jié)點(diǎn)楼眷，把這個(gè)節(jié)點(diǎn)擴(kuò)容铲汪，讓這個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)索引，每個(gè)索引對(duì)應(yīng)數(shù)據(jù)庫的行的數(shù)據(jù)罐柳。原來紅黑樹是一個(gè)小節(jié)點(diǎn)掌腰，B-Tree實(shí)際上在那個(gè)小節(jié)點(diǎn)里面又存儲(chǔ)了很多很多小節(jié)點(diǎn)，相當(dāng)于把原來的小節(jié)點(diǎn)變成了大節(jié)點(diǎn)张吉，大節(jié)點(diǎn)里面的每一個(gè)小節(jié)點(diǎn)就是數(shù)據(jù)庫對(duì)應(yīng)的一行記錄齿梁，記錄里面有一個(gè)是key, value的結(jié)構(gòu)，key對(duì)應(yīng)這一行的縮影，value對(duì)應(yīng)這一行的數(shù)據(jù)

橫向怎么查：比如要查詢索引是77的元素勺择，先去磁盤里吧77那一層的大節(jié)點(diǎn)查出來创南，這個(gè)節(jié)點(diǎn)全部load到內(nèi)存里面，實(shí)際上在內(nèi)存里面去查找的酵幕，內(nèi)存里面做的是隨機(jī)訪問扰藕，是非常快的芳撒，跟磁盤的尋道和旋轉(zhuǎn)的查找時(shí)間去比邓深，基本可以忽略不計(jì)的，主要是查這個(gè)節(jié)點(diǎn)費(fèi)時(shí)間笔刹，查到這個(gè)節(jié)點(diǎn)之后把這個(gè)節(jié)點(diǎn)整個(gè)數(shù)據(jù)放到內(nèi)存之后芥备，在這個(gè)大節(jié)點(diǎn)里面查某一個(gè)小節(jié)點(diǎn)，也就是某一行記錄的索引是非成嗖耍快的萌壳，因?yàn)槭窃趦?nèi)存里面做操作，都是內(nèi)存的隨機(jī)訪問日月，直接通過地址在內(nèi)存里面去找袱瓮，非常快爱咬。

疑問：度越大越好尺借，100萬數(shù)據(jù)，度設(shè)置100萬精拟，那么只有一層了燎斩，查找更快了？

不行蜂绎，如果越大越好栅表，那么所有數(shù)據(jù)都在一個(gè)節(jié)點(diǎn)了，這個(gè)節(jié)點(diǎn)非常大师枣，幾十上百M(fèi)怪瓶，磁盤的操作不可能一次把所有都拿出來。如果讀取磁盤每次IO操作讀取一頁的數(shù)據(jù)(大屑馈：4K洗贰，磁盤數(shù)據(jù)的基本單位)，每次IO讀取頁數(shù)跟計(jì)算機(jī)的性能有關(guān)拨脉，如果大節(jié)點(diǎn)是10M哆姻，那么要讀取完這個(gè)節(jié)點(diǎn)要很多次IO操作，最好的是一次性IO操作讀取完一個(gè)節(jié)點(diǎn)玫膀，所以不能越大越好矛缨。這個(gè)度是有上限的，不能無限擴(kuò)大，是根據(jù)計(jì)算機(jī)硬件情況mysql來自動(dòng)優(yōu)化的箕昭。一般mysql會(huì)把一個(gè)節(jié)點(diǎn)的大小設(shè)置成一頁（4K）灵妨，能算出度的大小。4K/小節(jié)點(diǎn)數(shù)據(jù)=度落竹，所以小節(jié)點(diǎn)越小泌霍，度越大。

3.2 B+Tree(B-Tree變種)

• 非葉子節(jié)點(diǎn)不存儲(chǔ)data述召，只存儲(chǔ)key朱转，可以增大度
• 葉子節(jié)點(diǎn)不存儲(chǔ)指針

• 順序訪問指針，提高區(qū)間訪問的性能

  
  

B+Tree： 把數(shù)據(jù)放到葉子節(jié)點(diǎn)（將key依次復(fù)制到下面的非葉子節(jié)點(diǎn)积暖，并將數(shù)據(jù)移到葉子節(jié)點(diǎn)）藤为，非葉子節(jié)點(diǎn)不存儲(chǔ)任何數(shù)據(jù)，存儲(chǔ)索引key（非常卸嵝獭）缅疟，同等的節(jié)點(diǎn)大小可以存儲(chǔ)更多的索引，非葉子節(jié)點(diǎn)的度更大遍愿，高度就越低存淫，只有非葉子節(jié)點(diǎn)才影響查找次數(shù)，葉子節(jié)點(diǎn)是最后一次查找沼填，無所謂桅咆，總的查找次數(shù)是沒有任何影響。key有一定的冗余（相同）倾哺，key很小轧邪，適量的冗余可以接受刽脖。
B+Tree在底層的葉子節(jié)點(diǎn)之間（節(jié)點(diǎn)的尾元素和頭元素之間）還有一個(gè)指針的存儲(chǔ)：存儲(chǔ)指針是為了范圍查詢羞海，直接通過指針去找

3.3 B+Tree索引的性能分析

• 一般使用磁盤I/O次數(shù)評(píng)價(jià)索引結(jié)構(gòu)的優(yōu)劣
• 預(yù)讀：磁盤一般會(huì)順序向后讀取一定長度的數(shù)據(jù)(頁的整數(shù)倍)放入內(nèi)存
• 局部性原理：當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用
• B+Tree節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁曲管，每次新建節(jié)點(diǎn)直接申請(qǐng)一個(gè)頁的空間却邓，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁里，就實(shí)現(xiàn)了一個(gè)節(jié)點(diǎn)的載入只需一次I/O
• B+Tree的度d一般會(huì)超過100院水，因此h非常小(一般為3到5之間)

存儲(chǔ)引擎設(shè)置在表級(jí)別腊徙，不是數(shù)據(jù)庫，同一個(gè)庫兩張表可以用不同的存儲(chǔ)引擎

test_innodb_lock.frm: innodb表結(jié)構(gòu)文件
test_innodb_lock.ibd: 索引和數(shù)據(jù)文件檬某，在一起

myisam引擎數(shù)據(jù)庫文件：

test_myisam.frm: myisam表結(jié)構(gòu)文件
test_myisam.MYD: 數(shù)據(jù)文件
test_myisam.MYI：索引文件

3.4 MyISAM索引實(shí)現(xiàn)(非聚集: 索引和數(shù)據(jù)分開存儲(chǔ))

MyISAM索引文件和數(shù)據(jù)文件是分離的
主鍵索引：

非主鍵索引撬腾，輔助索引：（myisam非主鍵索引和主鍵索引存儲(chǔ)方式一樣）

MyISAM葉子節(jié)點(diǎn)存的是指針，通過指針去文件里面再找數(shù)據(jù)

3.5 InnoDB索引實(shí)現(xiàn)(聚集：將索引和數(shù)據(jù)聚集到一起在葉子節(jié)點(diǎn)上)

• 數(shù)據(jù)文件本身就是索引文件
• 表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)文件
• 聚集索引-葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄
• 為什么InnoDB表必須有主鍵恢恼，并且推薦使用整型的自增主鍵民傻？

為什么InnoDB表必須有主鍵：表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)文件 ，如果沒有設(shè)置，會(huì)默認(rèn)一列不重復(fù)的作為主鍵漓踢，如果沒有字段不重復(fù)的牵署，后臺(tái)會(huì)默認(rèn)生成一個(gè)不重復(fù)字段作為主鍵（整型的），推薦的是自增的主鍵

UUID和整型的自增主鍵區(qū)別：

• UUID比較大喧半，比自增主鍵浪費(fèi)一點(diǎn)存儲(chǔ)空間奴迅；
• 查找的時(shí)候，索引會(huì)比較大小去查找（比這個(gè)大的去找右邊挺据，小的找左邊）取具，int類型根據(jù)大小比較，UUID根據(jù)字符的ASCII編碼大小比較扁耐，顯然者填，整型的int類型的比較大小比字符串類型的比較大小速度快
• 主鍵自增插入直接在已有的數(shù)據(jù)后面插入，是連續(xù)的做葵，查找范圍的時(shí)候可以鎖定某一頁的某個(gè)范圍占哟，查找非常快酿矢，而UUID是隨機(jī)生成的榨乎，可能會(huì)在插在已有的數(shù)據(jù)之間，導(dǎo)致已有的數(shù)據(jù)中間分裂瘫筐，還可能造成其他節(jié)點(diǎn)分裂蜜暑，速度很慢

• 為什么非主鍵索引結(jié)構(gòu)葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵值？(一致性和節(jié)省存儲(chǔ)空間)

innodb主鍵索引將一行數(shù)據(jù)存儲(chǔ)到葉子節(jié)點(diǎn)上

innodb非主鍵索引存儲(chǔ)的是主鍵索引的值：為了一致性和節(jié)省存儲(chǔ)空間

3.6 聯(lián)合索引的底層存儲(chǔ)結(jié)構(gòu)長什么樣策肝？

varchar類型兩個(gè)索引（key1, key2）之間是 key1 + key2

這里是最上面的三個(gè)索引（emp_no(int), title(varchar), from_date(data)）數(shù)據(jù)結(jié)構(gòu)肛捍。先比較第一個(gè)字段，如果符合條件后面的字段就不用比了之众，然后索引順序依次比較拙毫。。棺禾。

分庫缀蹄，主鍵遞增，保證id不沖突膘婶，設(shè)置步長

第一個(gè)庫主鍵存1, 3, 5...缺前，第二個(gè)庫存2, 4, 6...

四. 索引最左前綴原理

單值索引實(shí)際上也是一種聯(lián)合索引，只不過值只有一個(gè)悬襟。

• 聯(lián)合索引的底層數(shù)據(jù)結(jié)構(gòu)長什么樣衅码？
  
  
  例如：員工表字段分別是員工號(hào)，員工職位脊岳，員工入職日期逝段，還有其他字段筛璧，選擇這三個(gè)字段作為聯(lián)合索引，那么葉子節(jié)點(diǎn)下面藍(lán)色的(2002-06-03)是什么：如果這三個(gè)字段作為主鍵索引的話惹恃，可以標(biāo)識(shí)某一行記錄夭谤，那么剩下的藍(lán)色區(qū)域value這一行就是存的其他字段；如果說這三個(gè)字段只是建的一個(gè)輔助索引巫糙，那么藍(lán)色區(qū)域存的肯定是主鍵朗儒，我們這里三個(gè)字段建的是主鍵索引，聯(lián)合主鍵参淹。