1 InnoDB頁的概念
InnoDB是一個將表中的數據存儲在磁盤上的存儲引擎，即使我們關閉并重啟服務器，數據還是存在。而真正處理數據的過程發生在內存中，所以需要把磁盤中的數據加載到內存中，所以需要把磁盤中的數據加載到內存中。如果處理寫入和修改請求，還需要將內存中的內容刷新到磁盤上。而我們知道讀寫磁盤的速度非常慢，與讀寫內存差了幾個數量級。當我們想從表中獲取某些記錄時，InnoDB存儲引擎需要一條一條的把記錄從磁盤上讀出來么？不，那樣會慢死，InnoDB采取的方式是，將數據劃分為若干個頁，以頁作為磁盤和內存之間交互的基本單位。InnoDB中頁的大小一般為16KB。也就是在一般情況下，一次最少從磁盤中讀取16KB的內容到內存中，一次最少把內存中的16KB內容刷新到磁盤中。
2 數據頁的結構
存放表中記錄的叫索引頁也叫數據頁，數據頁代表的這塊16KB大小的存儲空間可以劃分為多個部分，不同部分有不同功能。
我們自己存儲的記錄會按照指定的行格式存儲到User Records部分，但是一開始生成頁的時候，其實并沒有User Records部分，每當插入一條記錄時，都會從Free Space部分申請一個記錄大小的空間，并將這個空間劃分到User Records部分。當Free Records部分的空間全部被User Records部分替代掉之后，也就意味著這個頁被用完了，此時如果還有新的記錄插入，就需要去申請頁了。
3 記錄在頁中的存儲
假如向page_demo表中插入4條記錄，那么這4條記錄的存儲方式為：
insert into page_demo values(1,100,"aaaa"),(2,200,"bbbb"),(3,300,"cccc"),(4,400,"dddd");
無論向頁中插入了多少條記錄，InnoDB規定，任何用戶記錄都比infimum記錄大，任何用戶記錄都不supermum小。
通過記錄的存儲方式可以看到，記錄按照主鍵從小到大的順序形成了一個單向鏈表，通過一條記錄可以找到它的下一條記錄，下一條記錄指的并不是插入順序中的下一條記錄，而是按照主鍵值由小到大的順序排列的下一條記錄，而且規定infimum記錄的下一條記錄就是本頁中主鍵值最小的用戶記錄，本頁中主鍵值最大的用戶記錄的下一條記錄就是supermum記錄，supermum記錄是單向鏈表中的最后一個節點。
無論怎么對頁中的記錄進行增刪改查操作，InnoDB始終會維護記錄的一個單向鏈表，鏈表中的各個節點是按照主鍵值由小到大的順序鏈接起來的。
4 Page Directory頁目錄
我們知道記錄頁是按照主鍵值由小到大的順序串聯成了單向鏈表，如果想根據主鍵值查找頁中的某條記錄，該咋辦呢？比如下面的查詢語句：
select * from page_demo where c1=3;
最笨的方法就是從Infimum記錄開始，沿著單向鏈表一直往后找，而且在找的時候可以投機取巧，因為鏈表中各個記錄的值是按照從小到大的順序排列的，所以當鏈表中的某個節點記錄的主鍵值大于想要查找的主鍵值時，就可以停止查找了。
當頁中存儲的記錄數量比較少時，這種方法用起來沒有啥問題，但是，如果一個頁中存儲了非常多的記錄，遍歷操作對性能來說還是有損耗的，所以遍歷查找是一個笨方法，為此InnoDB設計了Page Directory頁目錄。
(1) 將所有正常的記錄（包括infinmum和supermum記錄）劃分為幾個組。InnoDB對每個分組的條數是有規定的，infimum記錄所在的分組只能有一條記錄，supermum記錄所在的分組擁有的記錄數只能在18條之間，剩下的分組中記錄的條數范圍只能在48之間。
(2) 將每個組中最后一條記錄在頁面中的地址偏移量單獨提取出來按順序存儲到靠近頁尾部的地方，這個地方就是Page Directory。
比如，現在page_demo有6條記錄，InnoDB會把他們分成2個組，第一組只有一個infimum記錄，第二組是剩余的5條記錄，2個組就對應著兩個槽，每個槽存放著每個組中最大的那條記錄在頁面中的地址偏移量。
由于現在page_demo表中的記錄太少，無法掩飾在添加頁目錄之后是如何加快查找速度的，所以再往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")
現在頁中就一共有18條記錄了（包括infimum記錄和supermum記錄），這些記錄被分成了5個組，因為各個槽之間是挨著的，而且他們代表的記錄的主鍵值都是從小到大排序的，所以可以使用二分法來快速查找。5個槽的編號跟別為0,1,2,3,4，所以初始情況下最低的槽就是low=0,最高的槽就是high=4，假如我們想要尋找主鍵值為6的記錄，過程就是這樣的：
(1) 計算中間槽的位置：(0+4)/2=2，查看槽2對應記錄的主鍵值8；又因為8>6，所以設置high=2，low保持不變。
(2) 重新計算中間槽的位置：(0+2)/2=1，查看槽1對應的記錄的主鍵值為4，又因為4<6，所以設置low=1，high保持不變。
(3) 因為high-low=1，所以主鍵值為6的記錄在槽2對應的組中，此時需要找到槽2所在分組中主鍵值最小的那條記錄，然后沿著單向鏈表遍歷槽2中的記錄。
綜上所述，在一個數據頁中查找指定主鍵值的記錄時，過程分為2步：
(1) 通過二分法確定該記錄所在分組對應的槽，然后找到該槽所在分組中主鍵值最小的那條記錄。
(2) 通過記錄的next_record屬性遍歷該槽所在分組中的各個記錄。
5 File Header文件頭部
InnoDB是以頁為單位存放數據的，有時在存放某種類型的數據時，占用的空間非常大。InnoDB可能無法一次性為這么多數據分配一個非常大的存儲空間，而如果分散到多個不連續的頁中進行存儲，則需要把這些也關聯起來，FIL_PAGE_PREV和FIL_PAGE_NEXT就分別代表本數據頁的上一個頁和下一個頁的頁號。這樣通過建立一個雙向鏈表就把許許多多的頁串聯起來了，而無須這些也在物理上真正連著。所以存儲記錄的數據頁其實可以組成一個雙向鏈表。
6 InnoDB頁和記錄的關系
各個數據頁可以組成一個雙向鏈表，而每個數據頁中的記錄會按照主鍵值從小到大的順序組成一個單向鏈表，每個數據頁都會為存儲在它里面的記錄生成一個頁目錄，在通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應的槽，然后遍歷該槽對應分組中的記錄即可快速找到指定的記錄。
7 沒有索引時查找記錄
1、在一個頁中查找：
假設現在表中的記錄較少，所有的記錄都可以存放在一個頁中，在查找記錄時，可以根據搜索條件的不同可以分為兩種情況：
(1) 以主鍵為搜索條件：可以在頁目錄中使用二分法快速定位到指定的槽，然后遍歷該槽對應分組中的記錄，即可快速定位到指定的記錄。
(2) 以其他列作為搜索條件：對于非主鍵列的查找就沒有那么幸運了，因為在數據頁中并沒有為非主鍵列建立所謂的頁目錄，所以無法通過二分法快速定位相應的槽，在這種情況下只能從Infimum記錄開始依次遍歷單向鏈表中的每條記錄，然后對比每條記錄是否符合搜索條件，這種查找的效率非常低。
2、在很多頁中查找：
在很多時候，表中存放的記錄都是非常多的，需要用到好多的數據頁來存儲這些記錄。在很多頁中查找記錄可以分為兩個步驟：
(1) 定位到記錄所在的頁；
(2) 從所在的頁內查找相應的記錄；
在沒有索引的情況下，無論是根據主鍵列還是其他的列進行查找，由于我們不能快速的定位到記錄所在的頁，所以只能從第一頁沿著雙向鏈表一直往下找。在每一頁中我們根據上面說的查找方式去查找指定的記錄。因為要遍歷所有的數據頁，所以這種方式顯然是超級耗時的。如果一個表有一億條記錄，使用這種方式去查找記錄，估計要到猴年馬月才能查到結果，所以就需要一種能高效完成搜索的方法，即索引。
總結
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關注服務器之家的更多內容!
原文地址：https://hengheng.blog.csdn.net/article/details/122973895
