一、序言
二撤嫩、磁盤結(jié)構(gòu)
三、磁盤中數(shù)據(jù)存儲(chǔ)
四蠢终、索引在磁盤中的存儲(chǔ)
五序攘、二級(jí)索引

一、序言

都說加索引能加快查詢的速度寻拂，其實(shí)通過索引本質(zhì)上是減少磁盤的讀取次數(shù)程奠，到底索引和磁盤的關(guān)系是怎樣的呢？

二祭钉、磁盤結(jié)構(gòu)

首先我們先了解一下操作系統(tǒng)是怎么從磁盤中讀取數(shù)據(jù)的瞄沙，操作系統(tǒng)通常是以頁為單位從磁盤中讀取數(shù)據(jù)，磁盤可以理解為一個(gè)圓盤慌核，每個(gè)圓盤上有若干磁道距境。

比如下面的圖有4種不同顏色的磁道，每條磁道上每個(gè)半圓代表一個(gè)扇區(qū)垮卓，也就是一條磁道在這里被劃分為4個(gè)扇區(qū)垫桂。

1.jpg

操作系統(tǒng)從磁盤中讀取數(shù)據(jù)時(shí)，也是按頁(扇區(qū))來讀取粟按，讀取一塊數(shù)據(jù)诬滩，我們稱之為1個(gè)block塊霹粥。

不同硬盤每個(gè)扇區(qū)的存儲(chǔ)容量不一樣。

• 機(jī)械硬盤：每個(gè)扇區(qū)為512B疼鸟。
• 固態(tài)硬盤(SSD)：page大小為4KB后控。

備注：為什么要以頁為單位從磁盤讀取數(shù)據(jù)呢？
如果每次只查詢1條記錄空镜，由于磁盤檢索速度比較慢浩淘，會(huì)有一定的性能消耗。但如果每次讀一頁數(shù)據(jù)姑裂，會(huì)減少磁盤讀取的次數(shù)馋袜。

三、磁盤中數(shù)據(jù)存儲(chǔ)

假設(shè)有一張用戶表舶斧，表中共有用戶ID欣鳖、用戶名、密碼茴厉、頭像泽台、備注5個(gè)字段，字段長度如下：

2.jpg

根據(jù)字段長度定義矾缓，一條記錄的大小為128字節(jié)怀酷，而機(jī)械硬盤一個(gè)扇區(qū)最多能存儲(chǔ)512字節(jié)，也就說是一次扇區(qū)掃描最多能讀取4條記錄嗜闻。

我們把從磁盤扇區(qū)讀取的數(shù)據(jù)稱之為1個(gè)block蜕依，

• 一個(gè)block可以存儲(chǔ)512 / 128 = 4條記錄
• 100條記錄則需要100 / 4 = 25個(gè)block

也就是說讀取user_id為100的記錄最多需要訪問25個(gè)block，也就是25次磁盤查詢琉雳。

如果說要讀取user_id為1000的記錄样眠，則最多需要進(jìn)行250次的磁盤查詢，如果數(shù)據(jù)量更大呢翠肘？這個(gè)時(shí)候索引的作用就出來了檐束。

四、索引在磁盤中的存儲(chǔ)

上面的例子中束倍，數(shù)據(jù)量越大被丧，磁盤查詢的的次數(shù)也就越多，我們可以做一個(gè)優(yōu)化绪妹，對(duì)user_id列加上索引甥桂。

3.png

上面我們說了假設(shè)該用戶表1條記錄占128字節(jié)，1個(gè)block可以存放512 / 128 = 4條記錄邮旷。

現(xiàn)在對(duì)user_id列加上索引格嘁，該索引會(huì)保存該列的數(shù)據(jù)和數(shù)據(jù)指針(指向數(shù)據(jù)所在的磁盤扇區(qū))。

假設(shè)數(shù)據(jù)指針為6字節(jié)廊移，那么一條索引將占用該列長度10 + 6 = 16字節(jié)糕簿，1個(gè)block(512字節(jié))可以存放512 / 16 = 32條索引記錄探入。100條索引記錄需要占用100 / 32 = 4個(gè)block。

上面說了100條數(shù)據(jù)記錄需要占用100 / 4 = 25個(gè)block懂诗。以這100條數(shù)據(jù)為例蜂嗽，我們用4個(gè)block存索引數(shù)據(jù)，25個(gè)block存儲(chǔ)列數(shù)據(jù)殃恒。

這個(gè)時(shí)候讀取user_id為100個(gè)記錄植旧，我們先掃描索引，最多讀取4個(gè)block就可以找到該數(shù)據(jù)所在磁盤扇區(qū)离唐，再經(jīng)過1次磁盤查詢就可以找到該數(shù)據(jù)病附，也就是說最多經(jīng)過5次磁盤查詢。

如果是讀取user_id為1000的記錄亥鬓，最多讀取32個(gè)block索引數(shù)據(jù)加上1個(gè)block列數(shù)據(jù)完沪，也就是33次磁盤查詢就能找到。

而且內(nèi)存訪問比磁盤快嵌戈，因?yàn)樗饕龜?shù)據(jù)比較小覆积，我們完全可以將索引數(shù)據(jù)加載到內(nèi)存，這樣訪問會(huì)更快熟呛。

備注：InnoDB中索引數(shù)據(jù)和列數(shù)據(jù)在同一個(gè)(.ibd)文件宽档，而索引數(shù)據(jù)總是在文件的最前面，查詢數(shù)據(jù)時(shí)先掃描索引庵朝。

五吗冤、二級(jí)索引

問題又來了，如果數(shù)據(jù)量越來越大九府，變成10w條椎瘟，100w條，就算建立10w條昔逗，100w條索引降传，速度還是會(huì)越來越慢篷朵，該怎么辦呢勾怒？

我們可以針對(duì)索引再見索引，什么意思呢声旺？

4.jpg

上面說了笔链，1000條數(shù)據(jù)需要構(gòu)建32個(gè)索引block，如果我們以32為單位腮猖，只存32條二級(jí)索引記錄鉴扫，再次構(gòu)建二級(jí)索引，則只需要1個(gè)索引block澈缺。（二級(jí)索引只存放user_id值為32及其倍數(shù)的數(shù)據(jù)）

以這1000條數(shù)據(jù)為例坪创，我們用1個(gè)block存二級(jí)索引數(shù)據(jù)炕婶，32個(gè)block存1級(jí)索引數(shù)據(jù)，250個(gè)block存列數(shù)據(jù)莱预。

這個(gè)時(shí)候如果讀取user_id為1000的記錄柠掂，只需要讀取1個(gè)二級(jí)索引block，1個(gè)一級(jí)索引塊依沮，再經(jīng)過1次磁盤查詢就能找到涯贞，也就是最多3次磁盤查詢。

當(dāng)然危喉，隨著數(shù)據(jù)量越來越大宋渔，二級(jí)索引數(shù)據(jù)也會(huì)越來越大，為了更好理解辜限，我們將它轉(zhuǎn)換為樹的形式皇拣，是不是覺得很熟悉。

5.jpg

當(dāng)然實(shí)際索引數(shù)據(jù)結(jié)構(gòu)列粪，像B+樹等多路平衡樹會(huì)更加復(fù)雜审磁，這個(gè)我們后面再分享。