我是肥哥，一名不專業(yè)的面試官！
我是囧囧，一名積極找工作的小菜鳥(niǎo)，囧囧表示：面試最怕的就是面試官問(wèn)的知識(shí)點(diǎn)太籠統(tǒng)，自己無(wú)法快速定位到關(guān)鍵問(wèn)題點(diǎn)?。?！
本期主要面試考點(diǎn)
面試官考點(diǎn)之談?wù)勀銓?duì)索引的理解？
面試官考點(diǎn)之解釋一下計(jì)算機(jī)層面索引快的原因？
面試官考點(diǎn)之為什么不使用哈希結(jié)構(gòu)作為索引結(jié)構(gòu)？
面試官考點(diǎn)之為什么不使用二叉樹(shù)作為索引結(jié)構(gòu)？
面試官考點(diǎn)之為什么不使用B-Tree，而是B+Tree？
面試官考點(diǎn)之索引是加速查詢，那么是否應(yīng)該給表盡可能建立多的索引列？
面試官考點(diǎn)之談?wù)勀銓?duì)索引的理解？
談到索引，最先聯(lián)想到的大概就是字典目錄，根據(jù)MySQL官方定義，索引是用來(lái)幫助MySQL高效獲取數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)。
本質(zhì)上：索引是一種有序的快速查找的數(shù)據(jù)結(jié)構(gòu)，用來(lái)快速高效的查找數(shù)據(jù)。
簡(jiǎn)單來(lái)說(shuō)，可以類比字典目錄，火車車次表。
面試官考點(diǎn)之解釋一下計(jì)算機(jī)層面索引快的原因？
計(jì)算機(jī)從磁盤獲取數(shù)據(jù)，加載到內(nèi)存期間，一般都要經(jīng)歷3個(gè)常規(guī)的耗時(shí)過(guò)程：
1、尋道（時(shí)間）：確定要讀的數(shù)據(jù)在哪個(gè)磁道耗費(fèi)的時(shí)間
2、旋轉(zhuǎn)延遲（時(shí)間）：確定要讀的數(shù)據(jù)在磁道上的哪個(gè)扇區(qū)耗費(fèi)的時(shí)間
3、數(shù)據(jù)傳輸（時(shí)間）：數(shù)據(jù)加載到內(nèi)存耗費(fèi)的時(shí)間
每次加載數(shù)據(jù)，我們稱其為一次磁盤IO，每一次IO操作耗費(fèi)時(shí)間 = 尋道 + 旋轉(zhuǎn)延遲 + 數(shù)據(jù)傳輸（時(shí)間短暫，可以忽略不計(jì)）。
事實(shí)上實(shí)際加載數(shù)據(jù)到內(nèi)存的時(shí)間非常短暫，一次IO操作主要的耗時(shí)來(lái)自尋道和旋轉(zhuǎn)延遲。
總體來(lái)說(shuō)，一般一次IO操作，耗時(shí)大概只有幾ms。假如是4ms，雖然看起來(lái)很短暫，但是數(shù)據(jù)庫(kù)百萬(wàn)級(jí)別的數(shù)據(jù)加載一遍，就需要4000s，對(duì)于一個(gè)系統(tǒng)來(lái)說(shuō)，簡(jiǎn)直是毀滅級(jí)別的。
我們需要的就是減少磁盤IO的次數(shù)，這也是使用索引的意義所在！?。∷饕軌虮ＷC在億級(jí)別的數(shù)據(jù)，只需要2~4次磁盤IO，這無(wú)疑是個(gè)福音！
面試官考點(diǎn)之為什么不使用哈希結(jié)構(gòu)作為索引結(jié)構(gòu)？
一般正常的業(yè)務(wù)場(chǎng)景中，通常查詢多數(shù)是范圍查詢 類似：
select id, name, age from sys_user where age between 18 and 28;
哈希結(jié)構(gòu)作為索引，那么存儲(chǔ)引擎就會(huì)為每一行表記錄計(jì)算出哈希值，哈希索引存儲(chǔ)的就是HASH碼；
HASH碼直接隨機(jī)生成，并沒(méi)有規(guī)律
沒(méi)有規(guī)律的HASH碼，導(dǎo)致數(shù)據(jù)隨機(jī)分布存儲(chǔ)，這就導(dǎo)致即使是兩個(gè)很相近的行記錄，極大可能也會(huì)被分配到不同的桶（磁盤塊）中。
最壞的情況下每查找一條記錄，都要進(jìn)行一次磁盤IO （可怕）。
優(yōu)點(diǎn)，哈希結(jié)構(gòu)這樣key-val 鍵值對(duì)的形式對(duì)于精確查找非常敏感，對(duì)全值匹配很友好，所以單條記錄查詢效率非常高，時(shí)間復(fù)雜度為 1，但是我們?nèi)粘I(yè)務(wù)來(lái)說(shuō)，最常用的還是范圍搜索，所以不哈希結(jié)構(gòu)適合。
記住一點(diǎn)即可：Hash索引適合精確查找，全值匹配，不適合范圍查找。
MySQL目前有Memory引擎和NDB引擎支持Hash索引。
面試官考點(diǎn)之為什么不使用二叉樹(shù)作為索引結(jié)構(gòu)？
首先觀察一下二叉樹(shù)結(jié)構(gòu)
二叉樹(shù)最多有兩個(gè)子節(jié)點(diǎn)，這種結(jié)構(gòu)導(dǎo)致樹(shù)的高度會(huì)很高，增加IO次數(shù)，特殊情況下可能化為鏈表結(jié)構(gòu)，相當(dāng)于全表掃描，全量磁盤IO。
假設(shè)二叉樹(shù)結(jié)構(gòu)作為索引，理想情況下是一顆完全二叉樹(shù)，那么具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)深度為log2x+1
（其中x表示不大于n的最大整數(shù)）
如果一個(gè)數(shù)據(jù)在二叉樹(shù)結(jié)構(gòu)的100層，那么為了查找到此數(shù)據(jù)，需要進(jìn)行100次磁盤IO。更糟糕情況下，二叉樹(shù)會(huì)退化成鏈表結(jié)構(gòu)，既，斜二叉樹(shù)。
類似的平衡二叉樹(shù)，高度也很高。
面試官考點(diǎn)之為什么不使用B-Tree，而是B+Tree？
既然二叉樹(shù)結(jié)構(gòu)樹(shù)高度很高，導(dǎo)致查詢時(shí)磁盤IO增加，那B-Tree 呢？B-Tree可以存儲(chǔ)更多的數(shù)據(jù)，高度更低，為什么不選擇？而是B+Tree？
B-Tree是多路平衡搜索樹(shù)，相比二叉樹(shù)結(jié)構(gòu)，可以極大的優(yōu)化磁盤IO次數(shù)，但是B-Tree每個(gè)節(jié)點(diǎn)中不僅包含數(shù)據(jù)的key（索引值），還有data（整行記錄），使用B-Tree結(jié)構(gòu)，優(yōu)點(diǎn)是找到索引就代表找到了數(shù)據(jù)記錄。
既然如此為什么不使用B-Tree結(jié)構(gòu)？還是老問(wèn)題，磁盤IO數(shù)！??！
我們知道MySQL讀取數(shù)據(jù)是以頁(yè)為單位（磁盤塊），每頁(yè)（或者說(shuō)每個(gè)磁盤塊）的存儲(chǔ)空間是有限的
如果data 很大，將會(huì)導(dǎo)致每頁(yè)存儲(chǔ)的索引數(shù)量很小
所以數(shù)據(jù)表存儲(chǔ)的數(shù)據(jù)量很大的時(shí)候同樣會(huì)導(dǎo)致 B-Tree的深度很大，增大查詢時(shí)的磁盤I/O次數(shù)，進(jìn)而影響查詢效率。
再說(shuō)到B+Tree，B+Tree是對(duì)B-Tree 的一種優(yōu)化結(jié)構(gòu)，使其更適合實(shí)現(xiàn)外存儲(chǔ)索引結(jié)構(gòu)
1、非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值信息(索引信息)
2、所有的數(shù)據(jù)記錄都按照鍵值大小順序存放在同一層的葉子節(jié)點(diǎn)上
好處：B+Tree的非葉子節(jié)點(diǎn)只存儲(chǔ)鍵值信息，那么每一頁(yè)能存儲(chǔ)更多的索引，樹(shù)的高度被壓縮到很低，磁盤IO次數(shù)更小，一般情況下2~4次IO，即可查詢到想要的記錄。
而且因?yàn)楸頂?shù)據(jù)都是順序存儲(chǔ)在B+Tree結(jié)構(gòu)的葉子節(jié)點(diǎn)，所以對(duì)于范圍查找很友好，效率高！
面試官考點(diǎn)之索引是加速查詢，那么是否應(yīng)該給表盡可能建立多的索引列？
雖然索引的優(yōu)勢(shì)是加快查詢效率，減少磁盤IO次數(shù)，但是盲目創(chuàng)建過(guò)多索引，大大增加了維護(hù)索引的時(shí)間成本和空間成本。
首先說(shuō)一下索引的好處
1、減少IO次數(shù)，提高-檢索效率
2、降低數(shù)據(jù)排序成本，可以減少CPU消耗
時(shí)間成本
因?yàn)樗饕怯行虻目焖俨檎医Y(jié)構(gòu)，要維護(hù)索引的這個(gè)快速查找且有序特性，需要不斷的進(jìn)行調(diào)整，而調(diào)整就需要時(shí)間成本。
創(chuàng)建索引和維護(hù)索引要耗費(fèi)時(shí)間，當(dāng)對(duì)表中的數(shù)據(jù)進(jìn)行增加、刪除和修改的時(shí)候，索引也要?jiǎng)討B(tài)地維護(hù)，這樣就降低了數(shù)據(jù)的維護(hù)速度。
而且這種時(shí)間成本隨著數(shù)據(jù)量的增加而增加！
空間成本
其次，每一個(gè)索引都是一棵B+Tree，保存索引和指向?qū)嶓w表的引用，需要占據(jù)空間。
如果建立的是聚簇索引，數(shù)據(jù)和主鍵都保存在索引文件中，則需要更大的空間成本。
敬請(qǐng)期待囧囧小白索引二面內(nèi)容！
更多精彩內(nèi)容，歡迎關(guān)注微信公眾號(hào)：囧么肥事 （或搜索：jiongmefeishi）
