01

為啥BAT大廠，在數(shù)據(jù)庫上都喜歡深入的問索引呢？

一線大廠，是很多人夢寐以求的盛典天堂。因為存在的無限的可能，可以幫你實現(xiàn)自己的遠大抱負。大平臺機會、視野、格局往往都比小廠多很多。但隨之而來也是那高挑的技術門檻需等你邁過。好事物大家都喜歡，但畢竟僧多粥少。外加任務有難度，如果你沒過硬的本領，那很難踏入平臺，領會一覽眾山小的風采。不知你心里有沒有小九九？

大廠產(chǎn)品大多數(shù)都成型很久，數(shù)據(jù)庫里面存儲的數(shù)據(jù)都以海量計算，如何在這種規(guī)模下的數(shù)據(jù)中做到快速篩選呢？那就需要你來答。

大家思路肯定和我一樣，話不多說，加索引再說！索引為的就是提高數(shù)據(jù)的檢索效率，進而減少請求的響應時間。

這時，有內(nèi)涵的人可能會反問你啦？

那你說說索引有哪些類型？索引底層實現(xiàn)是什么結構？B+Tree的優(yōu)點？聚簇索引和非聚簇的區(qū)別？索引一次讀讀取多少數(shù)據(jù)合適？為什么說索引會降低插入、刪除、修改等維護任務的速度？

這一套組合拳，可能虐的你是體無完膚。讓人招教不住，心理一萬個xxx省略。送他一個微笑，然后再尷尬而不失優(yōu)雅的離去。

大家可能都知道查詢慢了加索引，那為啥加？在哪些字段上加？以及索引的數(shù)據(jù)結構特點。索引優(yōu)化、優(yōu)點啥的都比較模糊或者不知道。

今天將是對索引來一次靈魂的拷問，在進一步對索引優(yōu)化、常見大廠面試問題、SQL優(yōu)化等內(nèi)容進行分享。這是個大工程，大家得關注再看。深，那就得深出高度。MOG！太深啦

02

用索引，那你得知道索引是什么？

百度百科定義：索引是數(shù)據(jù)表中一列或多列的值進行排序的一種數(shù)據(jù)結構

故此，索引本質就是數(shù)據(jù)結構。這也是為什么每次數(shù)據(jù)表建立索引都需要設置在列字段上的原因。那常見數(shù)據(jù)結構有哪些？

常見數(shù)據(jù)結構大致可分為三大類，如下所示

• 線性表：順序表、鏈表、棧和隊列；

• 樹結構：二叉樹，堆、線索二叉樹、紅黑樹、B-Tree等；

• 圖存儲結構

但在數(shù)據(jù)庫中常用數(shù)據(jù)結構為B+Tree、Hash索引。

對于此，有人可能覺得有了Hash和那么多樹結構（紅黑樹、B樹、完全平衡二叉（AVL）樹、B+樹），為啥Mysql唯獨喜歡B+樹？

請聽如下分解：

首先上場的是頑固不變Hash索引，這Hash索引又是什么？

哈希索引(hash index)基于哈希表實現(xiàn)，只有精確匹配索引所有列的查詢才能生效額。切記！切記！切記！

哈希的思路很簡單，以鍵-值（ key-value ）存儲數(shù)據(jù)的結構，對于待查找每一行的數(shù)據(jù)值,用一個哈希函數(shù)把數(shù)據(jù)值換算成一個確定的位置即  key，位置就是哈希碼，并且不同鍵值的行計算出來的哈希碼也不一樣。然后在 value 上存放每個數(shù)據(jù)行的指針。

對這樣的索引結構，執(zhí)行如下sql語句的過程是什么呢？

select * from nezha where name='lianhua'

MySQL首先計算'lianhua'的哈希值，并使用該值尋找對應的記錄指針。然后根據(jù)指針尋找對應的數(shù)據(jù)，最后一步是比較讀取的值是否為'lianhua', 從而來確保就是要查找的行。

那如果改變?yōu)榉秶圆檎揖蜁嬖趩栴}。還記得上面的切記嗎？因為它不支持范圍匹配，只支持等值匹配。例如：

select * from nezha where name like '%lianhua'

那像Hash這種等值查詢還有哪些場景？

Hash故名思議體現(xiàn)的就是（key-value）結構。所以像 Redis、Memcached 及其他一些 NoSQL 引擎（如 Memory）。

那有沒有既能快速查找，又可以支持范圍型查找呢？

自然有，有序數(shù)組在等值查詢和范圍查詢場景中的性能就都非常OK，足以滿足你的口味。

那它就好的沒天理啦？不，世上沒得十全十美的！

有序數(shù)組索引只適用于靜態(tài)存儲引擎，因為數(shù)組的空間必須是連續(xù)的，這就造成數(shù)組在內(nèi)存中分配空間時必須找到一塊連續(xù)的內(nèi)存空間。所以新增、刪除、修改數(shù)據(jù)時就會改變它的結構。

一下掉入無底洞，這在業(yè)務場景上怎樣使用？

靜態(tài)數(shù)據(jù)簡單點可以理解為不會在變化的數(shù)據(jù)，那你就可以用于歷史歸檔性的業(yè)務。比如你去年酷狗歌單、每上月的支付記錄等，這類不會再修改的數(shù)據(jù)。

接下來上場的是層次不齊的樹結構

樹結構基礎就是普通二叉樹，其它樹結構都是基于它演進產(chǎn)生。二叉樹會根據(jù)元素值的大小來創(chuàng)建樹形結構。所以它是有序的，并支持范圍查找。具體可查看數(shù)據(jù)結構相關書籍。

但普通二叉樹，有個問題，就是當元素是遞增或遞減時，它就會退化為線性表。

為了解決這個問題，就出現(xiàn)了我們的完全平衡二叉樹。可為何數(shù)據(jù)庫沒選擇它呢？

數(shù)據(jù)庫操作都是在內(nèi)存里面完成的，但最終還是要落地到磁盤。如果數(shù)據(jù)多了，樹會變得很高。然而查詢數(shù)據(jù)時，那都是從磁盤里面把數(shù)據(jù)讀取出來放入到內(nèi)存中。這樣I/O操作成本就會隨著樹的高度而增加。這也是常說完全平衡二叉樹具有高瘦特點。

好像女孩子都喜歡這樣的吧！

一般為節(jié)約成本，很多公司服務器采用的還是機械硬盤，這樣一次千萬級別的查詢差不多就要10秒，這還不算網(wǎng)絡傳輸、業(yè)務處理、CPU的執(zhí)行時間，一但匯總那誰頂?shù)米。?

那這怎么解決呢？不可能一直讓讓它變高吧! 可使用B-Tree。

B-Tree的特征就是矮胖，也稱為多叉樹，就是在樹的同一高度上開辟多個分叉來容納元素。從而樹在橫向上面變寬了。這樣減少了磁盤I/O的查詢查找次數(shù)，從而提升了效率。

B-Tree的特點簡寫：

• 每個節(jié)點中的元素（關鍵字）從小到大排列。

• 每個節(jié)點都保存有數(shù)據(jù)

那為什么最終數(shù)據(jù)庫選擇了B+Tree，而不是B-Tree呢？

B+Tree自然保持了B-Tree的矮胖特征，但它還做了升級的處理。就是讓葉子節(jié)點保存數(shù)據(jù)，而非葉子節(jié)點保存關鍵字即可，并且會有指針指向下一個葉子節(jié)點。這樣的好處是為了提高范圍查找的效率。找到數(shù)據(jù)后直接根據(jù)指針向后讀取即可，而B-Tree就不行，當它讀取下一個數(shù)據(jù)，還需要再一次的進行索引樹的查找。

B+Tree特點：

• 所有的非葉子節(jié)點只存儲關鍵字信息

• 只有葉子節(jié)點存儲數(shù)據(jù)

• 所有葉子節(jié)點之間都有一個鏈指針

小結：最終MySQL選用B+Tree作為索引，從而提高檢索索引時的磁盤IO效率，并且提高范圍查詢的效率，整個B+樹里的元素也是有序的。因為B+Tree默認就是按照主鍵索引來構建的樹結構。那你說呢？

03

索引是怎么構建的？

開發(fā)過程中，MySQL都首先B+Tree。在MySQL下還擁有Hash索引，也就是它擁有2大索引類型。具體選擇用什么，可在創(chuàng)建表時進行選擇。

那這索引到底是怎么創(chuàng)建出來的？

那還得分情況而定，分為以下2種

建表建索引

創(chuàng)建表的時候，先把索引字段建立好。如：

 create table nezha(id int unsigned   AUTO_INCREMENT PRIMARY KEY, phone int not null,name varchar(16),index (phone))engine=InnoDB;

當添加數(shù)據(jù)時，數(shù)據(jù)庫就會自動先去創(chuàng)建好索引結構，然后創(chuàng)建數(shù)據(jù)。最終在落地到磁盤上。

先建表，后添索引

這種情況需要注意，因為先建表，那可能你數(shù)據(jù)表已經(jīng)擁有了大量數(shù)據(jù)，這時候你在添加索引，那你的整個數(shù)據(jù)庫肯定會阻塞，因為數(shù)據(jù)庫需要根據(jù)表中數(shù)據(jù)建立索引，這都是由數(shù)據(jù)庫后臺線程來完成。

這也是為什么線上數(shù)據(jù)庫不要輕易變動索引，需根據(jù)用戶低峰時間來操作。所以索引創(chuàng)建過多，那也算是需要耗費資源的。

一般還需要維護表和索引，你這里有什么建議嗎？不妨留言說說你的提議，優(yōu)化就留到下次。

所以當你的大表需要導入到其它數(shù)據(jù)庫時，需在新數(shù)據(jù)庫上先關閉索引，然后再添上索引，要不然效率就太低了。

04

索引的表現(xiàn)類型代表作有哪些?

乖乖，索引還有表現(xiàn)種類，這神馬情況？

大家都知道B+Tree、Hash索引，但這些都底層實現(xiàn)的數(shù)據(jù)結構，而表現(xiàn)種類在明面上，我們常說的，例如：聚簇索引、非聚簇索引等，都包含了對應的數(shù)據(jù)結構。

問最多算聚簇索引、非聚簇索引，那它們是什么呢？

聚簇索引：索引和數(shù)據(jù)都存儲在一起，代表作Innodb

非聚簇索引：索引和數(shù)據(jù)分開存儲，代表作MyIASM

上述的特性，也和它們的物理存儲文件有關系。文件放在數(shù)據(jù)庫安裝目錄下的data目錄中

/mysql-57/data/mysql

MyISAM結構如下：

.frm為表結構文件，存儲像create alter等語句    .MYD為存儲數(shù)據(jù)文件   .MYI為存儲索引文件

InnoDb結構如下：

.frm為表結構文件，.ibd為數(shù)據(jù)+索引文件

在InnoDB存儲引擎中,就一定都是聚簇索引嗎？

并不是，只有主鍵索引被稱為聚簇索引（ clusteredindex ）。除開主鍵以外的字段上創(chuàng)建的索引被稱為非主鍵索引，非主鍵索引也被稱為二級索引（ secondary index ）。

注：現(xiàn)在你該知道，為啥面試都不問你什么唯一、普通、聯(lián)合索引了吧，那都是屬于二級索引呢

那這兩者之間有什么區(qū)別嗎？區(qū)別在非主鍵索引的葉子節(jié)點內(nèi)容是主鍵，當找到主鍵后，還需要根據(jù)主鍵再一次的進行索引樹的查找，這個過程稱之為回表。

例如：

如果語句是 select * from nezha  where ID=7 ，即主鍵查詢方式，那它只需搜索 ID 這棵 B+ 樹；

如果語句是 select * from nezha  where name = '哪吒' ，即普通索引查詢方式，則需要先搜索 name 索引樹，得到 ID的值為 7，再到 ID 索引樹搜索一次。這就是所謂的回表。

那這個問題怎么解決呀！

內(nèi)心獨白：哎呀！咋這么多問題，煩不煩。

這個好辦，剛才我們是 select * ，查詢所有記錄，如果查詢字段上只出現(xiàn)主鍵索引與創(chuàng)建索引的字段，那就不需要回表了。因為走二級索引時，就已經(jīng)包含了你需要的字段列啦，那就不需要在回表了。這就被稱之為索引覆蓋，即索引已經(jīng)包含了查詢操作的值。

這也是為什么，當有多個字段需創(chuàng)建索引時，會創(chuàng)建聯(lián)合索引，也是為了更好支持索引覆蓋。

瞬間飛過，"我怎么這么好看，這么好看怎么辦"

05

數(shù)據(jù)庫內(nèi)部利用索引是如何讀取數(shù)據(jù)的？

搞了這么久，那這個索引查找數(shù)據(jù)的時候，是怎么個讀取原理又是什么？

那這首先得說數(shù)據(jù)庫中的讀取數(shù)據(jù)單位，數(shù)據(jù)庫中的數(shù)據(jù)是按照頁讀取的。默認一頁的數(shù)據(jù)為16KB。而磁盤塊（OS）默認為4KB

 show global variables like 'innodb_page%';

那索引和數(shù)據(jù)都保存在節(jié)點里面，這個數(shù)據(jù)怎么個讀法？

上面說到，數(shù)據(jù)庫讀取數(shù)據(jù)是根據(jù)頁為單位，并且讀的數(shù)據(jù)不滿足1頁或超過1頁，那么也會讀滿1頁。這也叫做預讀

也就是說節(jié)點讀取數(shù)據(jù)的大小應該控制在1頁、2頁、3頁、4頁等倍數(shù)頁大小最為合適。

那你說說這個頁吧！

每個數(shù)據(jù)頁中的數(shù)據(jù)，采用單向鏈表的形式進行連接。

各個頁之間采用雙向鏈表鏈接。

查找數(shù)據(jù)時是根據(jù)頁內(nèi)分組定義的。首先在插入數(shù)據(jù)時就會根據(jù)主鍵大小做好排序結構，并按照最大和最小進行分組。

最小虛擬數(shù)據(jù)獨自一組，它擁有一條數(shù)據(jù)，就是最小數(shù)據(jù)。然后剩下的數(shù)據(jù)再分成一組，即最大數(shù)據(jù)為另一組。當進行數(shù)據(jù)插入的時，都是先插入到最大數(shù)據(jù)組，當最大數(shù)據(jù)組裝滿后在進行分裂。

分組確立后，在進行數(shù)據(jù)查找的時就是根據(jù)二分查找法確定對應數(shù)據(jù)所在的槽位置，然后在使用記錄頭信息的next_record一條條進行查找。

當以(非主鍵)作為搜索條件：只能從最小虛擬數(shù)據(jù)記錄，開始依次遍歷單鏈表中的每條記錄。

所以，當寫

 select * from nezha where name='nezha'

 這樣沒有進行任何優(yōu)化的sql語句，默認會這樣做：

• 讀取記錄所在頁的范圍

• 根據(jù)雙向鏈表，找到所在頁

• 從所在頁中查找相應的記錄

• 由于不是主鍵查詢，就遍歷所在頁的單鏈表

06

索引就不命中？前提你得知道規(guī)則

使用索引當中，最核心的就是最左匹配原則，索引命中都是根據(jù)它來定義的。

最左匹配原則：

• 索引可以的簡單如單列 (a)，也可以復雜如多列 (a,b,c,d)，即聯(lián)合索引。

• 如果是聯(lián)合索引，那么key也由多個列組成，同時，索引只能用于查找key是否存在（相等），遇到范圍查詢 (>、<、BETWEEN、LIKE)等就不能進一步匹配了，后續(xù)退化為線性查找。因此，列的排列順序決定了可命中索引的列數(shù)。

• 索引列不能是表達式的一部分，那樣無法命中索引，例如

 ：SELECT * FROM nezha WHERE id + 1 = 5; date(create_time)='2020-03-05' 

例如：

• 如有索引 (a,b,c,d)，查詢條件 a=7 and b=8 and c>15 and d=32，則會在每個節(jié)點依次命中a、b、c，無法命中d。(c已經(jīng)是范圍查詢了，d就沒辦法進行對比查找了)

總結：

索引在數(shù)據(jù)庫中是一個非常重要的內(nèi)容！

• 最左前綴匹配原則。這是非常重要的原則，SQL查詢都是基于它來。MySQL會一直向右匹配，直到遇到范圍查詢 （>,<,BETWEEN,LIKE）就停止匹配。

• 頁也需要了解下，這個是數(shù)據(jù)庫在內(nèi)部的工作機制。

• 索引的表現(xiàn)形式針對于不同的存儲引擎，表現(xiàn)也不一樣，并且2者之間的存儲引擎區(qū)別也要掌握了解

• 索引創(chuàng)建方式來自于建表前還是建表后。重點都是數(shù)據(jù)庫再用后臺線程創(chuàng)建與維護索引

• B+Tree和Hash這2個特點還是需要注意，并且它們之間區(qū)別還未細講。后面會針對面試問題，給大家補上來。

  
  

免責聲明：本文內(nèi)容由21ic獲得授權后發(fā)布，版權歸原作者所有，本平臺僅提供信息存儲服務。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！