作者：鄭啟龍
摘要：
對于MYSQL的INNODB存盤引擎的索引，大家是不陌生的，都能想到是 B+樹結構，可以加速SQL查詢，但對于B+樹索引，它到底“長”得什么樣子，它具體如何由一個個位元組構成的，這些的基礎知識鮮有人深究，本篇文章從MYSQL行記錄開始說起，層層遞進，包括資料頁，B+樹聚簇索引，B+樹二級索引，最后在文章末尾給出MYSQL索引的建議，文章涉及較多基礎知識，內容較為枯燥，因此采用較多的圖片補充說明，希望能對讀者有幫助，
A. 一條記錄存盤格式：COMPACT行記錄結構
mysql是關系型資料庫，每一行記錄都是表結構定義的關系的 顯示表達，在腦中很直觀地想到，記錄存盤時也可能按行存盤，
的確，mysql是這么存盤一條行記錄的，但會添加一些額外資訊，來補充行記錄資訊，
有一個概念可能大家不熟悉，是【變長欄位】，mysql資料庫型別中的 VARCHAR(M), VARBINARY(M), 各種TEXT，BLOB型別，這些型別的資料長度是可變的，稱 資料型別為可變長型別的列 為 變長欄位，
另外，mysql會默認為行記錄添加一些列（隱藏列），上圖補充這些隱藏列之后，完整行記錄的結構如：
DB_ROW_ID: 唯一標識一條記錄，在表中未設定主鍵 或 未有不允許為NULL的UNIQUE鍵時，則MYSQL新增該隱藏列作為主鍵， DB_TRX_ID: 事務ID， DB_ROLL_PTR: 回滾指標，
下面再詳細的鋪開 ，關于記錄的額外資訊 的具體內容，
通過真實的資料庫表的行資料，來強化下上面的概念， 首先新增一個表，并在表中insert兩條記錄，
create table record_format_demo(
c1 varchar(10),
c2 varchar(10) not null,
c3 char(10),
c4 varchar(10)
) charset=ascii row_format=compact
insert into record_format_demo(c1, c2, c3, c4) values
("aaaa", "bbb", "cc", "d"),
("eeee", "fff", NULL, NULL);
做一個簡單的查詢，驗證資料正常寫入，
分析這兩行資料的存盤記錄，
第一行記錄：
第二行記錄：
應該會注意到，變長欄位長度串列 與 NULL值串列都是逆序存放的， 原因是：這樣可以使得記錄中位置靠前的欄位 和 它們對應的欄位長度資訊在記憶體中的距離更近，可能會提高 高速快取的命中率，
B. 盛放記錄的盒子：資料頁
為了更清楚的理解 資料頁結構 以及 下文中的索引，更換一個帶主鍵的表，
CREATE TABLE page_demo(
c1 INT,
c2 INT,
c3 VARCHAR(10000),
PRIMARY KEY (c1)
) CHARSET=ascii ROW_FORMAT=Compact;
INSERT INTO page_demo VALUES
(1, 100, 'aaaa'),
(2, 200, 'bbbb'),
(3, 300, 'cccc'),
(4, 400, 'dddd');
做一個簡單的查詢，驗證資料正常寫入，
根據行記錄結構中的next_recrod屬性的含義，多條行記錄是以單向鏈表的形式存盤，mysql為了后續更好的查詢，單向鏈表上的記錄是按照主鍵順序排列的， 上述這四條記錄，可以顯示的畫成：
假如洗掉其中c1=2這條資料，則單向鏈表變更如下， 其中變化點為 c1=2 這條資料中，deleted_flag變更成0， next_record=0，但并沒有從磁盤上直接清除掉，head_no也未清除，第一條記錄的next_record 指向了第三條記錄，
當我們查詢資料時，如果資料以行記錄的形式一條一條從磁盤加載到記憶體中，那么因為IO過多的原因，整體性能肯定較為低效， 因此mysql規定，磁盤與記憶體交換資料的基本單位是一個頁大小，這個頁大小 默認是16K， 根據頁中存盤的資料型別不同，頁也分成許多型別，對于存盤行記錄的頁，稱為索引頁（Index Page），也稱為資料頁，
那么接下來我們看看，資料頁的結構如何，一條條行記錄如何存放在資料頁中，先上個圖，
從上圖中，我們可以猜到，資料頁總共分成7個模塊，目前咱們只關心 User Records 部分，它存盤的就是用戶真實的行記錄， 但是一個資料頁的空間總共是16K，不會自動增大空間，隨著User Records 模塊中的行記錄越來越多，那么肯定有其他模塊的空間就越來越小， 這個模塊是 Free Space，是頁中尚未使用的空間，更新一下上面這個圖，補充 Free Space的內容，隨著User Records中行記錄的增加，Free Space空間則越來越小，
在一個資料頁中，除了真實的行記錄之外，還有兩條固定的偽記錄， 其中一條記錄稱為 infimum 【[?n?fa?m?m] ，下確界】行記錄，規定是資料頁中記錄的最小值， infimum記錄特別簡單，僅包含了 記錄頭資訊(5位元組) + 真實記錄資料(8位元組)，其中【69 6E 66 69 6D 75 6D 00】16進制轉換成對應的單詞，就是【infimum】，
另外一條記錄稱為 supremum【 [s?'prim?m] ，上確界】行記錄，規定是資料頁中記錄的最大值， supremum記錄同樣特別簡單，僅包含了 記錄頭資訊(5位元組) + 真實記錄資料(8位元組)，其中【73 75 70 72 65 6D 75 6D】16進制轉換成對應的單詞，就是【supremum】，
再更新一版資料庫頁結構， 補充上infimum 與 supremum，
既然規定了頁面中的最小記錄 與 最大記錄，理所應當，上文中串聯各個行記錄的單向鏈表，則應該有一個固定的頭部 與 固定的尾部， 更新一下單鏈表的圖，注意下infimum 與 supremum中的幾個關鍵值，
infimum: n_owned=1，表示是某一個分組的最后一條記錄，當前分組共1條記錄；record_type=2； next_record=第一條真實行記錄的真實值的相對位置， supremum: n_owned=5，表示是某個分組的最后一條記錄，當前分組共5條記錄；record_type=3； next_record=0，表示記錄是本資料頁中最后一條記錄，
OK，到現在資料頁中完整的單鏈表已經形成了， 思考一個問題，如何根據主鍵值，在資料頁中的單鏈表如何查找到相應的資料， 最直接的做法是：從 infimum記錄開始，沿著單鏈表的順序不斷的向后查找，直到supremum結束，在這期間，找到滿足條件的記錄就回傳，找不到則不回傳，
一個資料頁默認大小是16K，用于存盤真實行記錄的空間超過 98%以上，也就是說，一個資料頁中在行記錄填充滿的情況下，行記錄的數量是較多的（當然與行記錄大小有關）， 如果每次查詢都從單鏈表的infimum記錄 一直到 supremum記錄，肯定是無法接受的，很有必要對此現狀進行優化， 由此，引出了資料頁中的另一個模塊，Page Directory，頁目錄，
首先回傳看下上面完整單鏈表中，infimum記錄 與 supremum記錄中的兩個值，n_owned，這個值分別為 n_owned=1 與 n_owned=5，
參考下n_owned的定義，它是：【頁面分組之后，每個組最后一條行記錄中該值等于本組內的記錄數量，本組內其他記錄該值都等于0，】 對于上面的單鏈表，其它行記錄的owned值 都為零，也就是說，infimum單條記錄作為一個組，剩余的四條行記錄+supremum記錄作為一個組， mysql規定：
?對于infimum記錄所在的分組只能有1條記錄，也就是它本身，
?對于supremum記錄所在的分組的記錄數在1~8條之間，
?其它的分組記錄的條數范圍，在4~8條之間，
將每個組中 最后一條記錄在頁面中的地址偏移量（該記錄的真實資料與資料頁中第0個位元組之間的距離）單獨提取出來，以倒序存盤到資料頁中的固定模塊中， 這個模塊，就稱為：Page Directory，Page Directory中存盤的地址偏移量，也稱為Slot 【[sl?t]， 槽】，每個Slot兩位元組，【可以想想為啥是兩位元組？】
再次更新下資料頁結構圖，
目前的只有四條記錄，兩個分組，數量太少了，我們繼續往表中繼續增加一些記錄，
INSERT INTO page_demo VALUES
(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');
INSERT INTO page_demo VALUES
(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');
在不斷的插入新行記錄時，因此不同型別分組數量的約束，所以分組也會增加，這個程序如下：
?在初始情況下，一個資料頁中只會有 infimum 與 supremum 這兩條記錄，它們分別屬于兩個組，此時Page Directory 也只會有兩個slot，分別代表infimum的地址偏移量 與 supremum的地址偏移量，
?之后每新增一條行記錄，都會從Page Directory中找到對應的記錄的主鍵值 比 待新增記錄的主鍵值大 并且差值最小的slot【slot是一個組內最大的那條記錄在頁面中的地址偏移量，通過slot可以快速找到對應記錄的主鍵值】， 然后把該slot對應的記錄的 n_owned值加1，表示本組內新增了一條記錄，直到該組中的記錄數等于8個，
?當一個組中的記錄數等于8后，再插入一條記錄，會將組中的記錄拆分成兩個組，其中一個組中是4條記錄，另外一個組中是5條記錄，拆分程序中，會新增一個slot，記錄這個新增分組中最大的那條記錄的地址偏移量，
現在來看看下，目前該資料頁中的行記錄的分組情況，
來演繹一個根據主鍵查詢行記錄的例子，假如想查詢主鍵值 ，也就是C1=6的行記錄，通過二分法查找，程序如下：
1.設定low=0，high=4，計算中間slot的位置，(0 + 4) / 2 = 2, 通過slot 2 查詢到對應的主鍵值等于8，因為8 > 6， 所以設定high = 2， low = 0不變，
2.重新計算中間slot的位置，（0 + 2）/ 2 = 1, 查看 slot 1對應記錄的主鍵值為4，又因為 4 < 6, 所以設定low = 1，high 不變，
3.此時low = 1， high = 2， 所以確定主鍵值為6的行記錄在 slot2 對應的組中，此時找到slot 2的最小一條記錄【通過slot 1 的next_record找到slot 2的最小記錄】，遍歷slot 2中的所有記錄即可，
截止目前，資料頁模塊中，還要三個模塊是未知的，回想一下，對于一條行記錄，它有 記錄頭資訊 來描述這條行記錄的相關資訊，那么對于一個資料頁，它有對應的頭部來記錄資料頁的相關資訊嗎？
有的，自然是有的，而且還不少，這個模塊就稱為 Page Header，
Page Header的結構如下：
主要作用是標識 資料頁中記錄了多少條記錄，Free Space在頁面中的地址偏移量，頁目錄中包含多少slot等等，
額外說下page_direction 與 page_n_direction的含義，
page_direction: 假如新插入的一條記錄的主鍵值比上一條記錄的主鍵值比上一條記錄大，我們說這條記錄的插入方向是右邊，反之則是左邊，用來表示最后一條記錄插入方向的狀態就是page_direction，
page_n_direction: 假設連續幾次插入新記錄的方向都是一致的，InnoDB會把沿著同一個方向插入記錄的條數記下來，這個條數就用PAGE_N_DIRECTION這個狀態表示， 當然，如果最后一條記錄的插入方向改變了的話，這個狀態的值會被清零重新統計，
到此為止，僅剩下兩個模塊了，加油啊，
上文中的Page Header 是專門針對資料頁記錄的各種狀態資訊，但資料頁 僅僅是多種頁型別中的一種，其它的還有例如undo日志頁，溢位頁，存盤段資訊頁，存盤區資訊頁等， 因此mysql 使用了File Header 來描述各種頁的通用資訊，
從fil_page_prev 與 fil_page_next 兩個屬性可以聯想到，不同頁之間是有關聯的，而且是以雙向鏈表的形式，
最后一個模塊，File Trailer 【 [?tre?l?(r)]，掛車】，
InnoDB存盤引擎會把資料存盤到磁盤上，但是磁盤速度太慢，需要以頁為單位把資料加載到記憶體中處理，如果該頁中的資料在記憶體中被修改了，那么在修改后的某個時間需要把資料同步到磁盤中，
但是在同步了一半的時候中斷電了怎么處理呢？此時就需要靠 File Trailer 模塊中資料起作用，
展示下完整的資料頁結構，
盜用一下網上的一個很好的資料頁圖，
C. 快速查詢的秘籍：B+樹索引
上文在介紹File Header時，我們特別說明了里面的兩個資料：FIL_PAGE_PREV，指向前一個頁號，FIL_PAGE_NEXT, 指向后一個頁號，由此可以得出，多個資料頁之間的資料結構是雙鏈表，
上文使用的資料共有16條，為了演示這個雙鏈表的效果，現在假設【僅僅是假設】每個頁中存放不超過4條行記錄，則上文的16條記錄，形成的資料頁雙鏈表結構如下圖【此處省略了許多非必要展示的欄位】，
從上面這個鏈表，可以得到以下結論：
1.雙向鏈表的頁號并不保證是連續的，
2.下一個資料頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值，【在依次寫入主鍵資料不連續的行記錄時，會發生頁中資料的遷移，】
從目前的雙向鏈表結構中，想要根據主鍵值查找記錄，也只能是從第一頁開始，一頁一頁的依次查找，雖然在一個資料頁中，可以根據 Page Directory進行快速的二分查找，但總體效率肯定不盡人意，得優化，
我們注意到，【下一個資料頁中用戶記錄的主鍵值必須大于上一個頁中用戶記錄的主鍵值】，因此，首先進行第一步改進， 維護一個目錄項，目錄項中記錄某個頁中主鍵的最小值以及頁號，各個目錄項再以單向鏈表的形式鏈接起來，這樣就可以根據主鍵查詢目錄項，得到滿足的條件頁，再進入相應的頁中查詢行記錄即可，
到現在看看，目錄項是不是也很像行記錄，只是它的列值是主鍵與頁號，那把這些目錄項維護成在一個頁中看看效果，毫無違和感，渾然天成，現在看到的，就是主鍵索引的雛形了，
目前資料有些少了，繼續補充一些資料，再畫個圖看看，
INSERT INTO page_demo VALUES
(17, 1700, 'qqqq'),
(18, 1800, 'rrrr'),
(19, 1900, 'sss'),
(20, 2000, 'tttt');
現在看到的，就是一個典型的INNODB的主鍵索引了，它包含以下特點：
1.整個主鍵索引的資料結構是一棵樹，具體是以B+樹實作，
2.葉子節點與非葉子節點中的行記錄按照主鍵大小順序排成一個單向鏈表，頁內的記錄被劃分成若干組，可以利用Page Directory進行二分法快速查找到行記錄，
3.存放用戶記錄的資料頁，根據頁中用戶記錄的主鍵大小順序排成一個雙向鏈表，所有用戶記錄都存放在葉子節點上，
4.存放目錄項記錄的資料頁都是非葉子節點，分層不同的層級，同一層級中的頁也是根據頁中目錄項記錄的主鍵大小順序，排成一個雙向鏈表，
通常也把INNODB的B+樹索引稱為 聚簇索引（clustered/?kl?st?d / index），所有的真實資料都存盤在聚簇索引中，【索引即資料，資料即索引】，
通常除了主鍵索引之外，肯定還會建一些普通索引，稱為二級索引，或者輔助索引，上面的資料，我們以上文中的資料 C2列建立一個二級索引看看，
現在來看看下，INNODB中 二級索引的特點，
1.二級索引的資料結構 與 聚簇索引一樣，是B+樹結構，
2.二級索引的所有目錄項頁存盤行記錄的真實資料是 索引列+頁號，
3.二級索引的非葉子節點存盤行記錄的真實資料是 索引列+主鍵值，
因為在二級索引中查詢到的是主鍵值，如果想要得到完整的行記錄，則需要拿著主鍵值再到聚簇索引中再進行一次查詢，這個程序稱為【回表】， 【回表的程序，特別要強調下每次對于二級索引來說，每次查詢到一條滿足二級索引欄位條件的記錄時，都進行一次 回表 判斷是否滿足其他條件，然后將滿足所有條件的一條查詢結果回傳給客戶端，】
再講講聯合索引，現在以C2 與 C3兩列作為聯合索引，為了更好的展示聯合索引的效果，先修改幾條行記錄，
update page_demo set c3 = 'dddd' where c2 = 100;
update page_demo set c3 = 'cccc' where c2 = 200;
update page_demo set c3 = 'bbbb' where c2 = 300;
update page_demo set c3 = 'aaaa' where c2 = 400;
update page_demo set c2 = 300 where c1 = 4;
給聯合索引畫個圖，
總結下聯合索引的特點：
聯合索引的資料頁中記錄的排序，默認是按照定義聯合索引的第一列排序的，在第一列值相等的情況下，再按照第二列排序，其它的方面均與單列的二級索引無差別，
聯合索引還有一個比較特殊的使用場景：最左前綴匹配， 例如有聯合索引的列包含：C1，C2，C3 三列，而且順序也是 C1，C2，C3， 則查詢陳述句：select * from page_demo where c1 = x and c2 = y and c3= z, 使用到了C1，C2，C3 列排序的結果， select * from page_demo where c1 = x and c2 = y, 使用到了C1，C2 列排序的結果， select * from page_demo where c1 = x and c3 = z, 僅使用到了C1 列排序的結果，
D. 索引的優缺點及建議
優點：
1.對于等值查詢，可快速定位到對于的行記錄，
2.對于范圍查詢，可輔助縮小掃描區間，
3.當ORDER BY的列名 與 索引的列名完全一致時，可加快排序的順序，
4.當GROUP BY的列名 與 索引的列名完全一致時，可加快分組，
5.當二級索引列中 包含了 SELECT 關鍵字后面寫明的所有列，則在查詢完成二級索引之后無需進行回表操作，直接回傳即可，這種情況，稱為【覆寫索引】，
缺點：
1.建立索引占用磁盤空間，
2.對表中的資料進行 增加，洗掉，修改 操作時，都需要修改各個索引樹，特別是如果新增的行記錄的主鍵順序不是遞增的，就會產生頁分裂，頁回收等操作，有較大的時間成本，
3.當二級索引列的值 的 不重復值的個數較少時，通過二級索引查詢找到的資料量就會比較多，相應的就會產生過多的回表操作，
4.在執行查詢陳述句的時候，首先要生成一個執行計劃，通常情況下，一個SQL在執行程序中最多使用一個二級索引，在生成執行計劃時需要計算使用不同索引執行查詢時所需的成本，最后選擇成本最低的那個索引執行查詢， 因此，如果建立太多的索引，就會導致成本分析程序耗時太多，從而影響查詢陳述句的性能，
建議：
1.只為用于搜索，排序，分組的列創建索引，
2.索引的列需要有辨識性，盡可能地區分出不同的記錄，
3.索引列的型別盡量小，因為資料型別越小，索引占用的存盤空間就越少，在一個資料頁內就可以存放更多的記錄，磁盤I/O帶來的性能損耗也就越小，
4.如果需要對很長的欄位進行快速查詢，可考慮為列前綴建立索引，【alter table table_M add index idx_key1(column_n(10)) --> 將table_M表的 idx_key1列的前10個字符創建索引】
5.覆寫索引，當二級索引列中 包含了 SELECT 關鍵字后面寫明的所有列，則在查詢完成二級索引之后無需進行回表操作，直接回傳即可，因此，撰寫【select *】的時候，要想想是否必要，
6.在查詢陳述句中，索引列不要參與 條件值計算，也是把條件值計算完成之后，再和索引列對比，【否則MYSQL會認為 搜索條件不能形成 合適的掃描區間來減少掃描的記錄數量】
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/539687.html
標籤：其他