文章來源于公眾號三太子敖丙 房匆，作者三太子敖丙

背景

我相信大家在數(shù)據(jù)庫優(yōu)化的時(shí)候都會說到索引，我也不例外报亩，大家也基本上能對數(shù)據(jù)結(jié)構(gòu)的優(yōu)化回答個(gè)一二三浴鸿，以及頁緩存之類的都能扯上幾句，但是有一次阿里P9的一個(gè)面試問我：你能從計(jì)算機(jī)層面開始說一下一個(gè)索引數(shù)據(jù)加載的流程么弦追？（就是想讓我聊IO）

我當(dāng)場就去世了....因?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)和操作系統(tǒng)的基礎(chǔ)知識真的是我的盲區(qū)岳链，不過后面我惡補(bǔ)了，廢話不多說劲件，我們就從計(jì)算機(jī)加載數(shù)據(jù)聊起掸哑，講一下?lián)Q個(gè)角度聊索引约急。

正文

MySQL的索引本質(zhì)上是一種數(shù)據(jù)結(jié)構(gòu)

讓我們先來了解一下計(jì)算機(jī)的數(shù)據(jù)加載。

磁盤IO和預(yù)讀：

image

先說一下磁盤IO苗分，磁盤讀取數(shù)據(jù)靠的是機(jī)械運(yùn)動厌蔽，每一次讀取數(shù)據(jù)需要尋道、尋點(diǎn)摔癣、拷貝到內(nèi)存三步操作奴饮。

尋道時(shí)間是磁臂移動到指定磁道所需要的時(shí)間，一般在5ms以下择浊；

尋點(diǎn)是從磁道中找到數(shù)據(jù)存在的那個(gè)點(diǎn)戴卜，平均時(shí)間是半圈時(shí)間，如果是一個(gè)7200轉(zhuǎn)/min的磁盤琢岩，尋點(diǎn)時(shí)間平均是600000/7200/2=4.17ms投剥；

拷貝到內(nèi)存的時(shí)間很快，和前面兩個(gè)時(shí)間比起來可以忽略不計(jì)担孔，所以一次IO的時(shí)間平均是在9ms左右薇缅。聽起來很快，但數(shù)據(jù)庫百萬級別的數(shù)據(jù)過一遍就達(dá)到了9000s攒磨，顯然就是災(zāi)難級別的了泳桦。

image

image

考慮到磁盤IO是非常高昂的操作，計(jì)算機(jī)操作系統(tǒng)做了預(yù)讀的優(yōu)化娩缰，當(dāng)一次IO時(shí)灸撰，不光把當(dāng)前磁盤地址的數(shù)據(jù)，而是把相鄰的數(shù)據(jù)也都讀取到內(nèi)存緩沖區(qū)內(nèi)拼坎，因?yàn)楫?dāng)計(jì)算機(jī)訪問一個(gè)地址的數(shù)據(jù)的時(shí)候浮毯，與其相鄰的數(shù)據(jù)也會很快被訪問到。

每一次IO讀取的數(shù)據(jù)我們稱之為一頁(page)泰鸡，具體一頁有多大數(shù)據(jù)跟操作系統(tǒng)有關(guān)债蓝，一般為4k或8k，也就是我們讀取一頁內(nèi)的數(shù)據(jù)時(shí)候盛龄，實(shí)際上才發(fā)生了一次IO饰迹。

（突然想到個(gè)我剛畢業(yè)被問過的問題，在64位的操作系統(tǒng)中余舶，Java中的int類型占幾個(gè)字節(jié)啊鸭？最大是多少？為什么匿值？）

那我們想要優(yōu)化數(shù)據(jù)庫查詢赠制，就要盡量減少磁盤的IO操作，所以就出現(xiàn)了索引挟憔。

索引是什么钟些？

MySQL官方對索引的定義為：索引(Index)是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)烟号。

MySQL中常用的索引在物理上分兩類，B-樹索引和哈希索引政恍。

本次主要講BTree索引褥符。

BTree索引

BTree又叫多路平衡查找樹，一顆m叉的BTree特性如下：

• 樹中每個(gè)節(jié)點(diǎn)最多包含m個(gè)孩子抚垃。
• 除根節(jié)點(diǎn)與葉子節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)至少有[ceil(m/2)]個(gè)孩子（ceil()為向上取整）趟大。
• 若根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)鹤树，則至少有兩個(gè)孩子。
• 所有的葉子節(jié)點(diǎn)都在同一層逊朽。
• 每個(gè)非葉子節(jié)點(diǎn)由n個(gè)key與n+1個(gè)指針組成罕伯，其中[ceil(m/2)-1] <= n <= m-1 。

image

這是一個(gè)3叉（只是舉例叽讳，真實(shí)會有很多叉）的BTree結(jié)構(gòu)圖追他，每一個(gè)方框塊我們稱之為一個(gè)磁盤塊或者叫做一個(gè)block塊，這是操作系統(tǒng)一次IO往內(nèi)存中讀的內(nèi)容岛蚤，一個(gè)塊對應(yīng)四個(gè)扇區(qū)邑狸，紫色代表的是磁盤塊中的數(shù)據(jù)key，黃色代表的是數(shù)據(jù)data涤妒，藍(lán)色代表的是指針p单雾，指向下一個(gè)磁盤塊的位置。

來模擬下查找key為29的data的過程：

1她紫、根據(jù)根結(jié)點(diǎn)指針讀取文件目錄的根磁盤塊1硅堆。【磁盤IO操作1次】

2贿讹、磁盤塊1存儲17渐逃，35和三個(gè)指針數(shù)據(jù)。我們發(fā)現(xiàn)17<29<35民褂，因此我們找到指針p2茄菊。

3、根據(jù)p2指針赊堪，我們定位并讀取磁盤塊3买羞。【磁盤IO操作2次】

4雹食、磁盤塊3存儲26畜普，30和三個(gè)指針數(shù)據(jù)。我們發(fā)現(xiàn)26<29<30群叶，因此我們找到指針p2吃挑。

5钝荡、根據(jù)p2指針，我們定位并讀取磁盤塊8舶衬〔和ǎ【磁盤IO操作3次】

6、磁盤塊8中存儲28逛犹，29端辱。我們找到29，獲取29所對應(yīng)的數(shù)據(jù)data虽画。

由此可見舞蔽，BTree索引使每次磁盤I/O取到內(nèi)存的數(shù)據(jù)都發(fā)揮了作用，從而提高了查詢效率码撰。

但是有沒有什么可優(yōu)化的地方呢渗柿？

我們從圖上可以看到，每個(gè)節(jié)點(diǎn)中不僅包含數(shù)據(jù)的key值脖岛，還有data值朵栖。而每一個(gè)頁的存儲空間是有限的，如果data數(shù)據(jù)較大時(shí)將會導(dǎo)致每個(gè)節(jié)點(diǎn)（即一個(gè)頁）能存儲的key的數(shù)量很小柴梆，當(dāng)存儲的數(shù)據(jù)量很大時(shí)同樣會導(dǎo)致B-Tree的深度較大陨溅，增大查詢時(shí)的磁盤I/O次數(shù)，進(jìn)而影響查詢效率绍在。

B+Tree索引

B+Tree是在B-Tree基礎(chǔ)上的一種優(yōu)化声登，使其更適合實(shí)現(xiàn)外存儲索引結(jié)構(gòu)。在B+Tree中揣苏，所有數(shù)據(jù)記錄節(jié)點(diǎn)都是按照鍵值大小順序存放在同一層的葉子節(jié)點(diǎn)上悯嗓，而非葉子節(jié)點(diǎn)上只存儲key值信息，這樣可以大大加大每個(gè)節(jié)點(diǎn)存儲的key值數(shù)量卸察，降低B+Tree的高度脯厨。

image

B+Tree相對于B-Tree有幾點(diǎn)不同：

非葉子節(jié)點(diǎn)只存儲鍵值信息， 數(shù)據(jù)記錄都存放在葉子節(jié)點(diǎn)中坑质， 將上一節(jié)中的B-Tree優(yōu)化合武，由于B+Tree的非葉子節(jié)點(diǎn)只存儲鍵值信息，所以B+Tree的高度可以被壓縮到特別的低涡扼。

具體的數(shù)據(jù)如下：

InnoDB存儲引擎中頁的大小為16KB稼跳，一般表的主鍵類型為INT（占用4個(gè)字節(jié)）或BIGINT（占用8個(gè)字節(jié)），指針類型也一般為4或8個(gè)字節(jié)吃沪，也就是說一個(gè)頁（B+Tree中的一個(gè)節(jié)點(diǎn)）中大概存儲16KB/(8B+8B)=1K個(gè)鍵值（因?yàn)槭枪乐堤郎疲瑸榉奖阌?jì)算，這里的K取值為〖10〗^3）。

也就是說一個(gè)深度為3的B+Tree索引可以維護(hù)10^3 * 10^3 * 10^3 = 10億 條記錄红淡。（這種計(jì)算方式存在誤差不狮，而且沒有計(jì)算葉子節(jié)點(diǎn)，如果計(jì)算葉子節(jié)點(diǎn)其實(shí)是深度為4了）

我們只需要進(jìn)行三次的IO操作就可以從10億條數(shù)據(jù)中找到我們想要的數(shù)據(jù)在旱，比起最開始的百萬數(shù)據(jù)9000秒不知道好了多少個(gè)華萊士了摇零。

而且在B+Tree上通常有兩個(gè)頭指針，一個(gè)指向根節(jié)點(diǎn)桶蝎，另一個(gè)指向關(guān)鍵字最小的葉子節(jié)點(diǎn)驻仅，而且所有葉子節(jié)點(diǎn)（即數(shù)據(jù)節(jié)點(diǎn)）之間是一種鏈?zhǔn)江h(huán)結(jié)構(gòu)。所以我們除了可以對B+Tree進(jìn)行主鍵的范圍查找和分頁查找登渣，還可以從根節(jié)點(diǎn)開始噪服，進(jìn)行隨機(jī)查找。

數(shù)據(jù)庫中的B+Tree索引可以分為聚集索引（clustered index）和輔助索引（secondary index）绍豁。

上面的B+Tree示例圖在數(shù)據(jù)庫中的實(shí)現(xiàn)即為聚集索引，聚集索引的B+Tree中的葉子節(jié)點(diǎn)存放的是整張表的行記錄數(shù)據(jù)牙捉，輔助索引與聚集索引的區(qū)別在于輔助索引的葉子節(jié)點(diǎn)并不包含行記錄的全部數(shù)據(jù)竹揍，而是存儲相應(yīng)行數(shù)據(jù)的聚集索引鍵，即主鍵邪铲。

當(dāng)通過輔助索引來查詢數(shù)據(jù)時(shí)第练，InnoDB存儲引擎會遍歷輔助索引找到主鍵襟己，然后再通過主鍵在聚集索引中找到完整的行記錄數(shù)據(jù)。

image

不過，雖然索引可以加快查詢速度旗芬，提高 MySQL 的處理性能，但是過多地使用索引也會造成以下弊端：

• 創(chuàng)建索引和維護(hù)索引要耗費(fèi)時(shí)間秋忙，這種時(shí)間隨著數(shù)據(jù)量的增加而增加秸弛。
• 除了數(shù)據(jù)表占數(shù)據(jù)空間之外，每一個(gè)索引還要占一定的物理空間搪搏。如果要建立聚簇索引狭握，那么需要的空間就會更大。
• 當(dāng)對表中的數(shù)據(jù)進(jìn)行增加疯溺、刪除和修改的時(shí)候论颅，索引也要?jiǎng)討B(tài)地維護(hù)，這樣就降低了數(shù)據(jù)的維護(hù)速度囱嫩。

注意：索引可以在一些情況下加速查詢恃疯，但是在某些情況下，會降低效率墨闲。

索引只是提高效率的一個(gè)因素今妄，因此在建立索引的時(shí)候應(yīng)該遵循以下原則：

• 在經(jīng)常需要搜索的列上建立索引，可以加快搜索的速度。
• 在作為主鍵的列上創(chuàng)建索引蛙奖，強(qiáng)制該列的唯一性潘酗，并組織表中數(shù)據(jù)的排列結(jié)構(gòu)。
• 在經(jīng)常使用表連接的列上創(chuàng)建索引雁仲，這些列主要是一些外鍵仔夺，可以加快表連接的速度。
• 在經(jīng)常需要根據(jù)范圍進(jìn)行搜索的列上創(chuàng)建索引攒砖，因?yàn)樗饕呀?jīng)排序缸兔，所以其指定的范圍是連續(xù)的。
• 在經(jīng)常需要排序的列上創(chuàng)建索引吹艇，因?yàn)樗饕呀?jīng)排序惰蜜，所以查詢時(shí)可以利用索引的排序，加快排序查詢受神。
• 在經(jīng)常使用 WHERE 子句的列上創(chuàng)建索引抛猖，加快條件的判斷速度。

現(xiàn)在大家知道索引為啥能這么快了吧鼻听，其實(shí)就是一句話财著，通過索引的結(jié)構(gòu)最大化的減少數(shù)據(jù)庫的IO次數(shù)，畢竟撑碴，一次IO的時(shí)間真的是太久了撑教。。醉拓。

總結(jié)

就面試而言很多知識其實(shí)我們可以很容易就掌握了伟姐，但是要以學(xué)習(xí)為目的，你會發(fā)現(xiàn)很多東西我們得深入到計(jì)算機(jī)基礎(chǔ)上才能發(fā)現(xiàn)其中奧秘亿卤，很多人問我怎么記住這么多東西愤兵，其實(shí)學(xué)習(xí)本身就是一個(gè)很無奈的東西，既然我們不能不學(xué)那為啥不好好學(xué)排吴？去學(xué)會享受呢恐似？最近我也在惡補(bǔ)基礎(chǔ)，后面我會開始更新計(jì)算機(jī)基礎(chǔ)和網(wǎng)絡(luò)相關(guān)的知識的傍念。