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