資料庫與I/O原理
資料會持久化到磁盤，查詢資料是就會有I/O操作，相對于快取操作，I/O操作的時間成本相當高昂，
I/O操作的基本單位是一個磁盤頁面，比如16KB的頁面大小，當資料量比較大時，單表資料就會分布在多個磁盤頁面，
如果沒有索引，就必須按順序加載磁盤頁面到快取進行查找，判斷資料是否存在，隨著資料量的增長，磁盤I/O操作的次數也會越來越多，
因此，有必要通過一些輔助的資料結構來提交檢索的速度，
從上面可以看出，想要快速讀取到資料，可從以下幾個方面著手
1. 如何盡量減少磁盤IO操作
2. 如何快速定位到資料所在的磁盤頁面
3. 如何快速定位資料在磁盤頁面內的位置
資料庫索引是什么
索引是存盤引擎用于快速查找記錄的一種資料結構，
舉個類似的例子，當我們要閱讀《高性能MySQL》的第五章時，一般會先查找目錄，找到第五章對應的頁碼，然后翻到對應頁碼即可，
目錄一般不會超過10頁，整本書有將近700頁，
如果沒有目錄，那么我們只能順序或者使用二分的方法來查找第五章，需要翻頁的次數就會更多，
索引的作用與書籍的目錄相似，用于輔助快速查找目標資料，
存盤結構
記錄(行)格式
InnoDB支持四種記錄格式，分別是REDUNDANT、COMPACT、DYNAMIC和COMPRESSED，MySQL5.7默認是DYNAMIC格式，
下圖是DYNAMIC行格式的示意圖
記錄頭資訊的格式示意圖如下
部分欄位含義
deleted_flag:顧名思義，該記錄是否被洗掉的標志
min_rec_flag:B+樹每層非葉子結點中最小的記錄項的標志
n_owned: 頁面中分組的
heap_on: 表示當前記錄在頁面堆中的相對記錄
record_type: 表示當前記錄的型別，0表示普通記錄，1表示B+樹非葉子結點的目錄項記錄，2表示Infimum記錄，3表示Supremum記錄，
next_record: 指向下一條記錄，表示下一條記錄的相對位置
記錄示例
所有頁面都有兩條虛擬記錄，即Infimum和Supremum，
Infimum代表頁面中的最小的記錄，而Supremum則代表頁面中最大的記錄，
資料排序
頁內的記錄串聯成一個單向鏈表，
如果表有主鍵，會根據主鍵排序；
沒主鍵有唯一非空索引，會根據該索引排序；
兩者都沒有，InnoDB會自動生成一個row_id列并根據該列進行排序，
頁面格式
頁是InnoDB管理存盤空間的基本單位，一個頁的大小一般是16K，
資料頁面的結構如下圖
File Header：頁面通用資訊，如當前頁號、上一頁/下一頁頁號
Page Header：頁面的各種狀態資訊，如分組數量，記錄數
User Records：記錄的有序鏈表
Free Space：頁面中尚未使用的空間
Page Directory：對User Records資料進行分組，減少遍歷鏈表的次數，加速查找
File Tailer：校驗頁面資料是否完整
資料查找
頁面內的資料是有序的單向鏈表，
假設單行資料128B，而單個磁盤頁面大小可以是16KB，因此一個磁盤頁面最多可以存放128條資料，這樣挨個查找太慢，
可以利用有序鏈表的特性，對有序資料進行分組，記錄每組的最大值，形成一個有序分組串列，先二分查找有序分組串列，再查找分組內的資料，
這里就會涉及的行記錄的n_owned和頁面的Page Directory了，InnoDB分組規則如下
1. Infimum記錄所在的分組只能有一條記錄
2. Supremum記錄所在的分組擁有的記錄數量為1～8條
3. 其它分組擁有的記錄數量為4～8條
4. 分組指向組內ID最大的行，
查找程序
下圖是簡化的行記錄和Page Directory，
在上圖中查找ID=17的記錄
1. 利用分組進行二分查找，
(1 + 5) / 2 = 3，分組3的最大ID為10，因此繼續在右半區間查找
(3 + 5) / 2 = 4，分組最大的ID為15，17位于右半區間，又應為5 - 4 = 1，因此，17位于分組5
2. 組內順序查找
在分組內遍歷單向鏈表，查找到ID=17的記錄
B+樹索引
B+樹資料結構
在B樹詳解，這邊隨筆中介紹了B樹的查找、插入、洗掉操作，可以深入理解B數的資料結構
CREATE TABLE `t_student` ( `id` int NOT NULL AUTO_INCREMENT COMMENT '主鍵ID', `age` int NOT NULL DEFAULT '0' COMMENT '年齡', `height` int NOT NULL DEFAULT '0' COMMENT '身高' PRIMARY KEY (`id`) KEY `age` (`age`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci ROW_FORMAT=COMPACT
聚簇索引
為了方便畫圖表示，下面是簡化的聚簇索引各種記錄格式
聚簇索引結構舉例
從上圖可以看出，
1）頁面內記錄按照主鍵增長的順序構成一個單項鏈表
2）對于普通記錄，則是一個按照主鍵有序的雙向鏈表
二級索引
為了方便畫圖表示，下面是簡化的二級索引各種記錄格式
二級索引結構舉例
1）頁面內記錄按照二級索引age增長的順序構成一個單項鏈表
2）對于普通記錄，則是一個按照age有序的雙向鏈表
3）普通記錄并沒沒有包含完整的資訊，而是<age,主鍵>的組合，需要取其它資訊如height還需要進行回表
回表: 資料庫根據索引（非主鍵）找到了指定的記錄所在行后，還需要根據索引上保存的主鍵 ID 再次到資料塊里獲取資料，
建立索引的原則
1. 盡量使用占用空間少的索引
索引欄位占用空間小，意味著單個頁面可以存放更多的目錄專案記錄，使得B+數更加扁平，從而減少IO次數
2. 選擇頻繁作為查詢條件的欄位作為索引
頻繁作為查詢條件的欄位作為索引，減少查詢的時間，避免全表查詢，
3. 選擇區分度高的欄位作為索引
例如性別只有男1女2兩種情況，如果建立索引，目錄項只有兩條記錄，意義不大，還增加了維護索引的成本，
4. 最左匹配原則
多個欄位構成聯合索引時，這幾個欄位的順序十分重要，
假設有聯合索引<a，b，c>
目錄項記錄是先按a排序，如果a相等再按b排序，如果a和b都相等，再按c排序，
如果查詢條件只有(b,c)，則改索引并不會生效，如果只有(a)，那索引只是部分生效，
InnoDB Row Formats
《MySQL是怎么運行的》
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/502950.html
標籤：MySQL
上一篇：JDBC
下一篇：Redis 集群模式