Mysql第二篇—InnoDB數(shù)據(jù)存儲結(jié)構(gòu)

數(shù)據(jù)庫的存儲結(jié)構(gòu): 頁

索引結(jié)構(gòu)給我們提供了高效的索引方式, 不過索引信息以及數(shù)據(jù)記錄都是保存在文件上的(innodb的ibd文件, MyISAM的MyI和MyD文件), 確切的說是存儲在頁結(jié)構(gòu)中. 另一方面, 索引是在存儲引擎中實現(xiàn)的, MySQL服務(wù)器上的存儲引擎負(fù)責(zé)對表中數(shù)據(jù)的讀取和寫入工作. 不同存儲引擎中存放的格式一般是不同的, 甚至有的存儲引擎比如Memory都不用磁盤來存儲數(shù)據(jù)

由于InnoDB是MySQL的默認(rèn)存儲引擎, 所以本章剖析InnoDB存儲引擎的數(shù)據(jù)結(jié)構(gòu)

磁盤與內(nèi)存交互的基本單位 : 頁
InnoDB將數(shù)據(jù)劃分為若干個頁, InnoDB中頁的大小默認(rèn)為16KB。
以頁作為磁盤和內(nèi)存之間交互的基本單位, 也就是一次最少從磁盤中讀取16KB的內(nèi)容到內(nèi)存中, 一次最少把內(nèi)存中的16KB內(nèi)容刷新到磁盤中. 也就是說, 在數(shù)據(jù)庫中, 不論讀一行還是讀多行, 都是將這些行所在的頁進(jìn)行加載. 也就是說, 數(shù)據(jù)庫管理存儲空間的基本單位是頁(Page), 數(shù)據(jù)庫I/O操作的最小單位是頁， 一個頁中可以存儲多行記錄。
記錄是按照行來存儲的, 但是數(shù)據(jù)庫的讀取并不以行為單位, 否則一次讀取(也就是一次I/O操作)只能處理一行數(shù)據(jù), 效率會非常低。

頁結(jié)構(gòu)概述
頁a, 頁b, 頁c… 頁n這些頁可以不在物理結(jié)構(gòu)上相連, 只要通過雙向鏈表相關(guān)聯(lián)即可. 每個數(shù)據(jù)頁中的記錄會按照主鍵值從小到達(dá)的順序組成一個單向鏈表, 每個數(shù)據(jù)頁都會為存儲在它里面的記錄生成一個頁目錄, 在通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應(yīng)的槽位, 然后再遍歷該槽對應(yīng)分組中的記錄即可快速找到指定的記錄。

• 頁目錄等我們下面詳細(xì)介紹頁結(jié)構(gòu)的會講解
• 注意: 這些頁是同一層的頁, 可以不在物理結(jié)構(gòu)上相連, 但是頁分配的時候確實是相連的, 但是不是同一層相連。就是B+樹比如有三層，而且是聚簇索引，那么第二層就是目錄項頁（里面不包含一行的全部記錄），第二層有好多個頁，但是這些頁在物理存儲上并不是連續(xù)的，比如可能有三個頁，分別是23，12,33 ；但是呢，如果把B+樹所有層的頁都算上，它是一個段連續(xù)的頁，比如說從1到100；
• 但是注意: 數(shù)據(jù)庫分配的單位是段, 段又分為了索引段和數(shù)據(jù)段, 數(shù)據(jù)段就是索引結(jié)構(gòu)的葉子結(jié)點層, 所以說其實葉子結(jié)點層的頁是相連的。

頁的大小
不同的數(shù)據(jù)庫管理系統(tǒng)(簡稱DBMS)的頁大小不同. 比如在MySQL的InnoDB存儲引擎中, 默認(rèn)頁的大小是16KB, 我們可以通過下面的命令來進(jìn)行查看:

show variables like '%innodb_page_size';

SQL Server中頁的大小為8KB, 而在Oracle中我們用術(shù)語"塊"(Block)來代表頁, Oracle支持的塊大小為2KB, 4KB, 8KB, 16K, 32KB, 64KB。

頁的上層結(jié)構(gòu)
另外在數(shù)據(jù)庫中, 還存在著區(qū)(Extent), 段(Segment)和表空間(Tablespace)的概念.。行, 頁, 區(qū), 段, 表空間的關(guān)系如下圖所示:
區(qū)(Extent)是比頁大一級的存儲結(jié)構(gòu), 在InnoDB存儲引擎中, 一個區(qū)會分配64個連續(xù)的頁。因為InnoDB中的頁的大小默認(rèn)是16KB, 所以一個區(qū)的大小是64*16KB = 1MB。

在mysql中一個表中的數(shù)據(jù)量過大的時候，有一個優(yōu)化方式是分區(qū)，就是創(chuàng)建表的時候使用partition by關(guān)鍵字，從外部來看分區(qū)就是給原表分成好多個子表。比如原表中有一個時間time字段，那么我們可以把時間是1月份的記錄放到month1分區(qū)，把時間是2月份的記錄放到month2分區(qū)，。。。把時間是12月份記錄的放到month12分區(qū)。首先需要知道一個知識點，就是一個頁中的記錄行會根據(jù)我們的索引列比如就先當(dāng)成主鍵吧去進(jìn)行從小到大的排序，比如頁38的主鍵排序是333到444，然后我們把這個頁38放到區(qū)里面，現(xiàn)在問題來了，區(qū)里面有多個頁，這些頁在物理上是連續(xù)的，那么下一個頁我們找誰？把誰放到區(qū)里面？需要找一個頁，它里面的主鍵排序要從445到556，這個頁就是物理上相鄰的頁39，那么我們一個區(qū)里面的前兩個頁就是頁38和頁39。注意聚簇索引中葉子節(jié)點中列出的所有頁物理上都是相鄰的；但是非葉子結(jié)點的層，頁與頁之間不是物理空間上相鄰，僅僅只是邏輯上相鄰。之前在做上面的數(shù)據(jù)庫優(yōu)化的時候遇到了一個問題，就是分區(qū)字段time必須要是主鍵或者聯(lián)合主鍵里面的字段，這是因為這樣的話能保證頁里面的分區(qū)字段是連續(xù)遞增的，比如說頁11里面全是時間為2月份的記錄，這樣我們才能把頁11放到month2分區(qū)里面，不然的話，假設(shè)分區(qū)字段不是聯(lián)合主鍵或者是主鍵，那么就會出現(xiàn)頁11里面的前幾條時間都是6月份，而后面時間就變成了1月份，再往后又變成了10月份，這樣我們這個頁11就不能假如到month2分區(qū)里面了，因為month2分區(qū)里面假如的頁要求里面的時間對應(yīng)的月份全都是2月份。因此只要根據(jù)主鍵或者聯(lián)合主鍵里面的字段分區(qū)的時候，我們的頁里面的數(shù)據(jù)才會根據(jù)分區(qū)字段遞增，因為頁里面的記錄是根據(jù)主鍵遞增的。這樣我們才能把頁假如到區(qū)里面，不然的話我們的頁是不配加入到區(qū)里面的。

段(Segment) 由一個或者多個區(qū)組成, 區(qū)在文件系統(tǒng)是一個連續(xù)分配的空間(在InnoDB中是連續(xù)的64個頁), 不過在段中不要求區(qū)與區(qū)是相鄰的. 段是數(shù)據(jù)庫中的分配單位, 不同類型的數(shù)據(jù)庫對象以不同的段形式存在, 當(dāng)我們創(chuàng)建數(shù)據(jù)表, 索引的時候, 就會相應(yīng)創(chuàng)建對應(yīng)的段, 比如創(chuàng)建一張表時會創(chuàng)建一個表段, 創(chuàng)建一個索引時會創(chuàng)建一個索引段。

表空間(Tablespace) 是一個邏輯容器, 表空間存儲的對象是段, 在一個表空間中可以有一個或者多個段, 但是一個段只能屬于一個表空間。數(shù)據(jù)庫由一個或者多個表空間組成, 表空間從管理上可以劃分為系統(tǒng)表空間, 用戶表空間, 撤銷表空間, 臨時表空間等。

頁的內(nèi)部結(jié)構(gòu)

頁如果按照類型劃分的話, 常見的有數(shù)據(jù)頁(保存B+樹結(jié)點), 系統(tǒng)頁, Unod頁和事物數(shù)據(jù)頁等, 數(shù)據(jù)頁是我們最常使用的頁。我們這里說的數(shù)據(jù)頁包括了B+樹葉子結(jié)點和非葉子結(jié)點, 但是其實也可以把非葉子結(jié)點分出去稱之為目錄頁。

數(shù)據(jù)頁的16KB大小的存儲空間被劃分為了7個部分, 分別是文件頭(File Header), 頁頭(Page Header), 最大最小記錄(Infimum+supremum), 用戶記錄(User Records), 空閑空間(Free Space), 頁目錄(Page Directory)和文件尾(File Tailer)。
頁結(jié)構(gòu)的示意圖如下所示:

這7個部分作用分別如下: 我們簡單的梳理如下表所示:

我們可以把這7個結(jié)構(gòu)分成3個部分:
第一部分: File Header(文件頭部)和File Trailer(文件尾部)
首先是文件通用部分, 也就是文件頭和文件尾

1. 文件頭:
作用 : 描述各種頁的通用信息(比如頁的編號, 其上一頁, 下一頁是誰等等)
文件頭的構(gòu)成如下圖:

我們說幾個比較重要的組成:
1. fil_page_offset(4個字節(jié)) :
每一個頁都有一個單獨的頁號, 就和你的身份證號碼一樣, InnoDB通過頁號可以唯一定位一個頁。

2. fil_page_type
這個代表當(dāng)前頁的類型

可以看到頁其實是不區(qū)分?jǐn)?shù)據(jù)頁和索引頁的, 我們說索引頁也好, 說數(shù)據(jù)頁也好都是代表的是索引 或者 數(shù)據(jù)。段是分為索引段和數(shù)據(jù)段的, 因為我們要區(qū)分索引和數(shù)據(jù)進(jìn)行分開存儲, 至于好處就是為了能多一點順序IO, 減少隨機(jī)IO。

3. fil_page_prev(4字節(jié))和fil_page_next(4字節(jié))
InnoDB都是以頁為單位來存放數(shù)據(jù)的, 如果數(shù)據(jù)分散到多個不連續(xù)的頁中存儲的話需要把這些頁關(guān)聯(lián)起來, fil_page_prev和fil_page_next就分別代表本頁的上一個和下一個頁的頁號. 這樣通過建立一個雙向鏈表把許許多多的頁就串聯(lián)起來了, 保證這些頁之間不需要是物理上連續(xù), 而是邏輯上連續(xù) (區(qū)上的頁的分配是連續(xù)的, 但是經(jīng)過很多操作后, 可能邏輯連續(xù)的頁物理位置就不連續(xù)了)。

fil_page_space_or_chksum(4字節(jié))
代表當(dāng)前頁面的校驗和(checksum)。文件頭部和文件尾部都有屬性fil_page_space_or_chksum。

什么是校驗和?
就是對于很長的字節(jié)串來說, 我們會通過某種算法來計算一個比較短的值來代表這個很長的字符串, 這個比較短的值就稱之為校驗和。
在比較兩個很長的字節(jié)串之前, 先比較這兩個長字節(jié)串的校驗和, 如果校驗和都不一樣, 則兩個長字節(jié)串肯定是不同的, 所以省去了直接比較兩個比較長的字節(jié)串的時間損耗。

校驗和的作用？
InnoDB存儲引擎以頁為單位把數(shù)據(jù)加載到內(nèi)存中處理, 如果該頁中的數(shù)據(jù)在內(nèi)存中被修改了, 那么在修改后的某個時間需要把數(shù)據(jù)同步到磁盤中. 但是在同步了一半的時候斷電了, 造成該頁傳輸?shù)牟煌暾?br> 為了檢測一個頁是否完整(也就是在同步的時候有沒有發(fā)生只同步一半的尷尬情況), 這時可以通過文件尾的校驗和與文件頭的校驗和做對比, 如果兩個值不相等則證明頁的傳輸有問題, 需要重新進(jìn)行傳輸, 否則認(rèn)為頁的傳輸已經(jīng)完成。
后面我們講到redo日志的時候就會講到刷盤, 以及刷盤策略, 我們開始的時候?qū)?shù)據(jù)加載到內(nèi)存中, 對內(nèi)存中數(shù)據(jù)操作之后要以頁為單位將數(shù)據(jù)寫回到磁盤中, 那么如何判斷我們磁盤中的文件是刷新完的, 如何確保刷新的過程是正確的, 我們就要用到檢驗和, 修改內(nèi)存中頁的數(shù)據(jù)之后我們就會同時改變校驗和, 那么如果刷盤的過程中刷盤一般停機(jī)了, 這個時候我們就可以判斷磁盤中的頁的文件頭和文件尾的校驗和是否相等, 如果不相等, 那不就直接說明是失敗的? 就節(jié)省了性能。

具體的？
每當(dāng)一個頁面在內(nèi)存中修改了, 在同步之前就要把它的校驗和算出來. 因為File Headeer在頁面的前面, 所以校驗和會被首先同步到磁盤, 當(dāng)完全寫完時, 校驗和也會被寫到頁的尾部, 如果完全同步成功, 則頁的首部和尾部的校驗和應(yīng)該是一致的. 如果寫一般斷電了, 那么在File Header中的校驗和就代表著已經(jīng)修改過的頁, 而在File Trailer中的校驗和代表著原先的頁, 二者不同則意味著同步中間出了錯. 這里, 校驗方式就是采用Hash算法進(jìn)行校驗。

5. fil_page_lsn(8字節(jié))
頁面被最后修改時對應(yīng)的日志序列位置(英文名是: Log Sequence Number)。日志序列位置也是為了校驗頁的完整性的, 如果首部和尾部LSN值校驗不成功的話, 就說明同步過程出現(xiàn)了問題。

文件尾(8字節(jié))
1. 前4個字節(jié)代表頁的校驗和
這個部分是和文件頭(File Header)中的校驗和相對應(yīng)的。
2.后4個字節(jié)代表頁面被最后修改時對應(yīng)的日志序列位置(LSN):
這個部分也是為了校驗頁的完整性的, 如果首部和尾部的LSN值校驗不成功的話, 就說明同步過程出現(xiàn)了問題。

第二部分: 記錄部分
第二個部分是記錄部分, 頁的主要作用是存儲記錄, 所以"最大和最小記錄"和"用戶記錄"部分占了頁結(jié)構(gòu)的主要空間。記錄部分分為: 1.空閑空間, 2.用戶記錄, 3.最小最大記錄。

1. Free Space(空閑空間)
我們自己存儲的記錄會按照指定的行格式存儲到User Records(用戶記錄)部分, 但是在一開始生成頁的時候, 其實并沒有User Records這個部分, 每當(dāng)我們插入一條記錄, 都會從Free Space部分, 也就是尚未使用的存儲空間申請一個記錄大小的空間劃分到User Records部分, 當(dāng)Free Space部分的空間全部被User Records部分代替掉之后, 也就意味著這個頁使用完了, 如果還有新的記錄插入的話, 就需要去申請新的頁了。

2. User Records(用戶記錄)
User Records中的這些記錄按照指定的行格式一條一條擺在User Records部分, 相互之間形成單鏈表。那么如何證明記錄之間是使用的單鏈表? —> 這里我們要先講解一下記錄的行格式的記錄頭信息。

3.Infimum+Supremum(最小最大記錄)
就是上闕界和下闕界。
最大記錄和最小記錄是一個固定的字符串信息, 所以并不是我們理解上的最大和最小記錄, 只是一個鏈表中值最小的記錄的前一個記錄(最小記錄), 一個是鏈表中值最大的記錄的后一個記錄(最大記錄)。
記錄可以比較大小嗎?
是的, 記錄可以比較大小, 對于一條完整的記錄來說, 比較記錄的大小就是比較主鍵的大小. 比方說我們插入的4行記錄的主鍵值分別是: 1, 2, 3, 4, 這也就意味著這4條記錄了是從小到達(dá)依次遞增
InnoDB規(guī)定了最小記錄與最大記錄這兩條記錄的構(gòu)造十分簡單, 都是由5字節(jié)大小的記錄頭信息和8字節(jié)大小的一個固定的部分組成的, 如圖所示:

這兩條記錄不是我們自己定義的記錄, 所以它們并不存放在頁的User Records部分, 它們被單獨放在了一個稱為Infimum+Supremum的部分, 如圖所示:

補(bǔ)充:
Infimum 和 Supremum
有人可能會說了，你在 User Records 中還不是通過遍歷來解決的，你就是簡單的把數(shù)據(jù)分了個組而已。如果我的數(shù)據(jù)根本不在當(dāng)前這個頁中，那我難道還是得把之前的頁中的每一條數(shù)據(jù)全部遍歷完？這效率也太低了。
當(dāng)然，MySQL 也考慮到了這個問題，所以實際上在頁中還存在一塊區(qū)域叫做 The Infimum and Supremum Records ，代表了當(dāng)前頁中最大和最小的記錄。
有了 Infimum Record 和 Supremum Record ，現(xiàn)在查詢不需要將某一頁的 User Records 全部遍歷完，只需要將這兩個記錄和待查詢的目標(biāo)記錄進(jìn)行比較。比如我要查詢的數(shù)據(jù) id = 101 ，那很明顯不在當(dāng)前頁。接下來就可以通過下一頁指針跳到下頁進(jìn)行檢索。

使用Page Directory
可能有人又會說了，你這 User Records 里不也全是單鏈表嗎？即使我知道我要找的數(shù)據(jù)在當(dāng)前頁，那最壞的情況下，不還是得挨個挨個的遍歷100次才能找到我要找的數(shù)據(jù)？你管這也叫效率高？

不得不說，這的確是個問題，不過是一個 MySQL 已經(jīng)考慮到的問題。不錯，挨個遍歷確實效率很低。為了解決這個問題，MySQL 又在頁中加入了另一個區(qū)域 Page Directory 。
顧名思義，Page Directory 是個目錄，里面有很多個槽位（Slots），每一個槽位都指向了一條 User Records 中的記錄。大家可以看到，每隔幾條數(shù)據(jù)，就會創(chuàng)建一個槽位。其實我圖中給出的數(shù)據(jù)是非常嚴(yán)格按照其設(shè)定來的，在一個完整的頁中，每隔6條數(shù)據(jù)就會有一個 Slot。

MySQL 會在新增數(shù)據(jù)的時候就將對應(yīng)的 Slot 創(chuàng)建好，有了 Page Directory ，就可以對一張頁的數(shù)據(jù)進(jìn)行粗略的二分查找。至于為什么是粗略，畢竟 Page Directory 中不是完整的數(shù)據(jù)，二分查找出來的結(jié)果只能是個大概的位置，找到了這個大概的位置之后，還需要回到 User Records 中繼續(xù)的進(jìn)行挨個遍歷匹配。

不過這樣的效率已經(jīng)比我們剛開始聊的原始版本高了很多了。

第三部分: 頁部分
1. 頁目錄(Page Directory):
為什么需要頁目錄?
在頁中, 記錄是以單向鏈表的形式進(jìn)行存儲的, 單向鏈表的特點就是插入, 刪除非常方便, 但是檢索效率不高, 最差的情況下需要遍歷鏈表上的所有結(jié)點才能完成檢索. 因此在頁結(jié)構(gòu)中專門設(shè)計了頁目錄這個模塊, 專門給記錄做一個目錄, 通過二分查找法的方式進(jìn)行檢索, 提升效率。頁目錄包含所有槽, 其實就是一個頁中所有的槽加載一起構(gòu)成頁目錄。

需求：根據(jù)主鍵值查找頁中的某條記錄, 如何實現(xiàn)快速查找吶?

select * from page_demo where c1 = 3;

方式1 : 順序查找
從Infimum記錄(最小記錄)開始, 沿著鏈表一直往后找, 總有一天會找到(或者最終也找不到就說明是沒有這條記錄), 在找的時候還能投機(jī)取巧, 因為鏈表中各個記錄的值是按照從小到達(dá)的順序排列的, 所以當(dāng)鏈表的某個結(jié)點代表的記錄的主鍵值大于你想要查找的主鍵值時, 你就可以停止查找了, 因為該結(jié)點以后的結(jié)點的值主鍵依次遞增。

如果一個頁中存儲了非常多的記錄, 那么查找性能很差。

方式2 : 使用頁目錄, 二分法查找

頁目錄是一個數(shù)組結(jié)構(gòu), 我們可以在頁目錄中使用二分查找的方式進(jìn)行搜索:

1. 將所有的記錄分成幾個組, 這些記錄包括最小記錄和最大記錄, 但是不包括標(biāo)記為已刪除的記錄
2. 第1組, 也就是最小記錄所在的分組( 第一組就只有一條記錄就是最小記錄自己 )。最后一組, 就是最大記錄所在的分組, 會有1-8條記錄;其余的組記錄數(shù)量在4-8條之間；這樣做的好處是, 除了第一組(最小記錄所在組)以外, 其余組的記錄數(shù)會盡量平分；
3. 在每個組中最后一條記錄的頭信息會存儲該組一共有多少條記錄, 作為n_owned字段值
4. 頁目錄用來存儲每組最后一條記錄的地址偏移量, 這些地址偏移量會按照先后順序存儲起來, 每組的地址偏移量也被稱之為槽(slot), 每個槽相當(dāng)于指針指向了不同組的最后一個記錄
   那么我們?nèi)绾瓮ㄟ^頁目錄, 通過槽來定位到二分位置? 由于槽指向的是一組中最大的值, 所以如果我們判斷到某個值比我們的上一個槽值大, 比下一個槽值小的時候, 那么我們就應(yīng)該到上一個槽的位置, 上一個槽指向的就是上一個頁目錄中最大的, next_record指針指向的就是下一個槽中的最小值了, 因為頁內(nèi)是單向指針, 所以我們必須要從前往后找。

頁目錄分組的個數(shù)如何確定?
InnoDB規(guī)定: 對于最小記錄所在的分組只能有一條記錄, 最大記錄所在的分組擁有的記錄了條數(shù)只能在1-8條之間, 剩下的分組中記錄的條數(shù)范圍只能在4-8條之間。
分組是按照下邊的步驟進(jìn)行的:

• 初始情況下一個數(shù)據(jù)頁里只會有最小記錄和最大記錄這兩條記錄, 它們屬于兩個分組。
• 之后每插入一條記錄, 都會從頁目錄中找到主鍵值比本記錄的主鍵值大并且差值最小的槽, 然后把該槽對應(yīng)的記錄的n_owned值加1, 表示本組內(nèi)又添加了一條記錄, 知道該組中的記錄數(shù)等于8個。
• 在一個組中的記錄數(shù)等于8個后再插入一條記錄時, 會將組中的記錄拆分成兩個組, 一個組中4條記錄, 另一個5條記錄, 這個過程會在頁目錄中新增一個槽位來記錄這個新增分組中最大的那條記錄的偏移量。

2. 頁面頭部(Page Header):
為了能得到一個數(shù)據(jù)頁中存儲的狀態(tài)信息, 比如本頁中已經(jīng)存儲了多少條記錄, 第一條記錄的地址值是什么, 頁目錄中存儲了多少個槽等等, 特意在頁中定義了一個叫做Page Header的部分, 這部分占用固定的56個字節(jié), 專門存儲各種狀態(tài)信息

關(guān)于記錄插入方向:
page_direction :
假如新插入的一條記錄的主鍵值比上一條記錄的主鍵值大, 我們說這條記錄的插入方向是右邊, 反之就是左邊, 用來表示最后一條記錄插入方向的狀態(tài)就是page_direction。

page_n_direction
假設(shè)連續(xù)幾次插入新記錄的方向都是一致的, InnnoDB會把沿著同一個方向插入記錄的條數(shù)記下來, 這個條數(shù)就用page_n_direction這個字段表示. 當(dāng)然, 如果最后一條記錄的插入方向改變了的話, 這個狀態(tài)的值會被清零重新統(tǒng)計。

記錄行格式的記錄頭:
先給出一個表:

給出該表中記錄的行格式示意圖:

由于表中是指明了主鍵的, 所以隱藏字段只有兩個 : 1.transaction_id(事物id)和2. roll_pointer(回滾指針), 如果沒有指明主鍵, 也沒有指明非空且唯一的字段, 那么就會有一個row_id隱藏字段作為聚簇索引列。

記錄頭組成如下圖:

預(yù)留位是沒有使用的空間, 所以我們直接去掉預(yù)留位, 得到簡化后的行格式示意圖:

然后我們插入4條記錄:

然后我們來講解記錄頭組成(上面圖中我們可以看到記錄頭一共是分為了6個部分: ):

1. delete_mask
這個屬性標(biāo)記著當(dāng)前記錄是否被刪除, 占用1個二進(jìn)制位：

• 值為0 : 代表記錄并沒有被刪除
• 值為1 : 代表記錄被刪除掉了

被刪除的記錄為什么還在頁中存儲吶?
你以為它刪除了, 可它還在真實的磁盤上. 這些被刪除的記錄之所以不立即從磁盤上移除, 是因為移除它們之后其他的記錄在磁盤上需要重新排列, 導(dǎo)致性能消耗. 所以只是打一個刪除標(biāo)記而已, 所有被刪除掉的記錄都會組成一個所謂的垃圾鏈表, 在這個鏈表中的記錄占用的空間稱之為可重用空間, 之后如果有新記錄插入到表中的話, 可能把這些被刪除的記錄占用的存儲空間覆蓋掉。

2. min_rec_mask
B+樹的每層非葉子結(jié)點中最小記錄都會添加該標(biāo)記, min_rec_mask值為1。
我們自己插入的四條記錄的min_rec_mask值都是0, 意味著他們都不是B+樹的非葉子結(jié)點中的最小記錄(我們添加的這四條記錄都是葉子結(jié)點)。

我們之前在講數(shù)據(jù)庫索引(B+樹索引)設(shè)計的時候就提到過, 數(shù)據(jù)記錄(葉子結(jié)點)和目錄項(索引)記錄(非葉子結(jié)點)在記錄頭上有兩個不同 : 1. record_type不同, 一個是數(shù)據(jù)記錄, 一個是索引記錄, 2. min_rec_mask不同, 非葉子結(jié)點記錄的min_rec_mask值可能為1。

3. record_type
這個屬性表示當(dāng)前記錄的類型, 一共有4種類型的記錄:

• 0 : 表示普通記錄。
• 1 : 表示B+樹非葉子結(jié)點記錄。
• 表示最小記錄。
• 表示最大記錄。

從圖中我們也可以看出來, 我們自己插入的記錄就是普通記錄, 它們的record_type值都是0, 而最小記錄和最大記錄的record_type值分別為2和3。

注意: 最小記錄和最大記錄是MySQL為我們自動生成的兩個記錄, 最小記錄和最大記錄由于是MySQL自動生成的, 所以我們常常將之稱之為: 虛擬記錄。

4. heap_no
這個屬性表示當(dāng)前記錄在本頁中的位置。從上面(插入的數(shù)據(jù)的行記錄格式圖)圖中可以看出, 我們插入的4條記錄在本頁中的位置分別是: 2,3,4,5。

怎么不見heap_no值為0和1的記錄吶?
MySQL會自動給每個葉里加了兩個記錄, 由于這兩個記錄并不是我們自己插入的, 所以有時候也稱之為偽記錄或者虛擬記錄. 這兩個偽記錄一個代表最小記錄, 一個代表最大記錄. 最小記錄和最大記錄了的位置最靠前, 所以最小記錄和最大記錄的heap_no值分別是0和1。

5. n_owned
頁目錄中每個組最后一條記錄的頭信息中會存儲該組一共多少條記錄, 作為n_owned字段。可以看到n_owned和頁目錄是密切相關(guān)的。

6. next_record
記錄頭信息里該屬性非常重要, 它表示從當(dāng)前記錄的真實數(shù)據(jù)到下一條記錄的真實數(shù)據(jù)的地址偏移量。

比如: 第一條記錄的next_record值為32, 意味著從第一條記錄的真實數(shù)據(jù)的地址處向后找32個字節(jié)便是下一條記錄的真實數(shù)據(jù)。

注意 : 下一條記錄指的并不是按照我們插入順序的下一條記錄, 而是按照主鍵值從小到大的順序的下一條記錄, 而本頁中主鍵值最大的用戶記錄的下一條記錄就是Supremum記錄(也就是最大記錄)。也即是說: 我們的最大記錄雖然位置是頁中的第二個位置, 第一個位置是最小記錄, 但是在邏輯上卻是頁中的最后一條記錄(也就是值最大的記錄的下一條記錄), 也即是物理地址靠前但是邏輯地址靠后。

刪除操作舉例:

從圖中可以看出來, 刪除第二條記錄前后主要發(fā)生了這些變化:

• 第2條記錄并沒有從存儲空間中移除, 而是把該條記錄的delete_mask值設(shè)置為1
• 第2條記錄的next_record的值變?yōu)榱?, 意味著該記錄沒有下一條記錄了
• 第1條記錄的next_record指向了第3條記錄
• 最大記錄的n_owned值從5變成了4(原本刪除之前頁目錄中有5條記錄)

所以, 不論我們怎么對頁中的記錄做增刪改操作, InnoDB始終會維護(hù)一條記錄的單鏈表, 鏈表中的各個節(jié)點是按照主鍵值由小到大的順序連接起來的.

添加操作:

直接復(fù)用了原來被刪除記錄的存儲空間。

說明：
當(dāng)數(shù)據(jù)頁中存在多條被刪除掉的記錄時, 這些記錄了的next_record屬性將會把這些被刪除掉的記錄組成一個垃圾鏈表, 以備之后重用這部分存儲空間。

從數(shù)據(jù)頁的角度看B+樹如何查詢

一顆B+樹按照結(jié)點類型可以分為兩部分:

1. 葉子結(jié)點, B+樹最底層的結(jié)點, 結(jié)點的高度為0, 存儲行記錄
2. 非葉子結(jié)點, 結(jié)點的高度大于0, 存儲索引鍵和頁面指針, 并不存儲行記錄本身
   • 注意: 我們說非葉子結(jié)點存儲的是索引鍵和頁面指針, 這里的頁面指針并不是fil_page_prev和fil_page_next, 文件頭中的fil_page_prev和fil_page_next都是記錄的同一層的頁之間的上一頁和下一頁, 但是非葉子結(jié)點存儲的是下一層頁面的地址
   • 葉子結(jié)點中存儲的鍵是索引值, 值是行數(shù)據(jù)
   • 非葉子結(jié)點中存儲的鍵是索引值, 值是指向下一層的頁面指針(如果了解B+樹就應(yīng)該能大致想的明白)

不過是葉子結(jié)點頁還是非葉子結(jié)點頁(其實頁只有數(shù)據(jù)頁, 但是這里我們?yōu)榱朔奖憷斫饩驼f成兩種), 頁的結(jié)構(gòu)都是一個雙向鏈表, 很多時候我們都以為只有葉子結(jié)點才是雙向鏈表結(jié)構(gòu), 其實不是的, 同一層非葉子結(jié)點之間也是雙向鏈表結(jié)構(gòu)。

當(dāng)我們從頁結(jié)構(gòu)來理解B+樹結(jié)構(gòu)的時候, 可以幫我們理解一些通過索引進(jìn)行檢索的原理:
1. B+樹是如何進(jìn)行記錄檢索的
如果通過B+樹的索引查詢行記錄, 首先是從B+樹的根開始, 逐層檢索, 直到找到葉子結(jié)點, 也就是找到對應(yīng)的數(shù)據(jù)頁位置, 將數(shù)據(jù)頁加載到內(nèi)存中, 頁目錄中的槽(slot)采用二分查找的方式先找到一個粗略的記錄分組, 然后再在分組中通過鏈表遍歷的方式查找記錄。

2. 普通索引和唯一索引在查詢效率上有什么不同?
我們創(chuàng)建索引的時候可以是普通索引, 也可以是唯一索引, 那么這兩個索引在查詢效率上有什么不同?

唯一索引就是普通索引上增加了約束性, 也就是關(guān)鍵字唯一, 找到了關(guān)鍵字就停止檢索, 因為關(guān)鍵字不重復(fù). 而普通索引, 可能會存在用戶記錄中的關(guān)鍵字相同的情況, 根據(jù)頁結(jié)構(gòu)的原理, 當(dāng)我們讀取一條記錄的時候, 不是單獨將這條記錄從磁盤中讀取出去, 而是將這個記錄所在頁加載到內(nèi)存中進(jìn)行讀取, InnoDB存儲引擎的頁大小為16KB, 在一個頁中可能存儲著上千條記錄, 因此在普通索引的字段上進(jìn)行查找也就是在內(nèi)存中多幾次判斷(判斷下一條記錄是不是值也滿足)操作, 對于cpu來說, 這些操作鎖耗費的時間是可以忽略不計的. 所以對一個索引字段進(jìn)行檢索, 采用普通索引還是唯一索引在檢索效率上基本沒有差別.

區(qū), 段, 碎片區(qū)

為什么要有區(qū)?

B+樹的每一層的頁都會形成一個雙向鏈表, 如果是以頁為單位來分配存儲空間的話, 雙向鏈表相鄰的兩個頁之間的物理位置可能會離得非常遠(yuǎn). 我們介紹B+樹索引的使用場景的時候特別提到范圍查詢只需要定位到最左邊的記錄和最右邊的記錄, 然后沿著雙向鏈表一直掃描就可以了, 而如果鏈表中相鄰的兩個頁物理位置離得非常遠(yuǎn), 這就時所謂的隨機(jī)I/O. 再一次強(qiáng)調(diào), 磁盤的速度和內(nèi)存速度差了好幾個數(shù)量級, 隨機(jī)I/O是非常慢的, 所以我們應(yīng)該盡量讓鏈表中相鄰的頁的物理位置也相鄰, 這樣進(jìn)行范圍查詢的時候才可以使用所謂的順序I/O。

個人對于隨機(jī)IO和順序IO的理解：假如現(xiàn)在有一個需求，有一個log_script日志表，表里面有三個字段主鍵id，員工名字name，插入時間time，假如現(xiàn)在沒有分區(qū)，那么在一個頁中會根據(jù)主鍵id的大小把記錄行從小到大排序，但是time不會排序，所以就會出現(xiàn)一種情況，葉子節(jié)點數(shù)據(jù)頁中，每個頁中都可能出現(xiàn)各種插入時間的行記錄，并沒有順序，那么假如我現(xiàn)在想要查找插入時間大于2月小于3月的記錄，我就要把所有的葉子結(jié)點數(shù)據(jù)頁都查詢一遍，這就是所謂的隨機(jī)IO，就是查詢的時候會進(jìn)行很多個IO磁盤交互，因為要訪問所有的數(shù)據(jù)頁；但是如果分區(qū)了，就是順序IO了，比如我現(xiàn)在根據(jù)月份進(jìn)行了分區(qū)，那么每個頁里面都是會按照月份去排序的，這樣時間大于2月和小于3月的數(shù)據(jù)就會在某幾個順序的葉子節(jié)點數(shù)據(jù)頁中，我們查詢的時候就會只訪問這幾個頁，IO磁盤交互就會少很多，性能會大大的提高，這就是順序IO；

引入?yún)^(qū)的概念, 一個區(qū)就是在物理位置上連續(xù)的64個頁. 因為InnoDB中的頁的大小默認(rèn)是16KB, 所以一個區(qū)的大小是64*16KB = 1MB. 在表中數(shù)據(jù)量大的時候, 為某個索引分配空間的時候就不再按照頁為單位分配了, 而是按照區(qū)為單位分配, 甚至在表中的數(shù)據(jù)特別多的時候, 可以一次性分配多個連續(xù)的區(qū), 雖然可能造成一點點空間的浪費(數(shù)據(jù)不足以填充滿整個區(qū)), 但是從性能角度看, 可以消除很多隨機(jī)I/O, 功大于過!

為什么要有段?
對于范圍查詢, 其實時候?qū)+樹葉子結(jié)點中的記錄進(jìn)行順序掃描, 而如果不區(qū)分葉子節(jié)點和非葉子節(jié)點, 統(tǒng)統(tǒng)把節(jié)點代表的頁面放到申請到的區(qū)中的話, 進(jìn)行范圍掃描的效果就大打折扣了. 所以InnoDB對B+樹的葉子結(jié)點和非葉子結(jié)點進(jìn)行了區(qū)別對待, 也就是說葉子結(jié)點有自己的獨有的區(qū), 非葉子結(jié)點也有自己獨有的區(qū). 存放葉子結(jié)點的區(qū)的集合就是一個段(segment), 存放非葉子結(jié)點的區(qū)的集合也算是一個段. 也就是說一個索引會生成2個段, 一個葉子結(jié)點段, 一個非葉子結(jié)點段, 我們可以將葉子結(jié)點段稱之為數(shù)據(jù)段, 可以將非葉子階段稱之為索引段

除了索引的葉子結(jié)點段和非葉子結(jié)點段之外, InnoDB中還有為存儲一些特殊數(shù)據(jù)而定義的段, 比如回滾段. 所以, 常見的段有數(shù)據(jù)段, 索引段, 回滾段. 數(shù)據(jù)段即為B+樹的葉子結(jié)點, 索引段即為B+樹的非葉子結(jié)點

在InnoDB存儲引擎中, 對端的管理都是由執(zhí)行引擎自身所完成的, DBA不能也沒有必要對其進(jìn)行控制. 這從一定程度上簡化了DBA對于段的管理

段其實不對應(yīng)表空間中某一個連續(xù)的物理區(qū)域, 而是一個邏輯上的概念, 由若干個零散的頁面以及一些完成的區(qū)組成 —> 這里設(shè)計到的零散的頁面其實就需要提一個新的概念: 碎片區(qū)。

為什么要有碎片區(qū)
默認(rèn)情況下, 一個使用InnoDB存儲引擎的表只有一個聚簇索引, 一個索引會生成兩個段, 而段是以區(qū)為單位申請存儲空間的, 一個區(qū)默認(rèn)占用1M存儲空間, 所以默認(rèn)情況下一個只存了幾條記錄的小表也需要2M的存儲空間么? 以后每次添加一個索引都要多申請2M的存儲空間么? 這對于存儲記錄比較少的表簡直是天大的浪費. 這個問題的癥結(jié)在于到現(xiàn)在為止我們介紹的區(qū)都是非常純粹的, 也就是一個區(qū)被整個分配給某個段, 或者說區(qū)中的所有頁面都是為了存儲同一個段的數(shù)據(jù)而存在的, 即使段的數(shù)據(jù)填不滿區(qū)中所有的頁面, 那余下的頁面也不能挪作他用。一個索引因為有葉子結(jié)點還有非葉子結(jié)點, 所以一個索引就會創(chuàng)建一個數(shù)據(jù)段和一個索引段, 這個時候很多人會說, 不是只有聚簇索引才是葉子結(jié)點存儲的真實數(shù)據(jù)嗎? 普通索引不應(yīng)該只有一個索引段? 我的理解是即使是輔助索引(二級索引), 葉子結(jié)點也是存儲的數(shù)據(jù), 只不過不是行記錄而已, 所以即使是一個普通索引也是要分配一個索引段和一個數(shù)據(jù)段, 也就是2M的空間, 但是這樣太浪費了。

為了考慮以完整的區(qū)為單位分配給某個段對于數(shù)據(jù)量較小的表太浪費存儲空間的這種情況, InnoDB提出了一個碎片(fragment)區(qū)的概念. 在一個碎片區(qū)中, 并不是所有的頁都是為了存儲同一個段的數(shù)據(jù)而存在的, 而是碎片區(qū)中的頁可以用于不同的目的, 比如有些頁用于段A, 有些頁用于段B, 有些頁甚至哪個段都不屬于. 碎片區(qū)直屬于表空間, 并不屬于任何一個段。

所以以后為某個段分配存儲空間的策略是這樣的:

• 在剛開始向表中插入數(shù)據(jù)的時候, 段是從某個碎片區(qū)以單個頁面為單位來分配存儲空間的。
• 當(dāng)某個段已經(jīng)占用了32個碎片區(qū)頁面之后, 就會申請以完整的區(qū)為單位來分配存儲空間。就是某個段已經(jīng)是在32個碎片區(qū)中分配了頁面了, 這個時候就會以完整的區(qū)為單位來分配存儲空間。

所以現(xiàn)在段不能僅僅定義為是某些區(qū)的集合, 更精確的說應(yīng)該是某些零散的頁面以及一些完整的區(qū)的集合。

表空間和段都是邏輯概念, 區(qū)和頁和行是物理結(jié)構(gòu), 段是以區(qū)和零散的頁面為分配單位的。所以說數(shù)據(jù)庫最小的分配單位是邏輯上的段, 但是邏輯上的段實際分配的單位是零散的頁面(碎片區(qū)中), 或者是區(qū), 所以最小分配單位是碎片區(qū)中零散的頁面。

區(qū)的分類:
區(qū)大體上可以分為四種類型:

• 空閑的區(qū)(free) : 現(xiàn)在還沒有用到這個區(qū)中的任何頁面
• 有剩余空間的碎片區(qū)(free_frag) : 表示碎片區(qū)中還有可用的頁面
• 沒有剩余空間的碎片區(qū)(full_frag) : 表示碎片區(qū)中所有頁面都被使用, 沒有空閑頁面
• 附屬于某個段的區(qū)(fseg) : 每個索引都可以分為葉子結(jié)點段和非葉子結(jié)點段

處于free, free_frag以及full_frag這三種狀態(tài)的區(qū)都是獨立的, 直屬于表空間. 而處于FSEG狀態(tài)的區(qū)是附屬于某個段的。

表空間
MySQL5.5- 5.7中, 我們到數(shù)據(jù)目錄中看, 會發(fā)現(xiàn)一個新建的表的**.ibd文件只占用了96K**, 才6個頁面的大小,MySQL8.0中我們到數(shù)據(jù)目錄中看, 會發(fā)現(xiàn)一個新建的表的ibd文件占用112K, 也就是7個頁面大小, 這是因為一開始表空間占用的空間很小, 因為表里面都沒有數(shù)據(jù). 不過別忘了這些ibd文件是自擴(kuò)展的, 隨著表中數(shù)據(jù)的增多, 表空間對應(yīng)的文件也逐漸增大。

MySQL5.5之前默認(rèn)的執(zhí)行引擎是MyISAM, MySQL8.0之后把frm文件(表結(jié)構(gòu)文件)和ibd文件(表數(shù)據(jù)文件, 包括記錄(數(shù)據(jù))和日志), 還有db.opt文件(數(shù)據(jù)庫字符集, 比較規(guī)則等)合并到了一起。

查看InnoDB的表空間類型:

show variables like 'innodb_file_per_table';

你能看到innodb_file_per_table=on, 這就意味著每張表都會單獨保存為一個ibd文件。

系統(tǒng)表空間
系統(tǒng)表空間的結(jié)構(gòu)和獨立表空間基本類似, 只不過由于整個MySQL進(jìn)程只有一個系統(tǒng)表空間, 在系統(tǒng)表空間中會額外記錄一些有關(guān)整個系統(tǒng)信息的頁面, 這部分是獨立表空間中沒有的。

InnoDB數(shù)據(jù)字典(其實就是系統(tǒng)表):
每當(dāng)我們向一個表中插入一條記錄的時候, MySQL校驗過程如下:
先要檢驗以下插入語句對應(yīng)的表存不存在, 插入的列和表中的列是否符合, 如果語法沒有問題的話, 還需要知道該表的聚簇索引和所有二級索引對應(yīng)的根頁面是在哪個表空間的哪個頁面( 不知道根頁面怎么找? ), 然后把記錄插入對應(yīng)索引的B+樹中. 所以說, MySQL中除了保存著我們插入的用戶數(shù)據(jù)之外, 還需要保存許多額外的信息, 比方說:

• 某個表屬于哪個表空間, 表里面有多少個列
• 表對應(yīng)的每個列的類型是什么
• 表中有多少索引, 每個索引對應(yīng)哪幾個字段, 該索引對應(yīng)的根頁面在哪個表空間的哪個頁面
• 表有哪些外鍵, 外鍵對應(yīng)哪個表的哪些列
• 某個表空間對應(yīng)文件系統(tǒng)上的文件路徑是什么
• …

上述這些數(shù)據(jù)并不是我們使用INSERT語句插入的用戶數(shù)據(jù), 實際上是為了更好的管理我們這些用戶數(shù)據(jù)而不得已引入的一些額外記錄, 這些數(shù)據(jù)也稱之為元數(shù)據(jù). InnoDB存儲引擎特意定義了一些列的內(nèi)部系統(tǒng)表(Internal system table)來記錄這些元數(shù)據(jù)

這些系統(tǒng)表也被稱之為數(shù)據(jù)字典, 它們都是以B+樹的形式保存在系統(tǒng)表空間的某些頁面中, 其中sys_tables, sys_cloumns, sys_indexes, sys_fields這四個表尤其重要, 稱之為基本系統(tǒng)表(basic system tables),文章來源地址http://www.zghlxwxcb.cn/news/detail-722576.html

到了這里，關(guān)于Mysql第二篇---InnoDB數(shù)據(jù)存儲結(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！