面試官考點(diǎn)之索引是什么？

前言

有位朋友去阿里面試，他說(shuō)面試官給了幾條查詢(xún)SQL，問(wèn):需要執(zhí)行幾次樹(shù)搜索操作？我朋友當(dāng)時(shí)是有點(diǎn)懵的，后來(lái)冷靜思考，才發(fā)現(xiàn)就是考索引的幾個(gè)基礎(chǔ)知識(shí)點(diǎn)~~ 本文我們分九個(gè)索引知識(shí)點(diǎn)，一起來(lái)探討一下

一、面試官考點(diǎn)之索引是什么？

索引是一種能提高數(shù)據(jù)庫(kù)查詢(xún)效率的數(shù)據(jù)結(jié)構(gòu)。它可以比作一本字典的目錄，可以幫你快速找到對(duì)應(yīng)的記錄。

索引一般存儲(chǔ)在磁盤(pán)的文件中，它是占用物理空間的。

正所謂水能載舟，也能覆舟。適當(dāng)?shù)乃饕芴岣卟樵?xún)效率，過(guò)多的索引會(huì)影響數(shù)據(jù)庫(kù)表的插入和更新功能。

二、索引有哪些類(lèi)型類(lèi)型

數(shù)據(jù)結(jié)構(gòu)維度

B+樹(shù)索引：所有數(shù)據(jù)存儲(chǔ)在葉子節(jié)點(diǎn)，復(fù)雜度為O(logn)，適合范圍查詢(xún)。

哈希索引: 適合等值查詢(xún)，檢索效率高，一次到位。

全文索引：MyISAM和InnoDB中都支持使用全文索引，一般在文本類(lèi)型char,text,varchar類(lèi)型上創(chuàng)建。

R-Tree索引: 用來(lái)對(duì)GIS數(shù)據(jù)類(lèi)型創(chuàng)建SPATIAL索引

物理存儲(chǔ)維度

聚集索引：聚集索引就是以主鍵創(chuàng)建的索引，在葉子節(jié)點(diǎn)存儲(chǔ)的是表中的數(shù)據(jù)。

非聚集索引：非聚集索引就是以非主鍵創(chuàng)建的索引，在葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵和索引列。

邏輯維度

主鍵索引：一種特殊的唯一索引，不允許有空值。

普通索引：MySQL中基本索引類(lèi)型，允許空值和重復(fù)值。

聯(lián)合索引：多個(gè)字段創(chuàng)建的索引，使用時(shí)遵循最左前綴原則。

唯一索引：索引列中的值必須是唯一的，但是允許為空值。

空間索引：MySQL5.7之后支持空間索引，在空間索引這方面遵循OpenGIS幾何數(shù)據(jù)模型規(guī)則。

三、面試官考點(diǎn)之為什么選擇B+樹(shù)作為索引結(jié)構(gòu)

可以從幾個(gè)維度去看這個(gè)問(wèn)題，查詢(xún)是否夠快，效率是否穩(wěn)定，存儲(chǔ)數(shù)據(jù)多少，以及查找磁盤(pán)次數(shù)等等。為什么不是哈希結(jié)構(gòu)？為什么不是二叉樹(shù)，為什么不是平衡二叉樹(shù)，為什么不是B樹(shù)，而偏偏是B+樹(shù)呢？

我們寫(xiě)業(yè)務(wù)SQL查詢(xún)時(shí)，大多數(shù)情況下，都是范圍查詢(xún)的，如一下SQL

select*fromemployeewhereagebetween18and28;

為什么不使用哈希結(jié)構(gòu)？

我們知道哈希結(jié)構(gòu)，類(lèi)似k-v結(jié)構(gòu)，也就是，key和value是一對(duì)一關(guān)系。它用于等值查詢(xún)還可以，但是范圍查詢(xún)它是無(wú)能為力的哦。

為什么不使用二叉樹(shù)呢？

先回憶下二叉樹(shù)相關(guān)知識(shí)啦~ 所謂二叉樹(shù)，特點(diǎn)如下：

每個(gè)結(jié)點(diǎn)最多兩個(gè)子樹(shù)，分別稱(chēng)為左子樹(shù)和右子樹(shù)。

左子節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)的值，當(dāng)前節(jié)點(diǎn)值小于右子節(jié)點(diǎn)值

頂端的節(jié)點(diǎn)稱(chēng)為跟節(jié)點(diǎn)，沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)值稱(chēng)為葉子節(jié)點(diǎn)。

我們腦海中，很容易就浮現(xiàn)出這種二叉樹(shù)結(jié)構(gòu)圖：

但是呢，有些特殊二叉樹(shù)，它可能這樣的哦：

如果二叉樹(shù)特殊化為一個(gè)鏈表，相當(dāng)于全表掃描。那么還要索引干嘛呀？因此，一般二叉樹(shù)不適合作為索引結(jié)構(gòu)。

為什么不使用平衡二叉樹(shù)呢？

平衡二叉樹(shù)特點(diǎn)：它也是一顆二叉查找樹(shù)，任何節(jié)點(diǎn)的兩個(gè)子樹(shù)高度最大差為1。所以就不會(huì)出現(xiàn)特殊化一個(gè)鏈表的情況啦。

但是呢：

平衡二叉樹(shù)插入或者更新是，需要左旋右旋維持平衡，維護(hù)代價(jià)大

如果數(shù)量多的話(huà)，樹(shù)的高度會(huì)很高。因?yàn)閿?shù)據(jù)是存在磁盤(pán)的，以它作為索引結(jié)構(gòu)，每次從磁盤(pán)讀取一個(gè)節(jié)點(diǎn)，操作IO的次數(shù)就多啦。

為什么不使用B樹(shù)呢？

數(shù)據(jù)量大的話(huà)，平衡二叉樹(shù)的高度會(huì)很高，會(huì)增加IO嘛。那為什么不選擇同樣數(shù)據(jù)量，高度更矮的B樹(shù)呢？

B樹(shù)相對(duì)于平衡二叉樹(shù)，就可以存儲(chǔ)更多的數(shù)據(jù)，高度更低。但是最后為甚選擇B+樹(shù)呢？因?yàn)锽+樹(shù)是B樹(shù)的升級(jí)版：

B+樹(shù)非葉子節(jié)點(diǎn)上是不存儲(chǔ)數(shù)據(jù)的，僅存儲(chǔ)鍵值，而B(niǎo)樹(shù)節(jié)點(diǎn)中不僅存儲(chǔ)鍵值，也會(huì)存儲(chǔ)數(shù)據(jù)。innodb中頁(yè)的默認(rèn)大小是16KB，如果不存儲(chǔ)數(shù)據(jù)，那么就會(huì)存儲(chǔ)更多的鍵值，相應(yīng)的樹(shù)的階數(shù)（節(jié)點(diǎn)的子節(jié)點(diǎn)樹(shù)）就會(huì)更大，樹(shù)就會(huì)更矮更胖，如此一來(lái)我們查找數(shù)據(jù)進(jìn)行磁盤(pán)的IO次數(shù)有會(huì)再次減少，數(shù)據(jù)查詢(xún)的效率也會(huì)更快。

B+樹(shù)索引的所有數(shù)據(jù)均存儲(chǔ)在葉子節(jié)點(diǎn)，而且數(shù)據(jù)是按照順序排列的，鏈表連著的。那么B+樹(shù)使得范圍查找，排序查找，分組查找以及去重查找變得異常簡(jiǎn)單。

四、面試官考點(diǎn)之一次B+樹(shù)索引搜索過(guò)程

面試官：假設(shè)有以下表結(jié)構(gòu)，并且有這幾條數(shù)據(jù)

CREATETABLE`employee`( `id`int(11)NOTNULL, `name`varchar(255)DEFAULTNULL, `age`int(11)DEFAULTNULL, `date`datetimeDEFAULTNULL, `sex`int(1)DEFAULTNULL, PRIMARYKEY(`id`), KEY`idx_age`(`age`)USINGBTREE )ENGINE=InnoDBDEFAULTCHARSET=utf8; insertintoemployeevalues(100,'小倫',43,'2021-01-20','0'); insertintoemployeevalues(200,'俊杰',48,'2021-01-21','0'); insertintoemployeevalues(300,'紫琪',36,'2020-01-21','1'); insertintoemployeevalues(400,'立紅',32,'2020-01-21','0'); insertintoemployeevalues(500,'易迅',37,'2020-01-21','1'); insertintoemployeevalues(600,'小軍',49,'2021-01-21','0'); insertintoemployeevalues(700,'小燕',28,'2021-01-21','1');

面試官：如果執(zhí)行以下的查詢(xún)SQL，需要執(zhí)行幾次的樹(shù)搜索操作？可以畫(huà)下對(duì)應(yīng)的索引結(jié)構(gòu)圖~

select*fromTemployeewhereage=32;

解析：其實(shí)這個(gè)，面試官就是考察候選人是否熟悉B+樹(shù)索引結(jié)構(gòu)圖。可以像醬紫回答~

先畫(huà)出idx_age索引的索引結(jié)構(gòu)圖，大概如下：

再畫(huà)出id主鍵索引，我們先畫(huà)出聚族索引結(jié)構(gòu)圖，如下：

因此，這條 SQL 查詢(xún)語(yǔ)句執(zhí)行大概流程就是醬紫：

搜索idx_age索引樹(shù)，將磁盤(pán)塊1加載到內(nèi)存，由于32<37,搜索左路分支，到磁盤(pán)尋址磁盤(pán)塊2。

將磁盤(pán)塊2加載到內(nèi)存中，在內(nèi)存繼續(xù)遍歷，找到age=32的記錄，取得id = 400.

拿到id=400后，回到id主鍵索引樹(shù)。

搜索id主鍵索引樹(shù)，將磁盤(pán)塊1加載內(nèi)存，在內(nèi)存遍歷，找到了400，但是B+樹(shù)索引非葉子節(jié)點(diǎn)是不保存數(shù)據(jù)的。索引會(huì)繼續(xù)搜索400的右分支，到磁盤(pán)尋址磁盤(pán)塊3.

將磁盤(pán)塊3加載內(nèi)存，在內(nèi)存遍歷，找到id=400的記錄，拿到R4這一行的數(shù)據(jù)，好的，大功告成。

因此，這個(gè)SQL查詢(xún)，執(zhí)行了幾次樹(shù)的搜索操作，是不是一步了然了呀。特別的，在idx_age二級(jí)索引樹(shù)找到主鍵id后，回到id主鍵索引搜索的過(guò)程,就稱(chēng)為回表。

什么是回表？拿到主鍵再回到主鍵索引查詢(xún)的過(guò)程，就叫做回表

五、面試官考點(diǎn)之覆蓋索引

面試官：如果不用select *, 而是使用select id,age，以上的題目執(zhí)行了幾次樹(shù)搜索操作呢？

解析：這個(gè)問(wèn)題，主要考察候選人的覆蓋索引知識(shí)點(diǎn)。回到idx_age索引樹(shù)，你可以發(fā)現(xiàn)查詢(xún)選項(xiàng)id和age都在葉子節(jié)點(diǎn)上了。因此，可以直接提供查詢(xún)結(jié)果啦，根本就不需要再回表了~

覆蓋索引：在查詢(xún)的數(shù)據(jù)列里面，不需要回表去查，直接從索引列就能取到想要的結(jié)果。換句話(huà)說(shuō)，你SQL用到的索引列數(shù)據(jù)，覆蓋了查詢(xún)結(jié)果的列，就算上覆蓋索引了。

所以，相對(duì)于上個(gè)問(wèn)題，就是省去了回表的樹(shù)搜索操作。

六、面試官考點(diǎn)之索引失效

面試官：如果我現(xiàn)在給name字段加上普通索引，然后用個(gè)like模糊搜索，那會(huì)執(zhí)行多少次查詢(xún)呢？SQL如下：

select*fromemployeewherenamelike'%杰倫%';

解析：這里考察的知識(shí)點(diǎn)就是，like是否會(huì)導(dǎo)致不走索引，看先該SQL的explain執(zhí)行計(jì)劃吧。其實(shí)like 模糊搜索，會(huì)導(dǎo)致不走索引的，如下：

因此，這條SQL最后就全表掃描啦~日常開(kāi)發(fā)中，這幾種騷操作都可能會(huì)導(dǎo)致索引失效，如下：

查詢(xún)條件包含or，可能導(dǎo)致索引失效

如何字段類(lèi)型是字符串，where時(shí)一定用引號(hào)括起來(lái)，否則索引失效

like通配符可能導(dǎo)致索引失效。

聯(lián)合索引，查詢(xún)時(shí)的條件列不是聯(lián)合索引中的第一個(gè)列，索引失效。

在索引列上使用mysql的內(nèi)置函數(shù)，索引失效。

對(duì)索引列運(yùn)算（如，+、-、*、/），索引失效。

索引字段上使用（！= 或者 < >，not in）時(shí)，可能會(huì)導(dǎo)致索引失效。

索引字段上使用is null， is not null，可能導(dǎo)致索引失效。

左連接查詢(xún)或者右連接查詢(xún)查詢(xún)關(guān)聯(lián)的字段編碼格式不一樣，可能導(dǎo)致索引失效。

mysql估計(jì)使用全表掃描要比使用索引快,則不使用索引。

七、面試官考點(diǎn)聯(lián)合索引之最左前綴原則

面試官：如果我現(xiàn)在給name,age字段加上聯(lián)合索引索引，以下SQL執(zhí)行多少次樹(shù)搜索呢？先畫(huà)下索引樹(shù)？

select*fromemployeewherenamelike'小%'orderbyagedesc;

解析：這里考察聯(lián)合索引的最左前綴原則以及l(fā)ike是否中索引的知識(shí)點(diǎn)。組合索引樹(shù)示意圖大概如下：

聯(lián)合索引項(xiàng)是先按姓名name從小到大排序，如果名字name相同，則按年齡age從小到大排序。面試官要求查所有名字第一個(gè)字是“小”的人，SQL的like '小%'是可以用上idx_name_age聯(lián)合索引的。

該查詢(xún)會(huì)沿著idx_name_age索引樹(shù)，找到第一個(gè)字是小的索引值，因此依次找到小軍、小倫、小燕、，分別拿到Id=600、100、700，然后回三次表，去找對(duì)應(yīng)的記錄。這里面的最左前綴小，就是字符串索引的最左M個(gè)字符。實(shí)際上，

這個(gè)最左前綴可以是聯(lián)合索引的最左N個(gè)字段。比如組合索引（a,b,c）可以相當(dāng)于建了（a），（a,b）,(a,b,c)三個(gè)索引，大大提高了索引復(fù)用能力。

最左前綴也可以是字符串索引的最左M個(gè)字符。

八、面試官考點(diǎn)之索引下推

面試官：我們還是居于組合索引 idx_name_age，以下這個(gè)SQL執(zhí)行幾次樹(shù)搜索呢？

select*fromemployeewherenamelike'小%'andage=28andsex='0';

解析：這里考察索引下推的知識(shí)點(diǎn)，如果是Mysql5.6之前，在idx_name_age索引樹(shù)，找出所有名字第一個(gè)字是“小”的人，拿到它們的主鍵id，然后回表找出數(shù)據(jù)行，再去對(duì)比年齡和性別等其他字段。如圖：

有些朋友可能覺(jué)得奇怪，（name,age)不是聯(lián)合索引嘛？為什么選出包含“小”字后，不再順便看下年齡age再回表呢，不是更高效嘛？所以呀，MySQL 5.6 就引入了索引下推優(yōu)化，可以在索引遍歷過(guò)程中，對(duì)索引中包含的字段先做判斷，直接過(guò)濾掉不滿(mǎn)足條件的記錄，減少回表次數(shù)。

因此，MySQL5.6版本之后，選出包含“小”字后，順表過(guò)濾age=28，,所以就只需一次回表。

九、 面試官考點(diǎn)之大表添加索引

面試官：如果一張表數(shù)據(jù)量級(jí)是千萬(wàn)級(jí)別以上的，那么，給這張表添加索引，你需要怎么做呢？

解析：我們需要知道一點(diǎn)，給表添加索引的時(shí)候，是會(huì)對(duì)表加鎖的。如果不謹(jǐn)慎操作，有可能出現(xiàn)生產(chǎn)事故的?？梢詤⒖家韵路椒ǎ?/p>

1.先創(chuàng)建一張跟原表A數(shù)據(jù)結(jié)構(gòu)相同的新表B。

2.在新表B添加需要加上的新索引。

3.把原表A數(shù)據(jù)導(dǎo)到新表B

4.rename新表B為原表的表名A，原表A換別的表名；

總結(jié)與練習(xí)

本文主要講解了索引的9大關(guān)鍵知識(shí)點(diǎn)，希望對(duì)大家有幫助。接下來(lái)呢，給大家出一道，有關(guān)于我最近業(yè)務(wù)開(kāi)發(fā)遇到的加索引SQL，看下大家是怎么回答的，題目如下：

select*fromAwheretype='1'andstatus='s'orderbycreate_timedesc;

假設(shè)type有9種類(lèi)型，區(qū)分度性還算可以，status的區(qū)分度不高（有3種類(lèi)型），那么你是如何加索引呢？

是給type加單索引

還是（type，status，create_time）聯(lián)合索引

還是（type，create_time）聯(lián)合索引呢？

責(zé)任編輯：lq