聊聊 InnoDB 數(shù)據(jù)頁變成索引這件事
點(diǎn)擊關(guān)注公眾號(hào)，Java干貨及時(shí)送達(dá)??
前言
今天以數(shù)據(jù)頁為起點(diǎn)，來聊聊InnoDB的索引。
數(shù)據(jù)頁
我們都知道平時(shí)執(zhí)行crud的時(shí)候，都會(huì)從磁盤上加載數(shù)據(jù)頁到Buffer Pool的緩存頁里去，更新緩存頁后，由異步線程刷回磁盤的數(shù)據(jù)頁。
所以MySQL進(jìn)行數(shù)據(jù)操作的最小單位是數(shù)據(jù)頁，接下來就分析分析，數(shù)據(jù)頁到底長什么樣。
每個(gè)數(shù)據(jù)頁默認(rèn)16kb的大小，數(shù)據(jù)頁由多個(gè)部分組成，如下圖所示
當(dāng)然這么多概念，阿星只會(huì)挑重點(diǎn)，循循漸進(jìn)的講，所以大家莫慌。
空閑空間
其實(shí)數(shù)據(jù)頁還未寫入數(shù)據(jù)時(shí)，是沒有數(shù)據(jù)行的，只有空閑空間，一旦寫入，空閑空間會(huì)減少一些，直到空閑空間耗盡，具體過程如下圖
數(shù)據(jù)頁滿了，自然需要開辟新的數(shù)據(jù)頁出來存儲(chǔ)數(shù)據(jù)。
但是隨著數(shù)據(jù)頁多起來，它們?cè)趺粗郎弦豁撆c下一頁在那呢？
雙向鏈表
其實(shí)在數(shù)據(jù)頁文件頭中存放了特別多的信息，如當(dāng)前頁號(hào)、頁類型、所屬表空間、上一頁號(hào)、下一頁號(hào)等等。
所以數(shù)據(jù)頁是通過上下頁號(hào)，組成雙向鏈表，如下圖所示
數(shù)據(jù)頁內(nèi)部會(huì)存儲(chǔ)一行一行的數(shù)據(jù)，每一行數(shù)據(jù)都會(huì)按照主鍵大小進(jìn)行排序存儲(chǔ)，同時(shí)每一行數(shù)據(jù)都有指針指向下一行數(shù)據(jù)，組成單向鏈表。
但是這個(gè)結(jié)構(gòu)并不高效，假設(shè)根據(jù)主鍵ID查詢數(shù)據(jù)，只能進(jìn)入數(shù)據(jù)頁，挨個(gè)挨個(gè)的對(duì)單向鏈表遍歷查詢。
所以要再加點(diǎn)料，把二分查找利用起來（不知道二分查找是什么，建議百度，這是最基礎(chǔ)算法）
數(shù)據(jù)頁目錄
這個(gè)料就是數(shù)據(jù)頁目錄部分，數(shù)據(jù)頁目錄存儲(chǔ)的內(nèi)容就是主鍵ID和行位置。
這樣就可以通過數(shù)據(jù)頁目錄走二分查找，快速定位到數(shù)據(jù)頁內(nèi)的數(shù)據(jù)行。
如果只有一個(gè)數(shù)據(jù)頁，倒沒啥問題，哪有成千上萬個(gè)數(shù)據(jù)頁呢，還是得一個(gè)一個(gè)進(jìn)數(shù)據(jù)頁，搜索數(shù)據(jù)頁目錄。
有沒有覺得，這似乎是在做全表掃描？
沒錯(cuò)，在沒有索引的情況下，數(shù)據(jù)庫就是這樣執(zhí)行的。
索引
如果沒有索引，查詢速度可以說是慢到驚人，一般是不能讓查詢走全表掃描的。
因此數(shù)據(jù)庫中的查詢，必須要運(yùn)用索引來加速。
頁分裂
在說索引之前，先說個(gè)前置知識(shí)，索引的核心基礎(chǔ)要求后一個(gè)數(shù)據(jù)頁的主鍵值都大于前面一個(gè)數(shù)據(jù)頁的主鍵值，如果你的主鍵是自增的，可以保證這一點(diǎn)。
但有時(shí)候主鍵并不是自增長的，可能會(huì)出現(xiàn)后一個(gè)數(shù)據(jù)頁的主鍵值小于前一個(gè)數(shù)據(jù)頁的主鍵值。
為了保證索引的核心基礎(chǔ)，有個(gè)交換行數(shù)據(jù)的過程，這個(gè)過程叫頁分裂。
過程如下
數(shù)據(jù)頁0的id=6行數(shù)據(jù)挪到數(shù)據(jù)頁1 數(shù)據(jù)頁1的頁目錄更新 數(shù)據(jù)頁1的id=3行數(shù)據(jù)挪到數(shù)據(jù)頁0 數(shù)據(jù)頁0的頁目錄更新
主鍵目錄
好了，現(xiàn)在我們以主鍵為例，創(chuàng)建一個(gè)主鍵索引，這個(gè)主鍵索引就是主鍵目錄，它會(huì)維護(hù)所有數(shù)據(jù)頁的最小主鍵值與對(duì)應(yīng)的頁號(hào)。
有了主鍵目錄的加持，那找數(shù)據(jù)就非?？炝耍^程如下
二分查找主鍵目錄，找到對(duì)應(yīng)的數(shù)據(jù)頁 進(jìn)入數(shù)據(jù)頁，二分查找數(shù)據(jù)頁目錄，找到對(duì)應(yīng)的行數(shù)據(jù)
可是又來一個(gè)新問題，表里的數(shù)據(jù)可能有幾百萬，幾千萬，甚至幾億條數(shù)據(jù)，會(huì)有大量的數(shù)據(jù)頁，意味著主鍵目錄要存儲(chǔ)大量的數(shù)據(jù)頁號(hào)和最小主鍵值。
可能主鍵目錄存儲(chǔ)不下，就算能存儲(chǔ)，海量的數(shù)據(jù)僅僅靠二分查找也很吃力。
所以InnoDB實(shí)際上是把主鍵目錄數(shù)據(jù)存儲(chǔ)在多個(gè)數(shù)據(jù)頁中，我們把這個(gè)數(shù)據(jù)頁稱為索引頁
索引頁
索引頁，顧名思義，就是存儲(chǔ)索引信息的數(shù)據(jù)頁，在數(shù)據(jù)頁的文件頭部，有頁類型來進(jìn)行區(qū)分。
索引頁會(huì)存儲(chǔ)兩類內(nèi)容，一類是最小主鍵值與索引頁號(hào)，另一類是最小主鍵值與數(shù)據(jù)頁號(hào)。
把大量的索引信息分散在多個(gè)索引頁中，再將多個(gè)索引頁組建成B+樹結(jié)構(gòu)，方便二分查找，結(jié)構(gòu)如下圖
一直說InnoDB的索引是用B+樹來組成的，其實(shí)就是這個(gè)意思，當(dāng)然真實(shí)的B+樹不長這樣，這樣畫還是為了幫助大家理解。
現(xiàn)在整個(gè)搜索過程就十分簡單了
根據(jù)主鍵id二分查找索引頁 找到對(duì)應(yīng)索引頁，再二分查找數(shù)據(jù)頁 進(jìn)入數(shù)據(jù)頁，二分查找數(shù)據(jù)頁目錄，找到對(duì)應(yīng)的行數(shù)據(jù)
寫到這里就結(jié)束了，通過數(shù)據(jù)頁到最后的索引，體會(huì)這個(gè)優(yōu)化的過程，才是本文的重點(diǎn)。
最近面試BAT，整理一份面試資料《Java面試BATJ通關(guān)手冊(cè)》，覆蓋了Java核心技術(shù)、JVM、Java并發(fā)、SSM、微服務(wù)、數(shù)據(jù)庫、數(shù)據(jù)結(jié)構(gòu)等等。
獲取方式：點(diǎn)“在看”，關(guān)注公眾號(hào)并回復(fù)?Java?領(lǐng)取，更多內(nèi)容陸續(xù)奉上。
PS：因公眾號(hào)平臺(tái)更改了推送規(guī)則，如果不想錯(cuò)過內(nèi)容，記得讀完點(diǎn)一下“在看”，加個(gè)“星標(biāo)”，這樣每次新文章推送才會(huì)第一時(shí)間出現(xiàn)在你的訂閱列表里。
點(diǎn)“在看”支持小哈呀，謝謝啦??
