終于字節(jié)約面，可惜沒把握住

大家好，我是小林。

分享一篇字節(jié)后端開發(fā)校招一面經(jīng)，同學(xué)反饋面試官人很 nice，雖然問的很細(xì)節(jié)，但是會(huì)引導(dǎo)問題方向，但是可惜自己沒把握住，深問一點(diǎn)細(xì)節(jié)的，就不會(huì)了。

這一面主要是拷打基礎(chǔ)方向，重點(diǎn)拷打了網(wǎng)絡(luò)IO、Linux 操作系統(tǒng)、網(wǎng)絡(luò)協(xié)議、mysql、算法。

項(xiàng)目相關(guān)

epoll 的工作原理？

先用 epoll_create 創(chuàng)建一個(gè) epoll 對象 epfd，再通過 epoll_ctl 將需要監(jiān)視的 socket 添加到epfd中，最后調(diào)用 epoll_wait 等待數(shù)據(jù)，當(dāng)epoll_wait返回后，就可以遍歷它返回的事件列表，然后根據(jù)事件類型做出相應(yīng)的處理。

ints=socket(AF_INET,SOCK_STREAM,0);
bind(s,...);
listen(s,...)

intepfd=epoll_create(...);
epoll_ctl(epfd,...);//將所有需要監(jiān)聽的socket添加到epfd中

while(1){
intn=epoll_wait(...);
for(接收到數(shù)據(jù)的socket){
//處理
}
}

epoll、select、poll的區(qū)別？

select 實(shí)現(xiàn)多路復(fù)用的方式是，將已連接的 Socket 都放到一個(gè)文件描述符集合，然后調(diào)用 select 函數(shù)將文件描述符集合拷貝到內(nèi)核里，讓內(nèi)核來檢查是否有網(wǎng)絡(luò)事件產(chǎn)生，檢查的方式很粗暴，就是通過遍歷文件描述符集合的方式，當(dāng)檢查到有事件產(chǎn)生后，將此 Socket 標(biāo)記為可讀或可寫， 接著再把整個(gè)文件描述符集合拷貝回用戶態(tài)里，然后用戶態(tài)還需要再通過遍歷的方法找到可讀或可寫的 Socket，然后再對其處理。

所以，對于 select 這種方式，需要進(jìn)行 2 次「遍歷」文件描述符集合，一次是在內(nèi)核態(tài)里，一個(gè)次是在用戶態(tài)里 ，而且還會(huì)發(fā)生 2 次「拷貝」文件描述符集合，先從用戶空間傳入內(nèi)核空間，由內(nèi)核修改后，再傳出到用戶空間中。

select 使用固定長度的 BitsMap，表示文件描述符集合，而且所支持的文件描述符的個(gè)數(shù)是有限制的，在 Linux 系統(tǒng)中，由內(nèi)核中的 FD_SETSIZE 限制， 默認(rèn)最大值為 1024，只能監(jiān)聽 0~1023 的文件描述符。

poll 不再用 BitsMap 來存儲(chǔ)所關(guān)注的文件描述符，取而代之用動(dòng)態(tài)數(shù)組，以鏈表形式來組織，突破了 select 的文件描述符個(gè)數(shù)限制，當(dāng)然還會(huì)受到系統(tǒng)文件描述符限制。

但是 poll 和 select 并沒有太大的本質(zhì)區(qū)別，都是使用「線性結(jié)構(gòu)」存儲(chǔ)進(jìn)程關(guān)注的 Socket 集合，因此都需要遍歷文件描述符集合來找到可讀或可寫的 Socket，時(shí)間復(fù)雜度為 O(n)，而且也需要在用戶態(tài)與內(nèi)核態(tài)之間拷貝文件描述符集合，這種方式隨著并發(fā)數(shù)上來，性能的損耗會(huì)呈指數(shù)級增長。

epoll 通過兩個(gè)方面，很好解決了 select/poll 的問題。

• 第一點(diǎn)，epoll 在內(nèi)核里使用紅黑樹來跟蹤進(jìn)程所有待檢測的文件描述字，把需要監(jiān)控的 socket 通過 epoll_ctl() 函數(shù)加入內(nèi)核中的紅黑樹里，紅黑樹是個(gè)高效的數(shù)據(jù)結(jié)構(gòu)，增刪改一般時(shí)間復(fù)雜度是 O(logn)。而 select/poll 內(nèi)核里沒有類似 epoll 紅黑樹這種保存所有待檢測的 socket 的數(shù)據(jù)結(jié)構(gòu)，所以 select/poll 每次操作時(shí)都傳入整個(gè) socket 集合給內(nèi)核，而 epoll 因?yàn)樵趦?nèi)核維護(hù)了紅黑樹，可以保存所有待檢測的 socket ，所以只需要傳入一個(gè)待檢測的 socket，減少了內(nèi)核和用戶空間大量的數(shù)據(jù)拷貝和內(nèi)存分配。

• 第二點(diǎn)， epoll 使用事件驅(qū)動(dòng)的機(jī)制，內(nèi)核里維護(hù)了一個(gè)鏈表來記錄就緒事件，當(dāng)某個(gè) socket 有事件發(fā)生時(shí)，通過回調(diào)函數(shù)內(nèi)核會(huì)將其加入到這個(gè)就緒事件列表中，當(dāng)用戶調(diào)用 epoll_wait() 函數(shù)時(shí)，只會(huì)返回有事件發(fā)生的文件描述符的個(gè)數(shù)，不需要像 select/poll 那樣輪詢掃描整個(gè) socket 集合，大大提高了檢測的效率。

可以看到 epoll 相關(guān)的接口作用：

img

epoll 的方式即使監(jiān)聽的 Socket 數(shù)量越多的時(shí)候，效率不會(huì)大幅度降低，能夠同時(shí)監(jiān)聽的 Socket 的數(shù)目也非常的多了，上限就為系統(tǒng)定義的進(jìn)程打開的最大文件描述符個(gè)數(shù)。因而，epoll 被稱為解決 C10K 問題的利器。

select線性表要從用戶態(tài)復(fù)制到內(nèi)核態(tài)，具體怎么復(fù)制的？

用戶態(tài)準(zhǔn)備一個(gè)文件描述符集合，通常是使用fd_set數(shù)據(jù)結(jié)構(gòu)來表示，該集合包含要監(jiān)視的文件描述符。調(diào)用select系統(tǒng)調(diào)用時(shí)，將該文件描述符集合作為參數(shù)傳遞給select函數(shù)。

內(nèi)核態(tài)的select函數(shù)接收到用戶態(tài)傳遞的文件描述符集合后，會(huì)在內(nèi)核中創(chuàng)建一個(gè)與用戶態(tài)相對應(yīng)的數(shù)據(jù)結(jié)構(gòu) fdset，然后將用戶空間的ufdset拷貝到內(nèi)核空間fdset。

image-20230829160943074

操作系統(tǒng)

進(jìn)程、線程、協(xié)程的概念

• 進(jìn)程（Process）：進(jìn)程是操作系統(tǒng)中的一個(gè)執(zhí)行實(shí)例，它擁有獨(dú)立的內(nèi)存空間和資源。每個(gè)進(jìn)程都是獨(dú)立運(yùn)行的，擁有自己的地址空間、文件句柄、環(huán)境變量等。進(jìn)程間通信需要通過特定的機(jī)制，如管道、消息隊(duì)列、共享內(nèi)存等。

• 線程（Thread）：線程是進(jìn)程的一部分，是在同一進(jìn)程內(nèi)并發(fā)執(zhí)行的執(zhí)行單元。不同線程共享同一進(jìn)程的內(nèi)存空間和資源，包括全局變量、堆、文件描述符等。線程可以更輕量級地創(chuàng)建、切換和銷毀，相對于進(jìn)程而言，線程間的切換開銷較小。線程之間可以通過共享內(nèi)存等機(jī)制進(jìn)行通信。

• 協(xié)程（Coroutine）：協(xié)程是一種用戶級的輕量級線程。協(xié)程由用戶控制，而不是由操作系統(tǒng)內(nèi)核控制。在協(xié)程中，執(zhí)行流可以在不同協(xié)程之間進(jìn)行切換，切換由程序員手動(dòng)控制，而不需要內(nèi)核介入。協(xié)程可以在一個(gè)線程內(nèi)實(shí)現(xiàn)并發(fā)，但無法利用多核心處理器。協(xié)程通常用于實(shí)現(xiàn)高效的異步編程和協(xié)作任務(wù)。

系統(tǒng)創(chuàng)建進(jìn)程的時(shí)候，會(huì)給進(jìn)程分配哪些資源？

會(huì)分配虛擬內(nèi)存空間、文件描述符、信號資源。

線程的資源怎么回收？

linux 線程退出有多種方式，如return，pthread_exit,pthread_cancel等；線程分為可結(jié)合的（joinable）和 分離的（detached）兩種。

• 如果沒有在創(chuàng)建線程時(shí)設(shè)置線程的屬性為PTHREAD_CREATE_DETACHED，則線程默認(rèn)是可結(jié)合的?？山Y(jié)合的線程在線程退出后不會(huì)立即釋放資源，必須要調(diào)用pthread_join來顯式的結(jié)束線程。
• 分離的線程在線程退出時(shí)系統(tǒng)會(huì)自動(dòng)回收資源。

怎么看進(jìn)程當(dāng)中有哪些線程？

使用ps命令：通過在終端中運(yùn)行ps -eLf命令，可以列出所有進(jìn)程及其對應(yīng)的線程信息。每個(gè)線程都會(huì)顯示線程ID（TID）、進(jìn)程ID（PID）、線程優(yōu)先級（PRI）、CPU占用率（%CPU）、內(nèi)存占用（%MEM）等信息。

image-20230829163916659

怎么查看網(wǎng)絡(luò)的狀態(tài)？

可以通過 netstat 命令。

image-20230829164022018

如果只想看close_wait狀態(tài)的連接，怎么看？

netstat-napt|grepclose_wait

計(jì)網(wǎng)

HTTP協(xié)議狀態(tài)碼 500 501 502 503 504分別代表什么？可以舉出具體場景嘛？

狀態(tài)碼500：

• 服務(wù)器內(nèi)部錯(cuò)誤（Internal Server Error）：表示服務(wù)器在處理請求時(shí)遇到了意外的錯(cuò)誤，無法完成請求。

• 場景：當(dāng)服務(wù)器上的應(yīng)用程序發(fā)生未處理的異常或錯(cuò)誤時(shí)，可能會(huì)返回500狀態(tài)碼。例如，如果網(wǎng)站的后端代碼出現(xiàn)了錯(cuò)誤，導(dǎo)致無法正確處理請求，服務(wù)器可能會(huì)返回500狀態(tài)碼。

狀態(tài)碼501：

• 未實(shí)現(xiàn)（Not Implemented）：表示服務(wù)器不支持客戶端請求的功能或方法。

• 場景：當(dāng)客戶端發(fā)送了一個(gè)服務(wù)器不支持的請求方法或功能時(shí)，服務(wù)器可以返回501狀態(tài)碼。例如，如果客戶端發(fā)送了一個(gè)不被服務(wù)器支持的HTTP方法，如PROPFIND，服務(wù)器可能會(huì)返回501狀態(tài)碼。

狀態(tài)碼502：

• 錯(cuò)誤網(wǎng)關(guān)（Bad Gateway）：表示服務(wù)器作為網(wǎng)關(guān)或代理，從上游服務(wù)器接收到的響應(yīng)無效。

• 場景：當(dāng)服務(wù)器作為網(wǎng)關(guān)或代理時(shí)，如果服務(wù)器從上游服務(wù)器接收到的響應(yīng)無效，可能會(huì)返回502狀態(tài)碼。例如，當(dāng)反向代理服務(wù)器無法訪問后端服務(wù)器或后端服務(wù)器返回了無效的響應(yīng)時(shí)，可能會(huì)返回502狀態(tài)碼。

狀態(tài)碼503 ：

• 服務(wù)不可用（Service Unavailable）：表示服務(wù)器暫時(shí)無法處理請求，通常是由于服務(wù)器過載或維護(hù)。

• 場景：當(dāng)服務(wù)器暫時(shí)無法處理請求時(shí)，可能會(huì)返回503狀態(tài)碼。例如，當(dāng)網(wǎng)站正在進(jìn)行維護(hù)或升級時(shí)，服務(wù)器可以返回503狀態(tài)碼來告知客戶端服務(wù)不可用。

狀態(tài)碼504 ：

• 網(wǎng)關(guān)超時(shí)（Gateway Timeout）：表示服務(wù)器作為網(wǎng)關(guān)或代理，在等待上游服務(wù)器的響應(yīng)時(shí)超時(shí)。

• 場景：當(dāng)服務(wù)器作為網(wǎng)關(guān)或代理時(shí)，在等待上游服務(wù)器的響應(yīng)時(shí)超時(shí)，可能會(huì)返回504狀態(tài)碼。例如，如果反向代理服務(wù)器在規(guī)定的超時(shí)時(shí)間內(nèi)無法從后端服務(wù)器獲取響應(yīng)，可能會(huì)返回504狀態(tài)碼。

說一說四次揮手的整個(gè)過程？

TCP 四次揮手的過程如下：

在這里插入圖片描述

具體過程：

• 客戶端主動(dòng)調(diào)用關(guān)閉連接的函數(shù)，于是就會(huì)發(fā)送 FIN 報(bào)文，這個(gè) FIN 報(bào)文代表客戶端不會(huì)再發(fā)送數(shù)據(jù)了，進(jìn)入 FIN_WAIT_1 狀態(tài)；
• 服務(wù)端收到了 FIN 報(bào)文，然后馬上回復(fù)一個(gè) ACK 確認(rèn)報(bào)文，此時(shí)服務(wù)端進(jìn)入 CLOSE_WAIT 狀態(tài)。在收到 FIN 報(bào)文的時(shí)候，TCP 協(xié)議棧會(huì)為 FIN 包插入一個(gè)文件結(jié)束符 EOF 到接收緩沖區(qū)中，服務(wù)端應(yīng)用程序可以通過 read 調(diào)用來感知這個(gè) FIN 包，這個(gè) EOF 會(huì)被放在已排隊(duì)等候的其他已接收的數(shù)據(jù)之后，所以必須要得繼續(xù) read 接收緩沖區(qū)已接收的數(shù)據(jù)；
• 接著，當(dāng)服務(wù)端在 read 數(shù)據(jù)的時(shí)候，最后自然就會(huì)讀到 EOF，接著 read() 就會(huì)返回 0，這時(shí)服務(wù)端應(yīng)用程序如果有數(shù)據(jù)要發(fā)送的話，就發(fā)完數(shù)據(jù)后才調(diào)用關(guān)閉連接的函數(shù)，如果服務(wù)端應(yīng)用程序沒有數(shù)據(jù)要發(fā)送的話，可以直接調(diào)用關(guān)閉連接的函數(shù)，這時(shí)服務(wù)端就會(huì)發(fā)一個(gè) FIN 包，這個(gè) FIN 報(bào)文代表服務(wù)端不會(huì)再發(fā)送數(shù)據(jù)了，之后處于 LAST_ACK 狀態(tài)；
• 客戶端接收到服務(wù)端的 FIN 包，并發(fā)送 ACK 確認(rèn)包給服務(wù)端，此時(shí)客戶端將進(jìn)入 TIME_WAIT 狀態(tài)；
• 服務(wù)端收到 ACK 確認(rèn)包后，就進(jìn)入了最后的 CLOSE 狀態(tài)；
• 客戶端經(jīng)過 2MSL 時(shí)間之后，也進(jìn)入 CLOSE 狀態(tài)；

你可以看到，每個(gè)方向都需要一個(gè) FIN 和一個(gè) ACK，因此通常被稱為四次揮手。

Time_wait 為什么2MSL ？

主要是兩個(gè)原因：

• 防止歷史連接中的數(shù)據(jù)，被后面相同四元組的連接錯(cuò)誤的接收；
• 保證「被動(dòng)關(guān)閉連接」的一方，能被正確的關(guān)閉；

原因一：防止歷史連接中的數(shù)據(jù)，被后面相同四元組的連接錯(cuò)誤的接收

假設(shè) TIME-WAIT 沒有等待時(shí)間或時(shí)間過短，被延遲的數(shù)據(jù)包抵達(dá)后會(huì)發(fā)生什么呢？

TIME-WAIT 時(shí)間過短，收到舊連接的數(shù)據(jù)報(bào)文

如上圖：

• 服務(wù)端在關(guān)閉連接之前發(fā)送的 SEQ = 301 報(bào)文，被網(wǎng)絡(luò)延遲了。
• 接著，服務(wù)端以相同的四元組重新打開了新連接，前面被延遲的 SEQ = 301 這時(shí)抵達(dá)了客戶端，而且該數(shù)據(jù)報(bào)文的序列號剛好在客戶端接收窗口內(nèi)，因此客戶端會(huì)正常接收這個(gè)數(shù)據(jù)報(bào)文，但是這個(gè)數(shù)據(jù)報(bào)文是上一個(gè)連接殘留下來的，這樣就產(chǎn)生數(shù)據(jù)錯(cuò)亂等嚴(yán)重的問題。

為了防止歷史連接中的數(shù)據(jù)，被后面相同四元組的連接錯(cuò)誤的接收，因此 TCP 設(shè)計(jì)了 TIME_WAIT 狀態(tài)，狀態(tài)會(huì)持續(xù) 2MSL 時(shí)長，這個(gè)時(shí)間足以讓兩個(gè)方向上的數(shù)據(jù)包都被丟棄，使得原來連接的數(shù)據(jù)包在網(wǎng)絡(luò)中都自然消失，再出現(xiàn)的數(shù)據(jù)包一定都是新建立連接所產(chǎn)生的。

原因二：保證「被動(dòng)關(guān)閉連接」的一方，能被正確的關(guān)閉

在 RFC 793 指出 TIME-WAIT 另一個(gè)重要的作用是：

TIME-WAIT - represents waiting for enough time to pass to be sure the remote TCP received the acknowledgment of its connection termination request.

也就是說，TIME-WAIT 作用是等待足夠的時(shí)間以確保最后的 ACK 能讓被動(dòng)關(guān)閉方接收，從而幫助其正常關(guān)閉。

如果客戶端（主動(dòng)關(guān)閉方）最后一次 ACK 報(bào)文（第四次揮手）在網(wǎng)絡(luò)中丟失了，那么按照 TCP 可靠性原則，服務(wù)端（被動(dòng)關(guān)閉方）會(huì)重發(fā) FIN 報(bào)文。

假設(shè)客戶端沒有 TIME_WAIT 狀態(tài)，而是在發(fā)完最后一次回 ACK 報(bào)文就直接進(jìn)入 CLOSE 狀態(tài)，如果該 ACK 報(bào)文丟失了，服務(wù)端則重傳的 FIN 報(bào)文，而這時(shí)客戶端已經(jīng)進(jìn)入到關(guān)閉狀態(tài)了，在收到服務(wù)端重傳的 FIN 報(bào)文后，就會(huì)回 RST 報(bào)文。

TIME-WAIT 時(shí)間過短，沒有確保連接正常關(guān)閉

服務(wù)端收到這個(gè) RST 并將其解釋為一個(gè)錯(cuò)誤（Connection reset by peer），這對于一個(gè)可靠的協(xié)議來說不是一個(gè)優(yōu)雅的終止方式。

為了防止這種情況出現(xiàn)，客戶端必須等待足夠長的時(shí)間，確保服務(wù)端能夠收到 ACK，如果服務(wù)端沒有收到 ACK，那么就會(huì)觸發(fā) TCP 重傳機(jī)制，服務(wù)端會(huì)重新發(fā)送一個(gè) FIN，這樣一去一來剛好兩個(gè) MSL 的時(shí)間。

TIME-WAIT 時(shí)間正常，確保了連接正常關(guān)閉

客戶端在收到服務(wù)端重傳的 FIN 報(bào)文時(shí)，TIME_WAIT 狀態(tài)的等待時(shí)間，會(huì)重置回 2MSL。

當(dāng)存在大量close_wait的連接時(shí)怎么處理？

CLOSE_WAIT 狀態(tài)是「被動(dòng)關(guān)閉方」才會(huì)有的狀態(tài)，而且如果「被動(dòng)關(guān)閉方」沒有調(diào)用 close 函數(shù)關(guān)閉連接，那么就無法發(fā)出 FIN 報(bào)文，從而無法使得 CLOSE_WAIT 狀態(tài)的連接轉(zhuǎn)變?yōu)?LAST_ACK 狀態(tài)。

所以，當(dāng)服務(wù)端出現(xiàn)大量 CLOSE_WAIT 狀態(tài)的連接的時(shí)候，說明服務(wù)端的程序沒有調(diào)用 close 函數(shù)關(guān)閉連接。

那什么情況會(huì)導(dǎo)致服務(wù)端的程序沒有調(diào)用 close 函數(shù)關(guān)閉連接？這時(shí)候通常需要排查代碼。

我們先來分析一個(gè)普通的 TCP 服務(wù)端的流程：

1. 創(chuàng)建服務(wù)端 socket，bind 綁定端口、listen 監(jiān)聽端口
2. 將服務(wù)端 socket 注冊到 epoll
3. epoll_wait 等待連接到來，連接到來時(shí)，調(diào)用 accpet 獲取已連接的 socket
4. 將已連接的 socket 注冊到 epoll
5. epoll_wait 等待事件發(fā)生
6. 對方連接關(guān)閉時(shí)，我方調(diào)用 close

可能導(dǎo)致服務(wù)端沒有調(diào)用 close 函數(shù)的原因，如下。

第一個(gè)原因：第 2 步?jīng)]有做，沒有將服務(wù)端 socket 注冊到 epoll，這樣有新連接到來時(shí)，服務(wù)端沒辦法感知這個(gè)事件，也就無法獲取到已連接的 socket，那服務(wù)端自然就沒機(jī)會(huì)對 socket 調(diào)用 close 函數(shù)了。

不過這種原因發(fā)生的概率比較小，這種屬于明顯的代碼邏輯 bug，在前期 read view 階段就能發(fā)現(xiàn)的了。

第二個(gè)原因：第 3 步?jīng)]有做，有新連接到來時(shí)沒有調(diào)用 accpet 獲取該連接的 socket，導(dǎo)致當(dāng)有大量的客戶端主動(dòng)斷開了連接，而服務(wù)端沒機(jī)會(huì)對這些 socket 調(diào)用 close 函數(shù)，從而導(dǎo)致服務(wù)端出現(xiàn)大量 CLOSE_WAIT 狀態(tài)的連接。

發(fā)生這種情況可能是因?yàn)榉?wù)端在執(zhí)行 accpet 函數(shù)之前，代碼卡在某一個(gè)邏輯或者提前拋出了異常。

第三個(gè)原因：第 4 步?jīng)]有做，通過 accpet 獲取已連接的 socket 后，沒有將其注冊到 epoll，導(dǎo)致后續(xù)收到 FIN 報(bào)文的時(shí)候，服務(wù)端沒辦法感知這個(gè)事件，那服務(wù)端就沒機(jī)會(huì)調(diào)用 close 函數(shù)了。

第四個(gè)原因：第 6 步?jīng)]有做，當(dāng)發(fā)現(xiàn)客戶端關(guān)閉連接后，服務(wù)端沒有執(zhí)行 close 函數(shù)，可能是因?yàn)榇a漏處理，或者是在執(zhí)行 close 函數(shù)之前，代碼卡在某一個(gè)邏輯，比如發(fā)生死鎖等等。

可以發(fā)現(xiàn)，當(dāng)服務(wù)端出現(xiàn)大量 CLOSE_WAIT 狀態(tài)的連接的時(shí)候，通常都是代碼的問題，這時(shí)候我們需要針對具體的代碼一步一步的進(jìn)行排查和定位，主要分析的方向就是服務(wù)端為什么沒有調(diào)用 close。

mysql

什么是聚簇索引和非聚簇索引？

• 對于聚簇索引表來說（左圖），表數(shù)據(jù)是和主鍵一起存儲(chǔ)的，主鍵索引的葉結(jié)點(diǎn)存儲(chǔ)行數(shù)據(jù)(包含了主鍵值)，二級索引的葉結(jié)點(diǎn)存儲(chǔ)行的主鍵值。使用的是B+樹作為索引的存儲(chǔ)結(jié)構(gòu)，非葉子節(jié)點(diǎn)都是索引關(guān)鍵字，但非葉子節(jié)點(diǎn)中的關(guān)鍵字中不存儲(chǔ)對應(yīng)記錄的具體內(nèi)容或內(nèi)容地址。葉子節(jié)點(diǎn)上的數(shù)據(jù)是主鍵與具體記錄(數(shù)據(jù)內(nèi)容)。
• 對于非聚簇索引表來說（右圖），表數(shù)據(jù)和索引是分成兩部分存儲(chǔ)的，主鍵索引和二級索引存儲(chǔ)上沒有任何區(qū)別。使用的是B+樹作為索引的存儲(chǔ)結(jié)構(gòu)，所有的節(jié)點(diǎn)都是索引，葉子節(jié)點(diǎn)存儲(chǔ)的是索引+索引對應(yīng)的記錄的數(shù)據(jù)。

InooDB 為什么要使用聚簇索引？

使用聚簇索引的一些好處：

• 數(shù)據(jù)行的物理存儲(chǔ)順序：使用聚集索引可以將數(shù)據(jù)行按照索引鍵的順序存儲(chǔ)在磁盤上，這樣相鄰的數(shù)據(jù)行在物理上也是相鄰的。這種物理存儲(chǔ)順序可以提高基于范圍查詢的性能，因?yàn)橄嚓P(guān)的數(shù)據(jù)行在物理上是連續(xù)的，減少了磁盤I/O的次數(shù)。

• 覆蓋索引查詢：由于聚集索引包含了實(shí)際的數(shù)據(jù)行，當(dāng)查詢只需要使用聚集索引的鍵列時(shí)，可以避免訪問數(shù)據(jù)行，提高查詢性能。這種情況下也稱為覆蓋索引查詢。

什么是 InooDB里面的聯(lián)合索引？

通過將多個(gè)字段組合成一個(gè)索引，該索引就被稱為聯(lián)合索引。

比如，將商品表中的 product_no 和 name 字段組合成聯(lián)合索引(product_no, name)，創(chuàng)建聯(lián)合索引的方式如下：

CREATEINDEXindex_product_no_nameONproduct(product_no,name);

聯(lián)合索引(product_no, name) 的 B+Tree 示意圖如下（圖中葉子節(jié)點(diǎn)之間我畫了單向鏈表，但是實(shí)際上是雙向鏈表，原圖我找不到了，修改不了，偷個(gè)懶我不重畫了，大家腦補(bǔ)成雙向鏈表就行）。

聯(lián)合索引

可以看到，聯(lián)合索引的非葉子節(jié)點(diǎn)用兩個(gè)字段的值作為 B+Tree 的 key 值。當(dāng)在聯(lián)合索引查詢數(shù)據(jù)時(shí)，先按 product_no 字段比較，在 product_no 相同的情況下再按 name 字段比較。

也就是說，聯(lián)合索引查詢的 B+Tree 是先按 product_no 進(jìn)行排序，然后再 product_no 相同的情況再按 name 字段排序。

因此，使用聯(lián)合索引時(shí)，存在最左匹配原則，也就是按照最左優(yōu)先的方式進(jìn)行索引的匹配。在使用聯(lián)合索引進(jìn)行查詢的時(shí)候，如果不遵循「最左匹配原則」，聯(lián)合索引會(huì)失效，這樣就無法利用到索引快速查詢的特性了。

比如，如果創(chuàng)建了一個(gè) (a, b, c) 聯(lián)合索引，如果查詢條件是以下這幾種，就可以匹配上聯(lián)合索引：

• where a=1；
• where a=1 and b=2 and c=3；
• where a=1 and b=2；

需要注意的是，因?yàn)橛胁樵儍?yōu)化器，所以 a 字段在 where 子句的順序并不重要。

但是，如果查詢條件是以下這幾種，因?yàn)椴环献钭笃ヅ湓瓌t，所以就無法匹配上聯(lián)合索引，聯(lián)合索引就會(huì)失效:

• where b=2；
• where c=3；
• where b=2 and c=3；

上面這些查詢條件之所以會(huì)失效，是因?yàn)?code style="font-size:14px;padding:2px 4px;margin-right:2px;margin-left:2px;background-color:rgba(27,31,35,.05);font-family:'Operator Mono', Consolas, Monaco, Menlo, monospace;color:rgb(100,149,237);">(a, b, c) 聯(lián)合索引，是先按 a 排序，在 a 相同的情況再按 b 排序，在 b 相同的情況再按 c 排序。所以，b 和 c 是全局無序，局部相對有序的，這樣在沒有遵循最左匹配原則的情況下，是無法利用到索引的。

我這里舉聯(lián)合索引（a，b）的例子，該聯(lián)合索引的 B+ Tree 如下（圖中葉子節(jié)點(diǎn)之間我畫了單向鏈表，但是實(shí)際上是雙向鏈表，原圖我找不到了，修改不了，偷個(gè)懶我不重畫了，大家腦補(bǔ)成雙向鏈表就行）。

img

可以看到，a 是全局有序的（1, 2, 2, 3, 4, 5, 6, 7 ,8），而 b 是全局是無序的（12，7，8，2，3，8，10，5，2）。因此，直接執(zhí)行where b = 2這種查詢條件沒有辦法利用聯(lián)合索引的，利用索引的前提是索引里的 key 是有序的。

只有在 a 相同的情況才，b 才是有序的，比如 a 等于 2 的時(shí)候，b 的值為（7，8），這時(shí)就是有序的，這個(gè)有序狀態(tài)是局部的，因此，執(zhí)行where a = 2 and b = 7是 a 和 b 字段能用到聯(lián)合索引的，也就是聯(lián)合索引生效了。

給出一個(gè)表A 有a1~a5 個(gè)列，聯(lián)合索引（a2,a1）select a5 from A where a2=1 and a1=2 請問用到聯(lián)合索引了嘛？它的具體過程呢？

查詢符合最左匹配原則，可以a1 和 a2 都可以使用聯(lián)合索引。

具體的查詢過程，在二級索引 b+樹找到符合條件 a2 和 a1 的記錄，然后獲取這些記錄的 id 值，拿 id 值去主鍵索引查詢 a5 列的值，這里涉及了回表的查詢。

算法

滑動(dòng)窗口 歷史好文： 我們又出成績了??！ 還是銀行面試舒服些... 百度提前批，有點(diǎn)難度！ 面試不會(huì)的問題，可以硬著頭皮亂答嗎.....