前言
索引和鎖在數(shù)據(jù)庫中可以說是非常重要的知識點了凡蜻，在日常的功能開發(fā)中也會頻繁的接觸到辣之。
本文從github、博客想际、《高性能MySQL》上整理總結(jié)了一些常用的知識點培漏，希望大家看完都能有所收獲，開發(fā)過程中更能得心應(yīng)手胡本。
一牌柄、為什么索引能提高查詢速度
眾所周知，索引可以提高數(shù)據(jù)庫的查詢速度侧甫。同時珊佣， 索引也會降低插入蹋宦、刪除、修改等維護(hù)任務(wù)的速度咒锻。那索引到底是個啥冷冗，能這么神奇？回答這個問題前惑艇，我們先來扯一扯關(guān)于MySQL中數(shù)據(jù)的基本存儲結(jié)構(gòu)蒿辙。
MySQL中頁的基本存儲結(jié)構(gòu)
首先介紹下Mysql的基本存儲結(jié)構(gòu)——頁(記錄都存在頁里邊)：
頁的本質(zhì)就是一塊16KB大小的存儲空間，InnoDB為了不同的目的而把頁分為不同的類型滨巴，其中用于存放記錄的頁也稱為數(shù)據(jù)頁思灌，我們先看看這個用于存放記錄的頁長什么樣。數(shù)據(jù)頁代表的這塊16KB大小的存儲空間可以被劃分為多個部分恭取，不同部分有不同的功能泰偿，各個部分如圖所示：
大致說明一下各部分的作用：
| 名稱 | 中文名 | 占用空間大小 | 簡單描述 |
|---|---|---|---|
File Header |
文件頭 |
38字節(jié) |
一些描述頁的信息 |
Page Header |
頁頭 |
56字節(jié) |
頁的狀態(tài)信息 |
Infimum + Supremum |
最小記錄和最大記錄 |
26字節(jié) |
兩個虛擬的行記錄 |
User Records |
用戶記錄 | 不確定 | 實際存儲的行記錄內(nèi)容 |
Free Space |
空閑空間 | 不確定 | 頁中尚未使用的空間 |
Page Directory |
頁目錄 | 不確定 | 頁中的記錄相對位置 |
File Trailer |
文件結(jié)尾 |
8字節(jié) |
校驗頁是否完整 |
其中，存儲的記錄會按照我們指定的行格式存儲到User Records部分秽荤。但是在一開始生成頁的時候甜奄，其實并沒有User Records這個部分，每當(dāng)我們插入一行記錄窃款，都會從Free Space部分课兄，也就是尚未使用的存儲空間中申請一個記錄大小的空間劃分到User Records部分，當(dāng)Free Space部分的空間全部被User Records部分替代掉之后晨继，也就意味著這個頁使用完了烟阐，如果還有新的記錄插入的話，就需要去申請新的頁了紊扬，這個過程的圖示如下：
數(shù)據(jù)頁之間可以組成一個雙向鏈表
-
而每個數(shù)據(jù)頁中的記錄又可以組成一個單向鏈表
每個數(shù)據(jù)頁都會為存儲在它里面的記錄生成一個頁目錄蜒茄，在通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應(yīng)的槽，然后再遍歷該槽對應(yīng)分組中的記錄即可快速找到指定的記錄
以其他列(非主鍵)作為搜索條件：只能從最小記錄開始依次遍歷單鏈表中的每條記錄餐屎。
所以說檀葛，如果我們寫select * from user where username = 'shuaididi'這樣沒有進(jìn)行任何優(yōu)化的sql語句，默認(rèn)會這樣做：
需要依次遍歷雙向鏈表腹缩，定位到記錄所在的頁 屿聋。
從所在的頁內(nèi)中查找相應(yīng)的記錄 。由于不是根據(jù)主鍵查詢藏鹊，只能遍歷所在頁的單鏈表了
很明顯润讥，在數(shù)據(jù)量很大的情況下這樣查找會超級耗時的 ！ 時間復(fù)雜度為O（n） 盘寡。
MySQL中行的基本存儲結(jié)構(gòu)
為了故事的順利發(fā)展楚殿，我們新建一張表，然后說明數(shù)據(jù)是如何在計算機(jī)中被存儲的竿痰。
mysql> CREATE TABLE index_demo(
-> c1 INT,
-> c2 INT,
-> c3 CHAR(1),
-> PRIMARY KEY(c1)
-> ) ROW_FORMAT = Compact;
Query OK, 0 rows affected (0.03 sec)
這個新建的index_demo表中有2個INT類型的列脆粥，1個CHAR(1)類型的列砌溺，而且我們規(guī)定了c1列為主鍵，這個表使用Compact行格式來實際存儲記錄的变隔。為了我們理解上的方便抚吠，我們簡化了一下index_demo表的行格式示意圖：
我們只在示意圖里展示記錄的這幾個部分：
record_type：記錄頭信息的一項屬性，表示記錄的類型弟胀，0表示普通記錄、2表示最小記錄喊式、3表示最大記錄孵户、1我們還沒用過，等會再說～next_type：記錄頭信息的一項屬性岔留，表示下一條地址的偏移量夏哭，為了方便大家理解，我們都會用箭頭來表明下一條記錄是誰献联。各個列的值：就是各個數(shù)據(jù)列的值竖配，其中我們用橘黃色的格子代表c1列，深藍(lán)色的格子代表c2列里逆，紅色格子代表c3列进胯。其他信息：除了上述3種信息以外的所有信息，包括其他隱藏列的值以及記錄的額外信息原押。
為了節(jié)省篇幅胁镐，我們之后的示意圖中會把記錄的其他信息這個部分省略掉，因為它占地方并且不會有什么觀賞效果诸衔。另外盯漂，為了方便理解，我們覺得把記錄豎著放看起來感覺更好笨农，所以將記錄格式示意圖的其他信息去掉并把它豎起來的效果就是這樣：
把一些記錄放到頁里邊的示意圖就是：
一個簡單的索引方案
回到正題就缆，我們?yōu)槭裁匆闅v所有的數(shù)據(jù)頁呢？因為各個頁中的記錄并沒有規(guī)律谒亦，我們并不知道我們的搜索條件匹配哪些頁中的記錄竭宰，所以 不得不 依次遍歷。所以如果我們想快速的定位到需要查找的記錄在哪些數(shù)據(jù)頁中該咋辦诊霹？就像為數(shù)據(jù)頁中的記錄建立一個目錄一樣羞延，我們也可以為所有的數(shù)據(jù)頁建立一個目錄，建這個目錄必須完成下邊這些事兒：
-
下一個數(shù)據(jù)頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值脾还。
為了故事的順利發(fā)展伴箩，我們這里需要做一個假設(shè)：假設(shè)我們的每個數(shù)據(jù)頁最多能存放3條記錄（實際上一個數(shù)據(jù)頁非常大，可以存放下好多記錄）鄙漏。有了這個假設(shè)之后我們向
index_demo表插入3條記錄：
mysql> INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
Query OK, 3 rows affected (0.01 sec)
Records: 3 Duplicates: 0 Warnings: 0
mysql>
那么這些記錄已經(jīng)按照主鍵值的大小串聯(lián)成一個單向鏈表了嗤谚，如圖所示：
從圖中可以看出來棺蛛，index_demo表中的3條記錄都被插入到了編號為10的數(shù)據(jù)頁中了。此時我們再來插入一條記錄：
mysql> INSERT INTO index_demo VALUES(4, 4, 'a');Query OK, 1 row affected (0.00 sec)mysql>
因為頁10最多只能放3條記錄巩步，所以我們不得不再分配一個新頁：
這里需要注意的一點是旁赊，新分配的數(shù)據(jù)頁編號可能并不是連續(xù)的，也就是說我們使用的這些頁在存儲空間里可能并不挨著椅野。它們只是通過引用建立了鏈表關(guān)系终畅。另外，頁10中用戶記錄最大的主鍵值是5竟闪，而頁28中有一條記錄的主鍵值是4离福，因為5 > 4，所以這就不符合下一個數(shù)據(jù)頁的主鍵值必須大于上一個頁中的主鍵值的要求炼蛤，所以在插入主鍵值為4的記錄的時候需要伴隨著一次記錄移動妖爷，也就是把主鍵值為5的記錄移動到頁28中，然后再把主鍵值為4的記錄插入到頁10中理朋，這個過程的示意圖如下：
為了避免插入不連續(xù)數(shù)據(jù)導(dǎo)致的頁分裂和數(shù)據(jù)移動絮识，通常把主鍵設(shè)置為自增。同時嗽上，要避免使用UUID等隨機(jī)字符串作為主鍵次舌。
-
給所有的頁建立一個目錄項。
由于數(shù)據(jù)頁的編號可能并不是連續(xù)的兽愤，所以在向
index_demo表中插入許多條記錄后垃它，可能是這樣的效果：一個簡單的索引方案4.png因為這些
16KB的頁在物理存儲上并不挨著，所以如果想從這么多頁中根據(jù)主鍵值快速定位某些記錄所在的頁烹看，我們需要給它們做個目錄国拇，每個頁對應(yīng)一個目錄項，每個目錄項包括下邊兩個部分： 頁的用戶記錄中最小的主鍵值惯殊，我們用
key來表示酱吝。頁號，我們用
page_no表示土思。
所以我們?yōu)樯线厧讉€頁做好的目錄就像這樣子：
以
頁28為例务热，它對應(yīng)目錄項2，這個目錄項中包含著該頁的頁號28以及該頁中用戶記錄的最小主鍵值5己儒。我們只需要把幾個目錄項在物理存儲器上連續(xù)存儲崎岂，比如把他們放到一個數(shù)組里，就可以實現(xiàn)根據(jù)主鍵值快速查找某條記錄的功能了闪湾。比方說我們想找主鍵值為20的記錄冲甘，具體查找過程分兩步：先從目錄項中根據(jù)二分法快速確定出主鍵值為
20的記錄在目錄項3中（因為12 < 20 < 209），它對應(yīng)的頁是頁9。再根據(jù)前邊說的在頁中查找記錄的方式去
頁9中定位具體的記錄江醇。
至此濒憋，針對數(shù)據(jù)頁做的簡易目錄就搞定了。不過忘了說了陶夜，這個目錄有一個別名凛驮，稱為索引。
InnoDB中的索引方案
上邊之所以稱為一個簡易的索引方案条辟，是因為我們假設(shè)所有目錄項都可以在物理存儲器上連續(xù)存儲黔夭，但是這樣做有幾個問題：
InnoDB是使用頁來作為管理存儲空間的基本單位，也就是最多能保證16KB的連續(xù)存儲空間羽嫡，而隨著表中記錄數(shù)量的增多纠修，需要非常大的連續(xù)的存儲空間才能把所有的目錄項都放下，這對記錄數(shù)量非常多的表是不現(xiàn)實的厂僧。我們時常會對記錄進(jìn)行增刪，假設(shè)我們把
頁28中的記錄都刪除了了牛，頁28也就沒有存在的必要了颜屠，那意味著目錄項2也就沒有存在的必要了，這就需要把目錄項2后的目錄項都向前移動一下鹰祸，這種牽一發(fā)而動全身的設(shè)計不是什么好主意～
所以，設(shè)計InnoDB的大叔們需要一種可以靈活管理所有目錄項的方式。他們靈光乍現(xiàn)付燥，忽然發(fā)現(xiàn)這些目錄項其實長得跟我們的用戶記錄差不多舔糖，只不過目錄項中的兩個列是主鍵和頁號而已，所以他們復(fù)用了之前存儲用戶記錄的數(shù)據(jù)頁來存儲目錄項街图，為了和用戶記錄做一下區(qū)分浇衬，我們把這些用來表示目錄項的記錄稱為目錄項記錄。那InnoDB怎么區(qū)分一條記錄是普通的用戶記錄還是目錄項記錄呢餐济？別忘了記錄頭信息里的record_type屬性耘擂，它的各個取值代表的意思如下：
0：普通的用戶記錄1：目錄項記錄2：最小記錄3：最大記錄
哈哈，原來這個值為1的record_type是這個意思呀絮姆，我們把前邊使用到的目錄項放到數(shù)據(jù)頁中的樣子就是這樣：
從圖中可以看出來醉冤，我們新分配了一個編號為30的頁來專門存儲目錄項記錄。這里再次強(qiáng)調(diào)一遍目錄項記錄和普通的用戶記錄的不同點：
目錄項記錄的record_type值是1篙悯，而普通用戶記錄的record_type值是0蚁阳。目錄項記錄只有主鍵值和頁的編號兩個列，而普通的用戶記錄的列是用戶自己定義的鸽照，可能包含很多列螺捐，另外還有InnoDB自己添加的隱藏列。記錄頭信息里面還有一個叫
min_rec_mask的屬性，只有在存儲目錄項記錄的頁中的主鍵值最小的目錄項記錄的min_rec_mask值為1归粉，其他別的記錄的min_rec_mask值都是0椿疗。
除了上述幾點外，這兩者就沒啥差別了糠悼，它們用的是一樣的數(shù)據(jù)頁（頁面類型都是0x45BF届榄，這個屬性在Page Header中），頁的組成結(jié)構(gòu)也是一樣一樣的倔喂，都會為主鍵值生成Page Directory（頁目錄）以加快在頁內(nèi)的查詢速度铝条。所以現(xiàn)在根據(jù)某個主鍵值去查找記錄的步驟可以大致拆分成下邊兩步，以查找主鍵為20的記錄為例（因為都是從一個頁中通過主鍵查某條記錄席噩，所以都可以使用Page Directory通過二分法而實現(xiàn)快速查找）：
先到存儲
目錄項記錄的頁中通過二分法快速定位到對應(yīng)目錄項班缰，因為12 < 20 < 209，所以定位到對應(yīng)的記錄所在的頁就是頁9.從
頁9中根據(jù)二分法快速定位到主鍵值為20的用戶記錄悼枢。
雖然說目錄項記錄中只存儲主鍵值和對應(yīng)的頁號埠忘，比用戶記錄需要的存儲空間小多了，但是不論怎么說一個頁只有16KB大小馒索，能存放的目錄項記錄也是有限的莹妒，那如果表中的數(shù)據(jù)太多，以至于一個數(shù)據(jù)頁不足以存放所有的目錄項記錄绰上，該咋辦呢旨怠？
當(dāng)然是再多整一個存儲目錄項記錄的頁嘍～ 為了大家更好的理解如何新分配一個目錄項記錄頁的過程，我們假設(shè)一個存儲目錄項記錄的頁最多只能存放4條目錄項記錄（請注意是假設(shè)哦蜈块，真實情況下可以存放好多條的）鉴腻，所以如果此時我們再向上圖中插入一條主鍵值為320的用戶記錄的話，那就需要一個分配一個新的存儲目錄項記錄的頁嘍：
從圖中可以看出百揭，我們插入了一條主鍵值為320的用戶記錄之后新生成了2個數(shù)據(jù)頁
為存儲該用戶記錄而新生成了
頁31爽哎。因為原先存儲
目錄項記錄的頁30的容量已滿（我們前邊假設(shè)只能存儲4條目錄項記錄），所以不得不新生成了一個頁32來存放頁31對應(yīng)的目錄項器一。
那么問題來了倦青，在查詢過程中我們需要定位存儲目錄項記錄的頁，但是這些頁在存儲空間中也可能不挨著盹舞，如果我們表中的數(shù)據(jù)非常多則會產(chǎn)生很多存儲目錄項記錄的頁产镐，那我們怎么根據(jù)主鍵值快速定位一個存儲目錄項記錄的頁呢？其實也簡單踢步，為這些存儲目錄項記錄的頁再生成一個更高級的目錄癣亚，就像是一個多級目錄一樣，大目錄里嵌套小目錄获印，小目錄里才是實際的數(shù)據(jù)述雾，所以現(xiàn)在各個頁的示意圖就是這樣子：
假設(shè)我們要查詢id為8的記錄，查找過程如下：
如圖，我們生成了一個存儲更高級目錄項的頁33玻孟，這個頁中的兩條記錄分別代表頁30和頁32唆缴，如果用戶記錄的主鍵值在[1, 320)之間，則到頁30中查找更詳細(xì)的目錄項記錄黍翎，如果主鍵值不小于320的話面徽，就到頁32中查找更詳細(xì)的目錄項記錄。不過這張圖好漂亮喔匣掸，隨著表中記錄的增加趟紊，這個目錄的層級會繼續(xù)增加，如果簡化一下碰酝，那么我們可以用下邊這個圖來描述它：
這玩意兒像不像一個倒過來的樹呀霎匈！其實這是一種組織數(shù)據(jù)的形式，或者說是一種數(shù)據(jù)結(jié)構(gòu)送爸，它的名稱是B+樹铛嘱。
因為我們把數(shù)據(jù)頁都存放到B+樹這個數(shù)據(jù)結(jié)構(gòu)中了，所以我們也把我們的數(shù)據(jù)頁稱為節(jié)點袭厂。從圖中可以看出來墨吓，我們的實際用戶記錄其實都存放在B+樹的最底層的節(jié)點上，這些節(jié)點也被稱為葉子節(jié)點或葉節(jié)點嵌器，其余的節(jié)點都是用來存放目錄項的，這些節(jié)點統(tǒng)統(tǒng)被稱為內(nèi)節(jié)點或者說非葉節(jié)點谐丢。其中最上邊的那個節(jié)點也稱為根節(jié)點爽航。
從圖中可以看出來，一個B+樹的節(jié)點其實可以分成好多層乾忱，設(shè)計InnoDB的大叔們?yōu)榱擞懻摲奖慵フ洌?guī)定最下邊的那層，也就是存放我們用戶記錄的那層為第0層窄瘟，之后依次往上加衷佃。上邊我們做了一個非常極端的假設(shè)，存放用戶記錄的頁最多存放3條記錄蹄葱，存放目錄項記錄的頁最多存放4條記錄氏义，其實真實環(huán)境中一個頁存放的記錄數(shù)量是非常大的，假設(shè)图云，假設(shè)惯悠，假設(shè)所有的數(shù)據(jù)頁，包括存儲真實用戶記錄和目錄項記錄的頁竣况，都可以存放1000條記錄克婶，那么：
如果
B+樹只有1層，也就是只有1個用于存放用戶記錄的節(jié)點，最多能存放1000條記錄情萤。如果
B+樹有2層鸭蛙，最多能存放1000×1000=1000000條記錄。如果
B+樹有3層筋岛，最多能存放1000×1000×1000=1000000000條記錄娶视。-
如果
B+樹有4層，最多能存放1000×1000×1000×1000=1000000000000條記錄泉蝌。哇咔咔～這么多的記錄Ｐ颉！勋陪！事實上非葉子節(jié)點每頁存儲的數(shù)據(jù)要比葉子節(jié)點多得多贪磺。
這是因為非葉子節(jié)點不存儲用戶真實的數(shù)據(jù)，只存儲下一層的主鍵和頁號诅愚，占用空間較小寒锚。而葉子節(jié)點要存儲真實數(shù)據(jù)，所以占用空間較大违孝。
你的表里能存放1000000000000條記錄么刹前？所以一般情況下，我們用到的B+樹都不會超過4層雌桑，那我們通過主鍵去查找某條記錄最多只需要做4個頁面內(nèi)的查找喇喉，又因為在每個頁面內(nèi)有所謂的Page Directory（頁目錄），所以在頁面內(nèi)也可以通過二分法實現(xiàn)快速定位記錄校坑，這不是很diao么拣技，哈哈！
