MySQL 是怎樣運(yùn)行的(一)：B+樹索引結(jié)構(gòu)

參考資料：[掘金] MySQL 是怎樣運(yùn)行的：從根兒上理解 MySQL
(https://juejin.cn/book/6844733769996304392/section)

第七章- 快速查詢的秘籍 —— B+ 樹索引
第八章- 好東西也得先學(xué)會(huì)怎么用 —— B+ 樹索引的使用

數(shù)據(jù)頁

數(shù)據(jù)頁-普通用戶記錄

  • InnoDB 使用頁來作為管理存儲(chǔ)空間的基本單位，每個(gè)頁擁有16KB的連續(xù)存儲(chǔ)空間。
  • 每個(gè)普通用戶記錄數(shù)據(jù)頁中的記錄會(huì)按主鍵值從小到大的順序組成一個(gè)單向鏈表。
  • 頁目錄：
    • 頁目錄是一個(gè)線性表，將數(shù)據(jù)記錄進(jìn)行分組，記錄每組數(shù)據(jù)第一個(gè)元素的地址。（于最小記錄所在的分組只能有 1條記錄，最大記錄所在的分組擁有的記錄條數(shù)只能在 1~8 條之間，剩下的分組中記錄的條數(shù)范圍只能在是 4~8 條之間）
    • 單個(gè)數(shù)據(jù)頁查找指定主鍵方法：a）通過二分法確定該記錄所在的槽，并找到該槽所在分組中主鍵值最小的那條記錄。b）通過記錄的next_record屬性遍歷該槽所在的組中的各個(gè)記錄。

單頁的數(shù)據(jù)結(jié)構(gòu)示意圖：

image.png

數(shù)據(jù)頁-目錄項(xiàng)記錄

  • 各個(gè)普通用戶記錄數(shù)據(jù)頁可以組成一個(gè)雙向鏈表，也是按照key的大小順序排列的。即：下一個(gè)數(shù)據(jù)頁中用戶記錄的主鍵值必須大于上一個(gè)頁中用戶記錄的主鍵值。
  • 目錄項(xiàng)頁中保存了普通用戶記錄頁的最小值和頁面地址。
  • 多個(gè)數(shù)據(jù)頁查找指定主鍵的方法：如查找主鍵為20的記錄。a) 先到存儲(chǔ)目錄項(xiàng)記錄的頁，也就是頁30中通過二分法快速定位到對(duì)應(yīng)目錄項(xiàng)，因?yàn)?code>12 < 20 < 209，所以定位到對(duì)應(yīng)的記錄所在的頁就是頁9。b) 再到存儲(chǔ)用戶記錄的頁9中根據(jù)二分法快速定位到主鍵值為20的用戶記錄。
image.png

InnoDB中索引（B+樹）

  • 如果有多個(gè)目錄項(xiàng)頁，為這些存儲(chǔ)目錄項(xiàng)記錄的頁再生成一個(gè)更高級(jí)的目錄。就像是一個(gè)多級(jí)目錄一樣，大目錄里嵌套小目錄，小目錄里才是實(shí)際的數(shù)據(jù)。這就是B+樹的結(jié)構(gòu)。
  • 下圖是3層的B+樹，一般我們用到B+樹都不會(huì)超過4層，否則數(shù)據(jù)量太大會(huì)影響查詢和修改效率（考慮分區(qū)、分庫分表）。

B+樹示意圖：

image.png

B+樹的特點(diǎn)：

  1. 使用記錄主鍵值的大小進(jìn)行記錄和頁的排序，這包括三個(gè)方面的含義：
    • 頁內(nèi)的記錄是按照主鍵的大小順序排成一個(gè)單向鏈表。
    • 各個(gè)存放用戶記錄的頁也是根據(jù)頁中用戶記錄的主鍵大小順序排成一個(gè)雙向鏈表。
    • 存放目錄項(xiàng)記錄的頁分為不同的層次，在同一層次中的頁也是根據(jù)頁中目錄項(xiàng)記錄的主鍵大小順序排成一個(gè)雙向鏈表。
  2. B+樹只有葉子節(jié)點(diǎn)儲(chǔ)存了value值，非葉子節(jié)點(diǎn)只儲(chǔ)存key值和頁面地址。查詢的時(shí)候，必須經(jīng)歷從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)一層一層往下搜索。

聚簇索引

  • 聚簇索引中，B+樹的葉子節(jié)點(diǎn)存儲(chǔ)的是完整的用戶記錄。所謂完整的用戶記錄，就是指這個(gè)記錄中存儲(chǔ)了所有列的值。
  • InnoDB存儲(chǔ)引擎會(huì)自動(dòng)的為我們創(chuàng)建聚簇索引，索引的key值為主鍵值（primary key）。

二級(jí)索引

使用c2列創(chuàng)建二級(jí)索引：

  • B+樹的葉子節(jié)點(diǎn)存儲(chǔ)的并不是完整的用戶記錄，而只是c2列+主鍵這兩個(gè)列的值。
  • 目錄項(xiàng)記錄中不再是主鍵+頁號(hào)的搭配，而變成了c2列+頁號(hào)的搭配。

利用二級(jí)索引搜索用戶記錄的過程（需要回表）：

  1. 利用c2索引的B+樹，查找用戶記錄的主鍵。

  2. 根據(jù)c2列的值到聚簇索引中再查一遍，獲取完整的用戶記錄，這個(gè)過程叫回表。（如果只查詢c2列和主鍵，則不需要回表。因此select語句應(yīng)只查詢必要字段，避免select *。）

image.png

聯(lián)合索引

我們也可以同時(shí)以多個(gè)列的大小作為排序規(guī)則，也就是同時(shí)為多個(gè)列建立索引，比方說我們想讓B+樹按照c2和c3列的大小進(jìn)行排序，這個(gè)包含兩層含義：

  • 先把各個(gè)記錄和頁按照c2列進(jìn)行排序。
  • 在記錄的c2列相同的情況下，采用c3列進(jìn)行排序

為c2和c3列建立的索引的示意圖如下：

image.png

如圖所示，我們需要注意一下幾點(diǎn)：

  • 每條目錄項(xiàng)記錄都由c2、c3、頁號(hào)這三個(gè)部分組成，各條記錄先按照c2列的值進(jìn)行排序，如果記錄的c2列相同，則按照c3列的值進(jìn)行排序。
  • B+樹葉子節(jié)點(diǎn)處的用戶記錄由c2、c3和主鍵c1列組成。

唯一索引和普通索引

  • 唯一索引：

    ALTER TABLE `tt_test`
ADD UNIQUE INDEX `un_index_title` (`title`) USING BTREE ;

  • 普通索引

    ALTER TABLE `tt_test`
ADD INDEX `k_title` (`title`) USING BTREE ;

普通索引的B+樹

  • 使用上文描述B+樹存在的問題：索引列 + 頁號(hào) 無法確定唯一的用戶數(shù)據(jù)，在新插入記錄時(shí)，無法確定數(shù)據(jù)放在葉子節(jié)點(diǎn)的哪個(gè)頁面。

  • 我們需要保證在B+樹的同一層內(nèi)節(jié)點(diǎn)的目錄項(xiàng)記錄除頁號(hào)這個(gè)字段以外是唯一的。所以對(duì)于二級(jí)索引的內(nèi)節(jié)點(diǎn)的目錄項(xiàng)記錄的內(nèi)容實(shí)際上是由三個(gè)部分構(gòu)成的：

    • 索引列的值
    • 主鍵值
    • 頁號(hào)

MyISAM中的索引方案

  • MyISAM 中的記錄按照記錄的插入順序單獨(dú)存儲(chǔ)在一個(gè)文件中，包含行號(hào)和用戶數(shù)據(jù)。
  • MyISAM會(huì)單獨(dú)為表的主鍵創(chuàng)建一個(gè)索引，索引的葉子節(jié)點(diǎn)中存儲(chǔ)的不是完整的用戶記錄，而是主鍵值 + 行號(hào)的組合。
  • 根據(jù)主鍵查詢時(shí)，需要先通過索引找到對(duì)應(yīng)的行號(hào)，再通過行號(hào)去找對(duì)應(yīng)的記錄，也就是需要回表。（MyISAM索引葉子節(jié)點(diǎn)記錄的是物理地址偏移量，回表比InnoDB快）

索引的代價(jià)

一個(gè)表上索引建的越多，就會(huì)占用越多的存儲(chǔ)空間，在增刪改記錄的時(shí)候性能就越差。

  • 空間上的代價(jià)

    這個(gè)是顯而易見的，每建立一個(gè)索引都要為它建立一棵B+樹，每一棵B+樹的每一個(gè)節(jié)點(diǎn)都是一個(gè)數(shù)據(jù)頁，一個(gè)頁默認(rèn)會(huì)占用16KB的存儲(chǔ)空間，一棵很大的B+樹由許多數(shù)據(jù)頁組成，那可是很大的一片存儲(chǔ)空間呢。

  • 時(shí)間上的代價(jià)

    每次對(duì)表中的數(shù)據(jù)進(jìn)行增、刪、改操作時(shí)，都需要去修改各個(gè)B+樹索引。而增、刪、改操作可能會(huì)對(duì)節(jié)點(diǎn)和記錄的排序造成破壞，所以存儲(chǔ)引擎需要額外的時(shí)間進(jìn)行一些記錄移位，頁面分裂、頁面回收啥的操作來維護(hù)好節(jié)點(diǎn)和記錄的排序。

B+樹索引適用的條件

  • 全值匹配

    搜索條件中的列和索引列完全一致

  • 匹配左邊的列

    聯(lián)合索引左邊的列，必須是左連續(xù)的列。

    例如：聯(lián)合索引idx_name_birthday_phone_number中列的定義順序是name、birthday、phone_number 。

    以下語句適用于索引查詢

    SELECT * FROM person_info WHERE name = 'Ashburn';
SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday = '1990-09-27';

  • 匹配列前綴

    適用于字符串查詢。字符串排序?qū)嶋H上是：先按照字符串的第一個(gè)字符進(jìn)行排序，如果第一個(gè)字符相同再按照第二個(gè)字符進(jìn)行排序，以此類推。

    像這樣的前綴查詢語句可以適用于索引查詢：

    SELECT * FROM person_info WHERE name LIKE 'As%';

  • 匹配范圍值

    SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';

    范圍查找的過程如下：

    • 通過B+樹在葉子節(jié)點(diǎn)中找到第一條name值大于Asa的二級(jí)索引記錄，讀取該記錄的主鍵值進(jìn)行回表操作，獲得對(duì)應(yīng)的聚簇索引記錄后發(fā)送給客戶端。
    • 根據(jù)上一步找到的記錄，沿著記錄所在的鏈表向后查找（同一頁面中的記錄使用單向鏈表連接起來，數(shù)據(jù)頁之間用雙向鏈表連接起來）下一條二級(jí)索引記錄，判斷該記錄是否符合name < 'Barlow'條件，如果符合，則進(jìn)行回表操作后發(fā)送至客戶端。
    • 重復(fù)上一步驟，直到某條二級(jí)索引記錄不符合name <'Barlow'條件為止。

  • 精確匹配某一列并范圍匹配另一列

    SELECT * FROM person_info WHERE name = 'Ashburn' AND birthday > '1980-01-01' AND birthday < '2000-12-31'

    查找過程如下：

    • name = 'Ashburn'，對(duì)name列進(jìn)行精確查找，當(dāng)然可以使用B+樹索引了。
    • birthday > '1980-01-01' AND birthday < '2000-12-31'，由于name列是精確查找，所以通過name = 'Ashburn'條件查找后得到的結(jié)果的name值都是相同的，它們會(huì)再按照birthday的值進(jìn)行排序。所以此時(shí)對(duì)birthday列進(jìn)行范圍查找是可以用到B+樹索引的。

  • 用于排序

    文件排序（英文名：filesort） ：一般情況下，我們只能把記錄都加載到內(nèi)存中，利用排序算法排序，如果內(nèi)存容量不夠，還需要借助磁盤空間。文件排序的效率非常低。

    利用索引排序：（全值匹配或者匹配左邊的列）

    SELECT * FROM person_info ORDER BY name, birthday, phone_number LIMIT 10;

    直接提取聯(lián)合索引idx_name_birthday_phone_number的前10條記錄，再進(jìn)行回表。

    注意，以下情況不會(huì)用到索引：

    1. 排序列包含非同一個(gè)索引的列。如name和country不是同一個(gè)索引中的列。

      SELECT * FROM person_info ORDER BY name, country LIMIT 10;

    2. 排序類使用了復(fù)雜的表達(dá)式，如使用了UPPER函數(shù)

      SELECT * FROM person_info ORDER BY UPPER(name) LIMIT 10;

    3. ASC、DESC混用

  • 用于分組

    和用于排序類似，分組列的順序也需要和索引列的順序一致，也可以只使用索引列中左邊的列進(jìn)行分組。

    SELECT name, birthday, phone_number, COUNT(*) FROM person_info GROUP BY name, birthday, phone_number

回表的代價(jià)

  • 回表會(huì)使用到兩個(gè)B+樹索引，一個(gè)二級(jí)索引，一個(gè)聚簇索引。

  • 訪問二級(jí)索引使用順序I/O，訪問聚簇索引使用隨機(jī)I/O。

  • 需要回表的記錄越多，使用二級(jí)索引的性能就越低，甚至讓某些查詢寧愿使用全表掃描也不使用二級(jí)索引。

    比方說name值在Asa～Barlow之間的用戶記錄數(shù)量占全部記錄數(shù)量90%以上，那么如果使用idx_name_birthday_phone_number索引的話，有90%多的id值需要回表，還不如直接去掃描聚簇索引（也就是全表掃描）。

    SELECT * FROM person_info WHERE name > 'Asa' AND name < 'Barlow';

  • 覆蓋索引不需要回表。因此查詢的時(shí)候盡量只查必要的字段。

    由于索引中包含 name, birthday, phone_number 三個(gè)字段，以下SQL查詢不需要回表操作。

    SELECT name, birthday, phone_number FROM person_info WHERE name > 'Asa' AND name < 'Barlow'
SELECT name, birthday, phone_number  FROM person_info ORDER BY name, birthday, phone_number;

索引注意事項(xiàng)

在使用索引時(shí)需要注意下邊這些事項(xiàng)：

  • 只為用于搜索、排序或分組的列創(chuàng)建索引

    只為出現(xiàn)在WHERE子句中的列、連接子句中的連接列，或者出現(xiàn)在ORDER BY或GROUP BY子句中的列創(chuàng)建索引。

  • 為列的基數(shù)大的列創(chuàng)建索引

    • 列的基數(shù)指的是某一列中不重復(fù)數(shù)據(jù)的個(gè)數(shù)，比方說某個(gè)列包含值2, 5, 8, 2, 5, 8, 2, 5, 8，雖然有9條記錄，但該列的基數(shù)卻是3。也就是說，在記錄行數(shù)一定的情況下，列的基數(shù)越大，該列中的值越分散，列的基數(shù)越小，該列中的值越集中。
    • 最好為那些列的基數(shù)大的列建立索引，為基數(shù)太小列的建立索引效果可能不好。（如果列的基數(shù)小，查出來相同的數(shù)據(jù)較多，回表的代價(jià)也較大）

  • 索引列的類型盡量小

    如能使用int就不使用bigint

    • 數(shù)據(jù)類型越小，在查詢時(shí)進(jìn)行的比較操作越快（這是CPU層次的東東）
    • 數(shù)據(jù)類型越小，索引占用的存儲(chǔ)空間就越少，在一個(gè)數(shù)據(jù)頁內(nèi)就可以放下更多的記錄，從而減少磁盤I/O帶來的性能損耗，也就意味著可以把更多的數(shù)據(jù)頁緩存在內(nèi)存中，從而加快讀寫效率。

  • 可以只對(duì)字符串值的前綴建立索引

    前綴索引：只對(duì)字符串的前幾個(gè)字符進(jìn)行索引也就是說在二級(jí)索引的記錄中只保留字符串前幾個(gè)字符。

    建立前綴索引的理由：和上一條索引列類型盡量小的理由類似：

    • B+樹索引中的記錄需要把該列的完整字符串存儲(chǔ)起來，而且字符串越長，在索引中占用的存儲(chǔ)空間越大。
    • 如果B+樹索引中索引列存儲(chǔ)的字符串很長，那在做字符串比較時(shí)會(huì)占用更多的時(shí)間。

    注意：前綴索引不支持排序，如下

    CREATE TABLE person_info(
    name VARCHAR(100) NOT NULL,
    birthday DATE NOT NULL,
    phone_number CHAR(11) NOT NULL,
    country varchar(100) NOT NULL,
    KEY idx_name_birthday_phone_number (name(10), birthday, phone_number)
);    

SELECT * FROM person_info ORDER BY name LIMIT 10;

  • 只有索引列在比較表達(dá)式中單獨(dú)出現(xiàn)才可以適用索引

    第一種寫法會(huì)讓索引失效，因?yàn)?my_col * 2 不是單獨(dú)的列，而是包含表達(dá)式。

    WHERE my_col * 2 < 4
WHERE my_col < 4/2

  • 為了盡可能少的讓聚簇索引發(fā)生頁面分裂和記錄移位的情況，建議讓主鍵擁有AUTO_INCREMENT屬性。

    為了避免插入的時(shí)候頁分裂等操作，讓主鍵擁有AUTO_INCREMENT屬性，可以按順序插入值。

  • 定位并刪除表中的重復(fù)和冗余索引

    如下列代碼中，idx_name 是冗余索引，因?yàn)槁?lián)合索引 idx_name_birthday_phone_number 已經(jīng)具備按照name查詢的個(gè)功能。

    CREATE TABLE person_info(
    id INT UNSIGNED NOT NULL AUTO_INCREMENT,
    name VARCHAR(100) NOT NULL,
    birthday DATE NOT NULL,
    phone_number CHAR(11) NOT NULL,
    country varchar(100) NOT NULL,
    PRIMARY KEY (id),
    KEY idx_name_birthday_phone_number (name(10), birthday, phone_number),
    KEY idx_name (name(10))
);

  • 盡量使用覆蓋索引進(jìn)行查詢，避免回表帶來的性能損耗。

B樹和B+樹對(duì)比

參考文章1：https://zhuanlan.zhihu.com/p/27700617
參考文章2：http://www.itdecent.cn/p/a15bd7e5252b

image.png

B樹和B+樹的規(guī)則有什么不同：

  1. B+樹的非葉子節(jié)點(diǎn)不保存key對(duì)應(yīng)的value值，只有葉子節(jié)點(diǎn)保存了value。所有value必須要到葉子節(jié)點(diǎn)才能獲取到。B樹葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)都保存了key和value。
  2. B+樹葉子節(jié)點(diǎn)之間組成一個(gè)雙向鏈表，B樹的葉子節(jié)點(diǎn)是單獨(dú)的。

為什么MySQL選用B+樹，B+樹相較B樹有哪些優(yōu)點(diǎn)：

  1. B+樹的層級(jí)更少：相較于B樹B+每個(gè)非葉子節(jié)點(diǎn)存儲(chǔ)的關(guān)鍵字?jǐn)?shù)更多，樹的層級(jí)更少所以查詢數(shù)據(jù)更快；
  2. B+樹查詢速度更穩(wěn)定：B+所有關(guān)鍵字?jǐn)?shù)據(jù)地址都存在葉子節(jié)點(diǎn)上，所以每次查找的次數(shù)都相同所以查詢速度要比B樹更穩(wěn)定;
  3. B+樹天然具備排序功能：B+樹所有的葉子節(jié)點(diǎn)數(shù)據(jù)構(gòu)成了一個(gè)有序鏈表，在查詢大小區(qū)間的數(shù)據(jù)時(shí)候更方便，數(shù)據(jù)緊密性很高，緩存的命中率也會(huì)比B樹高。
  4. B+樹全節(jié)點(diǎn)遍歷更快：B+樹遍歷整棵樹只需要遍歷所有的葉子節(jié)點(diǎn)即可，，而不需要像B樹一樣需要對(duì)每一層進(jìn)行遍歷，這有利于數(shù)據(jù)庫做全表掃描。

B樹相對(duì)于B+樹的優(yōu)點(diǎn)是，如果經(jīng)常訪問的數(shù)據(jù)離根節(jié)點(diǎn)很近，而B樹的非葉子節(jié)點(diǎn)本身存有關(guān)鍵字其數(shù)據(jù)的地址，所以這種數(shù)據(jù)檢索的時(shí)候會(huì)要比B+樹快。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容