大家都知道 MySQL 的數(shù)據(jù)都是保存在磁盤的，那具體是保存在哪個文件呢？MySQL 存儲的行為是由存儲引擎實現(xiàn)的，MySQL 支持多種存儲引擎，不同的存儲引擎保存的文件自然也不同。InnoDB 是我們常用的存儲引擎，也是 MySQL 默認的存儲引擎。本文主要以 InnoDB 存儲引擎展開討論。InnoDB是一個將表中的數(shù)據(jù)存儲到磁盤上的存儲引擎。而真正處理數(shù)據(jù)的過程是發(fā)生在內(nèi)存中的，所以需要把磁盤中的數(shù)據(jù)加載到內(nèi)存中，如果是處理寫入或修改請求的話，還需要把內(nèi)存中的內(nèi)容刷新到磁盤上。而我們知道讀寫磁盤的速度非常慢，和內(nèi)存讀寫差了幾個數(shù)量級。所以當我們想從表中獲取某些記錄時，InnoDB存儲引擎需要一條一條的把記錄從磁盤上讀出來么？想要了解這個問題，我們首先需要了解InnoDB的存儲結(jié)構(gòu)是怎樣的。InnoDB采取的方式是：將數(shù)據(jù)劃分為若干個頁，以頁作為磁盤和內(nèi)存之間交互的基本單位innodb_page_size選項指定了MySQL實例的所有InnoDB表空間的頁面大小。這個值是在創(chuàng)建實例時設(shè)置的，之后保持不變。有效值為64KB，32KB，16KB(默認值 )，8kB和4kB。也就是在一般情況下，一次最少從磁盤中讀取16KB的內(nèi)容到內(nèi)存中，一次最少把內(nèi)存中的16KB內(nèi)容刷新到磁盤中。我們平時是以記錄為單位來向表中插入數(shù)據(jù)的，這些記錄在磁盤上的存放方式也被稱為行格式或者記錄格式。一行記錄可以以不同的格式存在InnoDB中，行格式分別是compact、redundant、dynamic和compressed行格式。可以在創(chuàng)建或修改的語句中指定行格式：CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名稱;ALTER TABLE 表名 ROW_FORMAT=行格式名稱;show table status like '<數(shù)據(jù)表名>';
mysql5.0之前默認的行格式是redundant，mysql5.0之后的默認行格式為compact ， 5.7之后的默認行格式為dynamiccompact格式
記錄的額外信息：分別是變長字段長度列表、NULL值列表和記錄頭信息mysql中支持一些變長數(shù)據(jù)類型（比如VARCHAR(M)、TEXT等），它們存儲數(shù)據(jù)占用的存儲空間不是固定的，而是會隨著存儲內(nèi)容的變化而變化。在Compact行格式中，把所有變長字段的真實數(shù)據(jù)占用的字節(jié)長度都存放在記錄的開頭部位，從而形成一個變長字段長度列表，各變長字段數(shù)據(jù)占用的字節(jié)數(shù)按照列的順序逆序存放NULL值列表：Compact格式會把所有可以為NULL的列統(tǒng)一管理起來，存在一個NULL值列表，如果表中沒有允許為NULL的列，則NULL值列表也不復(fù)存在了。表中的某些列可能存儲NULL值，如果把這些NULL值都放到記錄的真實數(shù)據(jù)中存儲會很浪費空間，所以Compact行格式把這些值為NULL的列統(tǒng)一管理起來，存儲到NULL值列表中，它的處理過程是這樣的：首先統(tǒng)計表中允許存儲NULL的列有哪些。
根據(jù)列的實際值，用0或者1填充NULL值列表，1代表該列的值為空，0代表該列的值不為空。
如果表中沒有允許存儲 NULL 的列，則 NULL值列表 也不存在了。
| | |
| | |
| | |
| | |
| | B+樹非葉子節(jié)點中最小記錄都會添加該標記 |
| | |
| | |
| | |
| | |
redundant 格式
與compact 格式相比, 沒有了 變長字段列表以及 NULL值列表, 取而代之的是 記錄了所有真實數(shù)據(jù)的偏移地址表 ，偏移地址表 是倒序排放的, 但是計算偏移量卻還是正序開始的從row_id作為第一個, 第一個從0開始累加字段對應(yīng)的字節(jié)數(shù)。在記錄頭信息中, 大部分字段和compact 中的相同，但是對比compact多了。n_field(記錄列的數(shù)量)、1byte_offs_flag(字段長度列表每一列占用的字節(jié)數(shù))，少了record_type字段。因為redundant是mysql 5.0 以前就在使用的一種格式, 已經(jīng)非常古老, 使用頻率非常的低，這里就不過多表述。dynamic 格式
在現(xiàn)在 mysql 5.7 的版本中,使用的格式就是 dynamic。dynamic 和 compact 基本是相同的，只有在溢出頁的處理上面,有所不同。在compact行格式中，對于占用存儲空間非常大的列，在記錄的真實數(shù)據(jù)處只會存儲該列的前768個字節(jié)的數(shù)據(jù)，把剩余的數(shù)據(jù)分散存儲在幾個其他的頁中，然后記錄的真實數(shù)據(jù)處用20個字節(jié)存儲指向這些頁的地址，從而可以找到剩余數(shù)據(jù)所在的頁。這種在本記錄的真實數(shù)據(jù)處只會存儲該列的前768個字節(jié)的數(shù)據(jù)和一個指向其他頁的地址，然后把剩下的數(shù)據(jù)存放到其他頁中的情況就叫做行溢出，存儲超出768字節(jié)的那些頁面也被稱為溢出頁（uncompresse blob page）。dynamic中會直接在真實數(shù)據(jù)區(qū)記錄 20字節(jié) 的溢出頁地址, 而不再去額外記錄一部分的數(shù)據(jù)了。MySQL中規(guī)定一個頁中至少存放兩行記錄。簡單理解：因為B+樹的特性，如果不存儲至少2條記錄，則這個B+樹是沒有意義的，形不成一個有效的索引。每個頁除了存放我們的記錄以外，也需要存儲一些額外的信息，大概132個字節(jié)。每個記錄需要的額外信息是27字節(jié)。假設(shè)一個列中存儲的數(shù)據(jù)字節(jié)數(shù)為n，如要要保證該列不發(fā)生溢出，則需要滿足：132 + 2×(27 + n) < 16384 結(jié)果是n < 8099。也就是說如果一個列中存儲的數(shù)據(jù)小于8099個字節(jié)，那么該列就不會成為溢出列。如果表中有多個列，那么這個值更小。compressed 格式
compressed 格式將會在Dynamic 的基礎(chǔ)上面進行壓縮處理特別是對溢出頁的壓縮處理，存儲在其中的行數(shù)據(jù)會以zlib的算法進行壓縮，因此對于blob、text這類大長度類型的數(shù)據(jù)能夠進行非常有效的存儲。但compressed格式其實也是以時間換空間，性能并不友好，并不推薦在常見的業(yè)務(wù)中使用。InnoDB數(shù)據(jù)頁結(jié)構(gòu)
數(shù)據(jù)頁代表的這塊16KB大小的存儲空間可以被劃分為多個部分，不同部分有不同的功能每當我們插入一條記錄，都會從Free Space部分，也就是尚未使用的存儲空間中申請一個記錄大小的空間劃分到User Records部分，當Free Space部分的空間全部被User Records部分替代掉之后，也就意味著這個頁使用完了，如果還有新的記錄插入的話，就需要去申請新的頁了，這個過程的圖示如下：先創(chuàng)建一個表： CREATE TABLE test( a1 INT, a2 INT, a3 VARCHAR(100), PRIMARY KEY (a1) ) CHARSET=ascii ROW_FORMAT=Compact; test表中插入幾條記錄：INSERT INTO test VALUES(1, 10, 'aaa'); INSERT INTO test VALUES(2, 20, 'bbb'); INSERT INTO test VALUES(3, 30, 'ccc'); INSERT INTO test VALUES(4, 40, 'ddd');
這些記錄，就如下圖所示，存儲在User Rcords里delete_mask這個屬性標記著當前記錄是否被刪除。這些被刪除的記錄之所以不立即從磁盤上移除，是因為移除它們之后把其他的記錄在磁盤上重新排列需要性能消耗，所以只是打一個刪除標記而已。所有被刪除掉的記錄都會組成一個所謂的垃圾鏈表，在這個鏈表中的記錄占用的空間稱之為所謂的可重用空間，之后如果有新記錄插入到表中的話，可能把這些被刪除的記錄占用的存儲空間覆蓋掉。
min_rec_maskB+樹的每層非葉子節(jié)點中的最小記錄都會添加該標記，min_rec_mask值都是0，意味著它們都不是B+樹的非葉子節(jié)點中的最小記錄。
n_owned在頁目錄分組時使用，每個組的最后一條記錄（也就是組內(nèi)最大的那條記錄）的頭信息中的n_owned屬性表示該記錄擁有多少條記錄，也就是該組內(nèi)共有幾條記錄。
heap_no這個屬性表示當前記錄在本頁中的位置，從圖中可以看出來，我們插入的4條記錄在本頁中的位置分別是：2、3、4、5。heap_no值為0和1的記錄，稱為偽記錄或者虛擬記錄。這兩個偽記錄一個代表最小記錄，一個代表最大記錄。
record_type這個屬性表示當前記錄的類型，一共有4種類型的記錄，0表示普通記錄，1表示B+樹非葉節(jié)點記錄，2表示最小記錄，3表示最大記錄。
next_record它表示從當前記錄的真實數(shù)據(jù)到下一條記錄的真實數(shù)據(jù)的地址偏移量。比方說第一條記錄的next_record值為32，意味著從第一條記錄的真實數(shù)據(jù)的地址處向后找32個字節(jié)便是下一條記錄的真實數(shù)據(jù)。下一條記錄指得并不是按照我們插入順序的下一條記錄，而是按照主鍵值由小到大的順序的下一條記錄。而且規(guī)定Infimum記錄（也就是最小記錄） 的下一條記錄就是本頁中主鍵值最小的用戶記錄，而本頁中主鍵值最大的用戶記錄的下一條記錄就是 Supremum記錄（也就是最大記錄）。
從圖中可以看出來，我們的記錄按照主鍵從小到大的順序形成了一個單鏈表。現(xiàn)在我們了解了記錄在頁中按照主鍵值由小到大順序串聯(lián)成一個單鏈表，單向鏈表的特點就是插入、刪除非常方便，但是檢索效率不高，最差的情況下需要遍歷鏈表上的所有節(jié)點才能完成檢索。因此在頁結(jié)構(gòu)中專門設(shè)計了頁目錄這個模塊，專門給記錄做一個目錄，通過二分查找法的方式進行檢索，提升效率。1：將所有正常的記錄（包括最大和最小記錄，不包括標記為已刪除的記錄）劃分為幾個組。2：每個組的最后一條記錄（也就是組內(nèi)最大的那條記錄）的頭信息中的n_owned屬性表示該記錄擁有多少條記錄，也就是該組內(nèi)共有幾條記錄。3：將每個組的最后一條記錄的地址偏移量單獨提取出來，用作查找。第一：第一個小組，也就是最小記錄所在的分組只能有1個記錄;第二：最后一個小組，就是最大記錄所在的分組，只能有1-8條記錄;第三：剩下的分組中記錄的條數(shù)范圍只能在是 4-8 條之間；初始情況下一個數(shù)據(jù)頁里只有最小記錄和最大記錄兩條記錄，它們分屬于兩個分組。
之后每插入一條記錄，都會從頁目錄中找到主鍵值比本記錄的主鍵值大并且差值最小的槽，然后把該槽對應(yīng)的記錄的n_owned值加1，表示本組內(nèi)又添加了一條記錄，直到該組中的記錄數(shù)等于8個。
在一個組中的記錄數(shù)等于8個后再插入一條記錄時，會將組中的記錄拆分成兩個組，一個組中4條記錄，另一個5條記錄。這個過程會在頁目錄中新增一個槽來記錄這個新增分組中最大的那條記錄的偏移量。
INSERT INTO test VALUES(5, 50, 'eee'); INSERT INTO test VALUES(6, 60, 'fff'); INSERT INTO test VALUES(7, 70, 'ggg'); INSERT INTO test VALUES(8, 80, 'hhh'); INSERT INTO test VALUES(9, 90, 'iii');INSERT INTO test VALUES(10, 100, 'jjj');INSERT INTO test VALUES(11, 110, 'kkk');INSERT INTO test VALUES(12, 120, 'lll');
這里為了便于理解，圖中只保留了用戶記錄頭信息中的n_owned和next_record屬性。
因為各個槽代表的記錄的主鍵值都是從小到大排序的，所以我們可以使用二分法來進行快速查找。
所以在一個數(shù)據(jù)頁中查找指定主鍵值的記錄的過程分為兩步：
1.通過二分法確定該記錄所在的槽，并找到該槽所在分組中主鍵值最大的那條記錄。2.通過記錄的next_record屬性遍歷該槽所在的組中的各個記錄。
比方說我們查找主鍵值為x的記錄，計算中間槽的位置(min+max)/2 =mid,查看mid槽對應(yīng)的主鍵值y，若x<y,則min不變，max=mid，若x>y，則max不變，min=mid。依此類推。
舉例：我們想找主鍵值為6的記錄，過程是這樣的計算中間槽的位置：(0+3)/2=1，所以查看槽1對應(yīng)記錄的主鍵值為4，因為4 < 6，所以設(shè)置low=1，high保持不變。因為high - low的值為1，所以確定主鍵值為6的記錄在槽2對應(yīng)的組中。我們可以很輕易的拿到槽1對應(yīng)的記錄（主鍵值為4），該條記錄的下一條記錄就是槽2中主鍵值最小的記錄，該記錄的主鍵值為5。所以我們可以從這條主鍵值為5的記錄出發(fā)，遍歷槽2中的各條記錄找到主鍵為6 的數(shù)據(jù)。
注意：若查到數(shù)據(jù)在槽2的分組中，由于槽2是指向最后一個記錄，所以需要向上找一個槽位，定位到上一個槽位最后一行，然后再向下找。
File Header針對各種類型的頁都通用，也就是說不同類型的頁都會以File Header作為第一個組成部分，它描述了一些針對各種頁都通用的一些信息，比方說這個頁的編號是多少，它的上一個頁、下一個頁是誰等。FIL_PAGE_OFFSET每一個頁都有一個單獨的頁號，就跟你的身份證號碼一樣，InnoDB通過頁號來可以唯一定位一個頁。FIL_PAGE_PREV和FIL_PAGE_NEXTFIL_PAGE_PREV和FIL_PAGE_NEXT就分別代表本頁的上一個和下一個頁的頁號。這樣通過建立一個雙向鏈表把許許多多的頁就都串聯(lián)起來了。InnoDB數(shù)據(jù)頁的主要組成部分。各個數(shù)據(jù)頁可以組成一個雙向鏈表，而每個數(shù)據(jù)頁中的記錄會按照主鍵值從小到大的順序組成一個單向鏈表，每個數(shù)據(jù)頁都會為存儲在它里邊兒的記錄生成一個頁目錄。再通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應(yīng)的槽。以主鍵為搜索條件這個查找過程我們已經(jīng)很熟悉了，可以在頁目錄中使用二分法快速定位到對應(yīng)的槽，然后再遍歷該槽對應(yīng)分組中的記錄即可快速找到指定的記錄。
以其他列作為搜索條件對非主鍵列的查找的過程可就不這么幸運了，因為在數(shù)據(jù)頁中并沒有對非主鍵列建立所謂的頁目錄，所以我們無法通過二分法快速定位相應(yīng)的槽。這種情況下只能從最小記錄開始依次遍歷單鏈表中的每條記錄，然后對比每條記錄是不是符合搜索條件。
1：定位到記錄所在的頁。
2：從所在的頁內(nèi)中查找相應(yīng)的記錄。在沒有索引的情況下，不論是根據(jù)主鍵列或者其他列的值進行查找，由于我們并不能快速的定位到記錄所在的頁，所以只能從第一個頁沿著雙向鏈表一直往下找，在每一個頁中根據(jù)我們上面聊過的查找方式去查找指定的記錄。
同樣的，我們以上面建的表test為例，清空插入的數(shù)據(jù)，此時test表為一張空數(shù)據(jù)的表，為了便于講述，我們可以簡單的把test表的行格式理解如下：一個簡單的索引方案：我們?yōu)楦鶕?jù)主鍵值快速定位一條記錄在頁中的位置而設(shè)立的頁目錄，目錄中記錄的數(shù)據(jù)頁需要滿足下一個數(shù)據(jù)頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值。假設(shè)我們的每個數(shù)據(jù)頁最多能存放3條記錄（實際上一個數(shù)據(jù)頁非常大，可以存放下很多記錄），這時候我們向test表插入三條記錄，那么數(shù)據(jù)頁就如圖所示：test表中插入幾條記錄：INSERT INTO test VALUES(1, 10, 'aa'); INSERT INTO test VALUES(2, 20, 'bb'); INSERT INTO test VALUES(4, 40, 'dd');
INSERT INTO test VALUES(3, 30, 'cc');
因為上面定義了，一個頁最多只能放3條記錄，所以我們不得不再分配一個新頁：頁1中用戶記錄最大的主鍵值是4，而頁2中有一條記錄的主鍵值是3，因為4 > 3，所以這就不符合下一個數(shù)據(jù)頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值的要求，所以在插入主鍵值為3的記錄的時候需要伴隨著一次記錄移動，也就是把主鍵值為4的記錄移動到頁2中，然后再把主鍵值為3的記錄插入到頁1中。最后形成如圖所示。真實數(shù)據(jù)存儲中，數(shù)據(jù)頁的編號并不是連續(xù)的，當我們在test表中插入多條記錄后，可能是這樣的效果：因為這些16KB的頁在物理存儲上可能并不挨著，所以如果想從這么多頁中根據(jù)主鍵值快速定位某些記錄所在的頁，我們需要給它們做個目錄，每個頁對應(yīng)一個目錄項，每個目錄項由頁中記錄的最小主鍵值和頁號組成。我們?yōu)樯厦鎺讉€頁做目錄，則如圖：比方說我們想找主鍵值為5的記錄，具體查找過程分兩步：1：先從目錄項中根據(jù)二分法快速確定出主鍵值為5的記錄在目錄2中（因為 4 < 5 < 7），它對應(yīng)的數(shù)據(jù)頁是頁23。
2：再根據(jù)前邊說的在頁中查找記錄的方式去頁23中定位具體的記錄。
在InnoDB中復(fù)用了之前存儲用戶記錄的數(shù)據(jù)頁來存儲目錄項，為了和用戶記錄做一下區(qū)分，我們把這些用來表示目錄項的記錄稱為目錄項記錄。用record_type來區(qū)分普通的用戶記錄還是目錄項記錄。如果表中的數(shù)據(jù)太多，以至于一個數(shù)據(jù)頁不足以存放所有的目錄項記錄，會再多整一個存儲目錄項記錄的頁。所以如果此時我們再向上圖中插入一條主鍵值為10的用戶記錄的話：在查詢時我們需要定位存儲目錄項記錄的頁，但是這些頁在存儲空間中也可能不挨著，如果我們表中的數(shù)據(jù)非常多則會產(chǎn)生很多存儲目錄項記錄的頁，那我們怎么根據(jù)主鍵值快速定位一個存儲目錄項記錄的頁呢？其實也簡單，為這些存儲目錄項記錄的頁再生成一個更高級的目錄，就像是一個多級目錄一樣，大目錄里嵌套小目錄，小目錄里才是實際的數(shù)據(jù)，所以現(xiàn)在各個頁的示意圖就是這樣子：用戶記錄其實都存放在B+樹的最底層的節(jié)點上，這些節(jié)點也被稱為葉子節(jié)點或葉節(jié)點，其余用來存放目錄項的節(jié)點稱為非葉子節(jié)點或者內(nèi)節(jié)點，其中B+樹最上邊的那個節(jié)點也稱為根節(jié)點。
我們上邊介紹的B+樹本身就是一個目錄，或者說本身就是一個索引。它有兩個特點：1：使用記錄主鍵值的大小進行記錄和頁的排序
2：B+樹的葉子節(jié)點存儲的是完整的用戶記錄。我們把具有這兩種特性的B+樹稱為聚簇索引，所有完整的用戶記錄都存放在這個聚簇索引的葉子節(jié)點處。這種聚簇索引并不需要我們在MySQL語句中顯式的使用INDEX語句去創(chuàng)建，InnoDB存儲引擎會自動的為我們創(chuàng)建聚簇索引。另外有趣的一點是，在InnoDB存儲引擎中，聚簇索引就是數(shù)據(jù)的存儲方式（所有的用戶記錄都存儲在了葉子節(jié)點），也就是所謂的索引即數(shù)據(jù)，數(shù)據(jù)即索引。
頁內(nèi)的記錄是按照a2列的大小順序排成一個單向鏈表。
各個存放用戶記錄的頁也是根據(jù)頁中記錄的a2列大小順序排成一個雙向鏈表。
存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據(jù)頁中目錄項記錄的a2列大小順序排成一個雙向鏈表。
B+樹的葉子節(jié)點存儲的并不是完整的用戶記錄，而只是a2列+主鍵這兩個列的值。
目錄項記錄中不再是主鍵+頁號的搭配，而變成了a2列+頁號的搭配。
1：空間上的代價每建立一個索引都要為它建立一棵B+樹，每一棵B+樹的每一個節(jié)點都是一個數(shù)據(jù)頁，一個頁默認會占用16KB的存儲空間。
2：時間上的代價每次對表中的數(shù)據(jù)進行增、刪、改操作時，都需要去修改各個B+樹索引。B+樹每層節(jié)點都是按照索引列的值從小到大的順序排序而組成了雙向鏈表。不論是葉子節(jié)點中的記錄，還是內(nèi)節(jié)點中的記錄（也就是不論是用戶記錄還是目錄項記錄）都是按照索引列的值從小到大的順序而形成了一個單向鏈表。而增、刪、改操作可能會對節(jié)點和記錄的排序造成破壞，所以存儲引擎需要額外的時間進行一些記錄移位，頁面分裂、頁面回收等操作來維護好節(jié)點和記錄的排序。通過對InnoDB存儲邏輯分析，我們可以清楚的了解到mysql中是怎樣對數(shù)據(jù)進行存儲的。并且對索引樹的結(jié)構(gòu)進行分析，幫助我們在工作中更加合理的使用索引。
