一. 索引優(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)
• 索引存儲在文件里
• 索引結(jié)構(gòu)
  • 二叉樹
  • 紅黑樹（相對于二叉樹多了自動平衡）
  • HASH
  • BTREE
  • 數(shù)據(jù)結(jié)構(gòu)教學網(wǎng)站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

二叉樹：某些特定情況（列遞增）查詢次數(shù)和正常查詢次數(shù)幾乎一樣多
紅黑樹：每一層存儲的數(shù)據(jù)是2的(n-1)次方的數(shù)據(jù)量，如果有幾百萬數(shù)據(jù)，有20層，差的數(shù)據(jù)在葉子節(jié)點，下面，深度太大，查詢速度還是很慢
HASH：可以通過hash計算到具體的磁盤位置，速度非?？?，但是不能范圍計算(a>10)
BTREE：在節(jié)點的橫向做文章，增大橫向節(jié)點數(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é)點的數(shù)據(jù)存儲個數(shù)
• 葉節(jié)點具有相同的深度
• 葉節(jié)點的指針為空

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

  
  

引入度的概念，相當于原來那個節(jié)點，把這個節(jié)點擴容，讓這個節(jié)點可以存儲多個索引，每個索引對應數(shù)據(jù)庫的行的數(shù)據(jù)。原來紅黑樹是一個小節(jié)點，B-Tree實際上在那個小節(jié)點里面又存儲了很多很多小節(jié)點，相當于把原來的小節(jié)點變成了大節(jié)點，大節(jié)點里面的每一個小節(jié)點就是數(shù)據(jù)庫對應的一行記錄，記錄里面有一個是key, value的結(jié)構(gòu)，key對應這一行的縮影，value對應這一行的數(shù)據(jù)

橫向怎么查：比如要查詢索引是77的元素，先去磁盤里吧77那一層的大節(jié)點查出來，這個節(jié)點全部load到內(nèi)存里面，實際上在內(nèi)存里面去查找的，內(nèi)存里面做的是隨機訪問，是非常快的，跟磁盤的尋道和旋轉(zhuǎn)的查找時間去比，基本可以忽略不計的，主要是查這個節(jié)點費時間，查到這個節(jié)點之后把這個節(jié)點整個數(shù)據(jù)放到內(nèi)存之后，在這個大節(jié)點里面查某一個小節(jié)點，也就是某一行記錄的索引是非?？斓模驗槭窃趦?nèi)存里面做操作，都是內(nèi)存的隨機訪問，直接通過地址在內(nèi)存里面去找，非?？臁?/p>

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

不行，如果越大越好，那么所有數(shù)據(jù)都在一個節(jié)點了，這個節(jié)點非常大，幾十上百M，磁盤的操作不可能一次把所有都拿出來。如果讀取磁盤每次IO操作讀取一頁的數(shù)據(jù)(大?。?K，磁盤數(shù)據(jù)的基本單位)，每次IO讀取頁數(shù)跟計算機的性能有關(guān)，如果大節(jié)點是10M，那么要讀取完這個節(jié)點要很多次IO操作，最好的是一次性IO操作讀取完一個節(jié)點，所以不能越大越好。這個度是有上限的，不能無限擴大，是根據(jù)計算機硬件情況mysql來自動優(yōu)化的。一般mysql會把一個節(jié)點的大小設置成一頁（4K），能算出度的大小。4K/小節(jié)點數(shù)據(jù)=度，所以小節(jié)點越小，度越大。

3.2 B+Tree(B-Tree變種)

• 非葉子節(jié)點不存儲data，只存儲key，可以增大度
• 葉子節(jié)點不存儲指針

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

  
  

B+Tree： 把數(shù)據(jù)放到葉子節(jié)點（將key依次復制到下面的非葉子節(jié)點，并將數(shù)據(jù)移到葉子節(jié)點），非葉子節(jié)點不存儲任何數(shù)據(jù)，存儲索引key（非常?。鹊墓?jié)點大小可以存儲更多的索引，非葉子節(jié)點的度更大，高度就越低，只有非葉子節(jié)點才影響查找次數(shù)，葉子節(jié)點是最后一次查找，無所謂，總的查找次數(shù)是沒有任何影響。key有一定的冗余（相同），key很小，適量的冗余可以接受。
B+Tree在底層的葉子節(jié)點之間（節(jié)點的尾元素和頭元素之間）還有一個指針的存儲：存儲指針是為了范圍查詢，直接通過指針去找

3.3 B+Tree索引的性能分析

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

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

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索引實現(xiàn)(非聚集: 索引和數(shù)據(jù)分開存儲)

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

非主鍵索引，輔助索引：（myisam非主鍵索引和主鍵索引存儲方式一樣）

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

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

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

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

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

• UUID比較大，比自增主鍵浪費一點存儲空間；
• 查找的時候，索引會比較大小去查找（比這個大的去找右邊，小的找左邊），int類型根據(jù)大小比較，UUID根據(jù)字符的ASCII編碼大小比較，顯然，整型的int類型的比較大小比字符串類型的比較大小速度快
• 主鍵自增插入直接在已有的數(shù)據(jù)后面插入，是連續(xù)的，查找范圍的時候可以鎖定某一頁的某個范圍，查找非常快，而UUID是隨機生成的，可能會在插在已有的數(shù)據(jù)之間，導致已有的數(shù)據(jù)中間分裂，還可能造成其他節(jié)點分裂，速度很慢

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

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

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

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

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

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

分庫，主鍵遞增，保證id不沖突，設置步長

第一個庫主鍵存1, 3, 5...，第二個庫存2, 4, 6...

四. 索引最左前綴原理

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

• 聯(lián)合索引的底層數(shù)據(jù)結(jié)構(gòu)長什么樣？
  
  
  例如：員工表字段分別是員工號，員工職位，員工入職日期，還有其他字段，選擇這三個字段作為聯(lián)合索引，那么葉子節(jié)點下面藍色的(2002-06-03)是什么：如果這三個字段作為主鍵索引的話，可以標識某一行記錄，那么剩下的藍色區(qū)域value這一行就是存的其他字段；如果說這三個字段只是建的一個輔助索引，那么藍色區(qū)域存的肯定是主鍵，我們這里三個字段建的是主鍵索引，聯(lián)合主鍵。