1 InnoDB頁(yè)的概念

InnoDB是一個(gè)將表中的數(shù)據(jù)存儲(chǔ)在磁盤上的存儲(chǔ)引擎，即使我們關(guān)閉并重啟服務(wù)器，數(shù)據(jù)還是存在。而真正處理數(shù)據(jù)的過程發(fā)生在內(nèi)存中，所以需要把磁盤中的數(shù)據(jù)加載到內(nèi)存中，所以需要把磁盤中的數(shù)據(jù)加載到內(nèi)存中。如果處理寫入和修改請(qǐng)求，還需要將內(nèi)存中的內(nèi)容刷新到磁盤上。而我們知道讀寫磁盤的速度非常慢，與讀寫內(nèi)存差了幾個(gè)數(shù)量級(jí)。當(dāng)我們想從表中獲取某些記錄時(shí)，InnoDB存儲(chǔ)引擎需要一條一條的把記錄從磁盤上讀出來么？不，那樣會(huì)慢死，InnoDB采取的方式是，將數(shù)據(jù)劃分為若干個(gè)頁(yè)，以頁(yè)作為磁盤和內(nèi)存之間交互的基本單位。InnoDB中頁(yè)的大小一般為16KB。也就是在一般情況下，一次最少?gòu)拇疟P中讀取16KB的內(nèi)容到內(nèi)存中，一次最少把內(nèi)存中的16KB內(nèi)容刷新到磁盤中。

2 數(shù)據(jù)頁(yè)的結(jié)構(gòu)

存放表中記錄的叫索引頁(yè)也叫數(shù)據(jù)頁(yè)，數(shù)據(jù)頁(yè)代表的這塊16KB大小的存儲(chǔ)空間可以劃分為多個(gè)部分，不同部分有不同功能。

我們自己存儲(chǔ)的記錄會(huì)按照指定的行格式存儲(chǔ)到User Records部分，但是一開始生成頁(yè)的時(shí)候，其實(shí)并沒有User Records部分，每當(dāng)插入一條記錄時(shí)，都會(huì)從Free Space部分申請(qǐng)一個(gè)記錄大小的空間，并將這個(gè)空間劃分到User Records部分。當(dāng)Free Records部分的空間全部被User Records部分替代掉之后，也就意味著這個(gè)頁(yè)被用完了，此時(shí)如果還有新的記錄插入，就需要去申請(qǐng)頁(yè)了。

3 記錄在頁(yè)中的存儲(chǔ)

假如向page_demo表中插入4條記錄，那么這4條記錄的存儲(chǔ)方式為：

insert into page_demo values(1,100,"aaaa"),(2,200,"bbbb"),(3,300,"cccc"),(4,400,"dddd");

無論向頁(yè)中插入了多少條記錄，InnoDB規(guī)定，任何用戶記錄都比infimum記錄大，任何用戶記錄都不supermum小。

通過記錄的存儲(chǔ)方式可以看到，記錄按照主鍵從小到大的順序形成了一個(gè)單向鏈表，通過一條記錄可以找到它的下一條記錄，下一條記錄指的并不是插入順序中的下一條記錄，而是按照主鍵值由小到大的順序排列的下一條記錄，而且規(guī)定infimum記錄的下一條記錄就是本頁(yè)中主鍵值最小的用戶記錄，本頁(yè)中主鍵值最大的用戶記錄的下一條記錄就是supermum記錄，supermum記錄是單向鏈表中的最后一個(gè)節(jié)點(diǎn)。

無論怎么對(duì)頁(yè)中的記錄進(jìn)行增刪改查操作，InnoDB始終會(huì)維護(hù)記錄的一個(gè)單向鏈表，鏈表中的各個(gè)節(jié)點(diǎn)是按照主鍵值由小到大的順序鏈接起來的。

4 Page Directory頁(yè)目錄

我們知道記錄頁(yè)是按照主鍵值由小到大的順序串聯(lián)成了單向鏈表，如果想根據(jù)主鍵值查找頁(yè)中的某條記錄，該咋辦呢？比如下面的查詢語句：

select * from page_demo where c1=3;

最笨的方法就是從Infimum記錄開始，沿著單向鏈表一直往后找，而且在找的時(shí)候可以投機(jī)取巧，因?yàn)殒湵碇懈鱾€(gè)記錄的值是按照從小到大的順序排列的，所以當(dāng)鏈表中的某個(gè)節(jié)點(diǎn)記錄的主鍵值大于想要查找的主鍵值時(shí)，就可以停止查找了。

當(dāng)頁(yè)中存儲(chǔ)的記錄數(shù)量比較少時(shí)，這種方法用起來沒有啥問題，但是，如果一個(gè)頁(yè)中存儲(chǔ)了非常多的記錄，遍歷操作對(duì)性能來說還是有損耗的，所以遍歷查找是一個(gè)笨方法，為此InnoDB設(shè)計(jì)了Page Directory頁(yè)目錄。

(1) 將所有正常的記錄（包括infinmum和supermum記錄）劃分為幾個(gè)組。InnoDB對(duì)每個(gè)分組的條數(shù)是有規(guī)定的，infimum記錄所在的分組只能有一條記錄，supermum記錄所在的分組擁有的記錄數(shù)只能在18條之間，剩下的分組中記錄的條數(shù)范圍只能在48之間。

(2) 將每個(gè)組中最后一條記錄在頁(yè)面中的地址偏移量單獨(dú)提取出來按順序存儲(chǔ)到靠近頁(yè)尾部的地方，這個(gè)地方就是Page Directory。

比如，現(xiàn)在page_demo有6條記錄，InnoDB會(huì)把他們分成2個(gè)組，第一組只有一個(gè)infimum記錄，第二組是剩余的5條記錄，2個(gè)組就對(duì)應(yīng)著兩個(gè)槽，每個(gè)槽存放著每個(gè)組中最大的那條記錄在頁(yè)面中的地址偏移量。

由于現(xiàn)在page_demo表中的記錄太少，無法掩飾在添加頁(yè)目錄之后是如何加快查找速度的，所以再往page_demo表中添加一些記錄。

insert into page_demo 
values(1,100,"aaaa"),(2,200,"bbbb"),(3,300,"cccc"),(4,400,"dddd"),(5,500,"eeee"),(6,600,"ffff"),(7,700,"gggg"),(8,800,"hhhh"),(9,900,"iiii"),(10,1000,"jjjj"),(11,1100,"kkkk"),(12,1200,"llll"),(13,1300,"mmmm")，(14,1400,"nnnn")，(15,1500,"oooo"),
(16,1600,"pppp")

現(xiàn)在頁(yè)中就一共有18條記錄了（包括infimum記錄和supermum記錄），這些記錄被分成了5個(gè)組，因?yàn)楦鱾€(gè)槽之間是挨著的，而且他們代表的記錄的主鍵值都是從小到大排序的，所以可以使用二分法來快速查找。5個(gè)槽的編號(hào)跟別為0,1,2,3,4，所以初始情況下最低的槽就是low=0,最高的槽就是high=4，假如我們想要尋找主鍵值為6的記錄，過程就是這樣的：

(1) 計(jì)算中間槽的位置：(0+4)/2=2，查看槽2對(duì)應(yīng)記錄的主鍵值8；又因?yàn)?>6，所以設(shè)置high=2，low保持不變。

(2) 重新計(jì)算中間槽的位置：(0+2)/2=1，查看槽1對(duì)應(yīng)的記錄的主鍵值為4，又因?yàn)?<6，所以設(shè)置low=1，high保持不變。

(3) 因?yàn)?code>high-low=1，所以主鍵值為6的記錄在槽2對(duì)應(yīng)的組中，此時(shí)需要找到槽2所在分組中主鍵值最小的那條記錄，然后沿著單向鏈表遍歷槽2中的記錄。

綜上所述，在一個(gè)數(shù)據(jù)頁(yè)中查找指定主鍵值的記錄時(shí)，過程分為2步：

(1) 通過二分法確定該記錄所在分組對(duì)應(yīng)的槽，然后找到該槽所在分組中主鍵值最小的那條記錄。

(2) 通過記錄的next_record屬性遍歷該槽所在分組中的各個(gè)記錄。

5 File Header文件頭部

InnoDB是以頁(yè)為單位存放數(shù)據(jù)的，有時(shí)在存放某種類型的數(shù)據(jù)時(shí)，占用的空間非常大。InnoDB可能無法一次性為這么多數(shù)據(jù)分配一個(gè)非常大的存儲(chǔ)空間，而如果分散到多個(gè)不連續(xù)的頁(yè)中進(jìn)行存儲(chǔ)，則需要把這些也關(guān)聯(lián)起來，FIL_PAGE_PREV和FIL_PAGE_NEXT就分別代表本數(shù)據(jù)頁(yè)的上一個(gè)頁(yè)和下一個(gè)頁(yè)的頁(yè)號(hào)。這樣通過建立一個(gè)雙向鏈表就把許許多多的頁(yè)串聯(lián)起來了，而無須這些也在物理上真正連著。所以存儲(chǔ)記錄的數(shù)據(jù)頁(yè)其實(shí)可以組成一個(gè)雙向鏈表。

6 InnoDB頁(yè)和記錄的關(guān)系

各個(gè)數(shù)據(jù)頁(yè)可以組成一個(gè)雙向鏈表，而每個(gè)數(shù)據(jù)頁(yè)中的記錄會(huì)按照主鍵值從小到大的順序組成一個(gè)單向鏈表，每個(gè)數(shù)據(jù)頁(yè)都會(huì)為存儲(chǔ)在它里面的記錄生成一個(gè)頁(yè)目錄，在通過主鍵查找某條記錄的時(shí)候可以在頁(yè)目錄中使用二分法快速定位到對(duì)應(yīng)的槽，然后遍歷該槽對(duì)應(yīng)分組中的記錄即可快速找到指定的記錄。

7 沒有索引時(shí)查找記錄

1、在一個(gè)頁(yè)中查找：

假設(shè)現(xiàn)在表中的記錄較少，所有的記錄都可以存放在一個(gè)頁(yè)中，在查找記錄時(shí)，可以根據(jù)搜索條件的不同可以分為兩種情況：

(1) 以主鍵為搜索條件：可以在頁(yè)目錄中使用二分法快速定位到指定的槽，然后遍歷該槽對(duì)應(yīng)分組中的記錄，即可快速定位到指定的記錄。

(2) 以其他列作為搜索條件：對(duì)于非主鍵列的查找就沒有那么幸運(yùn)了，因?yàn)樵跀?shù)據(jù)頁(yè)中并沒有為非主鍵列建立所謂的頁(yè)目錄，所以無法通過二分法快速定位相應(yīng)的槽，在這種情況下只能從Infimum記錄開始依次遍歷單向鏈表中的每條記錄，然后對(duì)比每條記錄是否符合搜索條件，這種查找的效率非常低。

2、在很多頁(yè)中查找：

在很多時(shí)候，表中存放的記錄都是非常多的，需要用到好多的數(shù)據(jù)頁(yè)來存儲(chǔ)這些記錄。在很多頁(yè)中查找記錄可以分為兩個(gè)步驟：

(1) 定位到記錄所在的頁(yè)；

(2) 從所在的頁(yè)內(nèi)查找相應(yīng)的記錄；

在沒有索引的情況下，無論是根據(jù)主鍵列還是其他的列進(jìn)行查找，由于我們不能快速的定位到記錄所在的頁(yè)，所以只能從第一頁(yè)沿著雙向鏈表一直往下找。在每一頁(yè)中我們根據(jù)上面說的查找方式去查找指定的記錄。因?yàn)橐闅v所有的數(shù)據(jù)頁(yè)，所以這種方式顯然是超級(jí)耗時(shí)的。如果一個(gè)表有一億條記錄，使用這種方式去查找記錄，估計(jì)要到猴年馬月才能查到結(jié)果，所以就需要一種能高效完成搜索的方法，即索引。

總結(jié)

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注服務(wù)器之家的更多內(nèi)容!  

原文地址：https://hengheng.blog.csdn.net/article/details/122973895