title: InnoDB存儲結(jié)構(gòu)與索引
date: 2020-01-14 20:39:13
categories: 數(shù)據(jù)庫
tags:
- mysql
- 索引
- B+樹
description: InnoDB是一個(gè)將表中的數(shù)據(jù)存儲到磁盤上的存儲引擎
InnoDB將數(shù)據(jù)劃分為若干個(gè)頁梧奢，以頁作為磁盤和內(nèi)存之間交互的基本單位，InnoDB中頁的大小一般為 16 KB符欠。也就是在一般情況下希柿，一次最少從磁盤中讀取16KB的內(nèi)容到內(nèi)存中养筒，一次最少把內(nèi)存中的16KB內(nèi)容刷新到磁盤中挤悉。
行格式
InnoDB存儲引擎到現(xiàn)在為止設(shè)計(jì)了4種不同類型的行格式装悲，分別是Compact尚氛、Redundant阅嘶、Dynamic和Compressed行格式抡蛙。
- 指定行格式
CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名稱
ALTER TABLE 表名 ROW_FORMAT=行格式名稱
Compact行格式
-----------------------------------------------------------------------------
| 變長字段長度列表 | NULL值列表 | 記錄頭信息 | 列1的值 | 列2的值 |.....| 列n的值 |
-----------------------------------------------------------------------------
- 變長字段長度列表： 對于比如varchar類型可變長度的字段粗截，存儲的時(shí)候是不固定的慈格，因此需要根據(jù)實(shí)際的值來計(jì)算出實(shí)際字段長度遥金，保存到該列表
頁數(shù)據(jù)結(jié)構(gòu)
使用記錄和槽的方式存儲數(shù)據(jù)稿械，
| 名稱 | 解釋 | 占用空間大小 | 描述 |
|---|---|---|---|
| File Header | 文件頭部 | 38字節(jié) | 頁的通用信息选泻，比如上一個(gè)頁信息梯捕、下一個(gè)頁 |
| Page Header | 頁頭部 | 56字節(jié) | 數(shù)據(jù)頁的專有信息傀顾，比如槽的數(shù)量短曾，記錄的數(shù)量 |
| Infimum+Superemum | 最小記錄和最大記錄 | 26字節(jié) | 兩個(gè)特殊的固定的記錄 |
| User Records | 用戶記錄 | 不定 | 實(shí)際存儲的行記錄 |
| Free Space | 尚未使用的空間 | 不定 | 尚未使用的 |
| Page Directory | 頁目錄 | 不定 | 頁中記錄的相對記錄嫉拐，也就是槽記錄的頁中每組最后一條記錄記錄的位置 |
| File Trailer | 文件尾部 | 8字節(jié) | 校驗(yàn)頁的完整性 |
要點(diǎn)：
- 每個(gè)記錄的頭信息都有一個(gè)next_record的信息婉徘，從而形成單鏈表
- InnoDB會把頁記錄劃分為若干個(gè)組，每個(gè)組的最后一個(gè)記錄的地址偏移量為一個(gè)槽咐汞，存放在Page Directory中盖呼，所以查找非常快
- 通過二分法確定該記錄所在的槽
- 通過記錄的next_record屬性遍歷該槽所在的組的各個(gè)記錄(每個(gè)組只有4-5條記錄)
- 每個(gè)數(shù)據(jù)頁的File Header部分都有上一個(gè)和下一個(gè)頁的編號化撕，形成了一個(gè)雙鏈表
- 為保證從內(nèi)存中同步到磁盤的頁的完整性塌计，在頁的首部和尾部都會存儲數(shù)據(jù)的校驗(yàn)，和最后修改時(shí)對應(yīng)的LSN值
B+樹索引
在引入索引之前侯谁，如果通過主鍵查找，則可以通過二分法快速定位到相應(yīng)的的槽章钾，再依次遍歷單鏈表即可找到記錄墙贱，但如果是其他字段則沒有槽，需要遍歷數(shù)據(jù)頁的所有記錄贱傀，非常耗時(shí)
不論是根據(jù)主鍵列或者其他列的值進(jìn)行查找惨撇，由于我們并不能快速的定位到記錄所在的頁
問題一： 快速定位所在頁
保證，下一個(gè)頁的主鍵值大于上一個(gè)頁中用戶所有的主鍵值，所以在增刪改查的時(shí)候會有一些記錄移動的操作，這個(gè)過程叫做頁分裂
-
由于頁并不是連續(xù)的碰煌，所以需要建立一個(gè)頁目錄俄认，頁中最小主鍵值與頁號對應(yīng)。（這個(gè)目錄就是叫做索引）
- 由于在數(shù)據(jù)量大的時(shí)候無法保證頁目錄連續(xù)，也就是看做無法用數(shù)組存儲，所以采用存儲數(shù)據(jù)的方式存儲索引，這就是目錄項(xiàng)記錄頁，只不過record_type屬性不一樣妓湘，這里是1唬党，而普通記錄的頁中是0
- 如果數(shù)據(jù)更大屯烦，那么目錄項(xiàng)記錄頁就可以再進(jìn)行壓縮，變成更高曾記得目錄項(xiàng)記錄頁，也就有了如下的結(jié)構(gòu)：
這就是B+樹，以前一直不知道為什么只有葉子節(jié)點(diǎn)才存儲數(shù)據(jù)，現(xiàn)在就非常清晰了纺涤，他們的record_type是不一樣的拧咳！
聚簇索引
我們上邊介紹的B+樹本身就是一個(gè)目錄谭网，或者說本身就是一個(gè)索引。它有兩個(gè)特點(diǎn)：
-
使用記錄主鍵值的大小進(jìn)行記錄和頁的排序殖妇，這包括三個(gè)方面的含義：
頁內(nèi)的記錄是按照主鍵的大小順序排成一個(gè)單向鏈表。
各個(gè)存放用戶記錄的頁也是根據(jù)頁中用戶記錄的主鍵大小順序排成一個(gè)雙向鏈表。
存放目錄項(xiàng)記錄的頁分為不同的層次，在同一層次中的頁也是根據(jù)頁中目錄項(xiàng)記錄的主鍵大小順序排成一個(gè)雙向鏈表治笨。
B+樹的葉子節(jié)點(diǎn)存儲的是完整的用戶記錄探膊。
這種聚簇索引并不需要我們在MySQL語句中顯式的使用INDEX語句去創(chuàng)建（后邊會介紹索引相關(guān)的語句）绳瘟，InnoDB存儲引擎會自動的為我們創(chuàng)建聚簇索引
二級索引
上邊介紹的聚簇索引只能在搜索條件是主鍵值時(shí)才能發(fā)揮作用，因?yàn)锽+樹中的數(shù)據(jù)都是按照主鍵進(jìn)行排序的嘲玫。那如果我們想以別的列作為搜索條件該咋辦呢穷蛹？難道只能從頭到尾沿著鏈表依次遍歷記錄么？
不，我們可以多建幾棵B+樹出刷，不同的B+樹中的數(shù)據(jù)采用不同的排序規(guī)則改抡。比方說我們用c2列的大小作為數(shù)據(jù)頁、頁中記錄的排序規(guī)則荆忍，再建一棵B+樹，效果如下圖所示：
[圖片上傳失敗...(image-e59db8-1614334697826)]
注意與主鍵的聚簇索引有3點(diǎn)不同：
- 頁內(nèi)記錄都是按照c2來排列
- B+樹的葉子節(jié)點(diǎn)存儲的不是完整的用戶記錄钟鸵，而只是c2+主鍵這兩個(gè)列的值
- 目錄項(xiàng)記錄中不再是主鍵+頁號钉稍，而是c2+頁號
所以查找過程也與主鍵查找方式不同，我們是先通過索引建立的B+樹找到主鍵值棺耍，再通過主鍵找到對應(yīng)的完整記錄贡未，這個(gè)過程稱為回表，也就是根據(jù)c2列需要用到2棵B+樹
聯(lián)合索引
我們也可以同時(shí)以多個(gè)列的大小作為排序規(guī)則蒙袍，也就是同時(shí)為多個(gè)列建立索引俊卤，比方說我們想讓B+樹按照c2和c3列的大小進(jìn)行排序，這個(gè)包含兩層含義：
- 先把各個(gè)記錄和頁按照c2列進(jìn)行排序害幅。
- 在記錄的c2列相同的情況下消恍，采用c3列進(jìn)行排序
不同之處與二級索引類似，注意以现，之前我們常常提到的最左匹配就是這個(gè)原理狠怨，先比較c2，再比較c3邑遏，如果沒有c2佣赖，那么索引失效
注意構(gòu)建B+樹過程，根節(jié)點(diǎn)一直不變
