MySQL索引為什么是B+樹

索引是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，在數(shù)據(jù)之外，數(shù)據(jù)庫還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)B+樹，這些數(shù)據(jù)結(jié)果以某種特定的方式引用數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)高級(jí)查找算法，提升數(shù)據(jù)的查找速度，這種數(shù)據(jù)結(jié)構(gòu)就是索引

如果此時(shí)有一個(gè)user表，在它還未建立索引的時(shí)候，如果想要查找age為35歲的用戶：

select * from user where age = 35

那么此時(shí)在user表中會(huì)逐個(gè)查找每一行，直到查找到最后一行，然后返回age為35的行

這樣的查找無疑是非常耗時(shí)的，當(dāng)數(shù)據(jù)量非常龐大時(shí)，全部檢索整張表會(huì)消耗大量的時(shí)間和性能，因此需要為數(shù)據(jù)建立合適的索引來提高查詢的效率

那為什么MySQL采用的是B+數(shù)呢？而不是二叉樹、紅黑數(shù)呢？

二叉樹

二叉樹在查找時(shí)，使用的是二分查找算法，查詢效率得到了提高，并且二叉樹簡(jiǎn)單易實(shí)現(xiàn)，當(dāng)數(shù)據(jù)量較小時(shí)，普通二叉樹的性能已經(jīng)能滿足要求，開銷更小

但是二叉樹有一個(gè)非常致命的缺點(diǎn)：高度不穩(wěn)定

普通二叉樹在數(shù)據(jù)分布不均時(shí)可能變成鏈表狀，最壞情況下高度為 O(n)，影響查找性能：

紅黑樹

紅黑樹是一種自平衡二叉搜索樹，保證任何路徑的最大深度不超過最小深度的兩倍，自平衡的特性完美解決了二叉樹中高度不穩(wěn)定的特點(diǎn)，查找、插入和刪除操作的時(shí)間復(fù)雜度始終保持在 O(log?n)，在插入和刪除操作引入了旋轉(zhuǎn)、變色等機(jī)制，確保平衡性，無需頻繁重構(gòu)樹結(jié)構(gòu)

紅黑規(guī)則：

• 每個(gè)節(jié)點(diǎn)都有一個(gè)顏色屬性，可以是紅色或黑色。
• 紅黑樹的根節(jié)點(diǎn)必須是黑色。
• 所有的葉子節(jié)點(diǎn)（即樹中的 null 節(jié)點(diǎn)）是黑色的。葉子節(jié)點(diǎn)不包含數(shù)據(jù)，只是輔助結(jié)構(gòu)。
• 如果一個(gè)節(jié)點(diǎn)是紅色的，則其子節(jié)點(diǎn)必須是黑色。這確保了沒有兩個(gè)紅色節(jié)點(diǎn)相連，從而避免了樹的高度過高。
• 任何路徑從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)或者空節(jié)點(diǎn)的過程中，必須經(jīng)過相同數(shù)量的黑色節(jié)點(diǎn)。這保證了紅黑樹的平衡性，避免了一些路徑比其他路徑過長(zhǎng)，從而影響查找效率。

但是當(dāng)數(shù)據(jù)規(guī)模量巨大時(shí)，他也會(huì)暴露出來缺點(diǎn)：深度較大

因此紅黑數(shù)無法適應(yīng)大規(guī)模數(shù)據(jù)，而且每個(gè)節(jié)點(diǎn)只存儲(chǔ)一個(gè)鍵值，導(dǎo)致樹的層數(shù)增加，浪費(fèi)存儲(chǔ)空間，紅黑樹需要通過中序遍歷才能完成范圍查詢，因此在大規(guī)模數(shù)據(jù)量的場(chǎng)景下，查詢效率依然不高

B樹

B樹（B-tree）是一種自平衡的多路搜索樹，它能夠保持?jǐn)?shù)據(jù)有序，并允許高效的插入、刪除和查找操作

B樹的特點(diǎn)包括：

1. 平衡性：B樹是一種平衡樹，所有葉子節(jié)點(diǎn)的深度相同。通過這種結(jié)構(gòu)，B樹保證了對(duì)所有節(jié)點(diǎn)的訪問時(shí)間是相同的，從而提高了查找效率。
2. 多路性：B樹的每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)（通常是 m 個(gè)子節(jié)點(diǎn)）。這使得B樹能夠存儲(chǔ)更多的數(shù)據(jù)，并且能更快地完成查找、插入、刪除等操作。
3. 節(jié)點(diǎn)結(jié)構(gòu)：每個(gè)節(jié)點(diǎn)包含若干個(gè)關(guān)鍵字（data），并且包含指向其子節(jié)點(diǎn)的指針。對(duì)于每個(gè)節(jié)點(diǎn)中的關(guān)鍵字，子節(jié)點(diǎn)的關(guān)鍵字范圍是有序的。
4. 查找效率：B樹的查找操作類似于二叉查找樹，但是每個(gè)節(jié)點(diǎn)具有多個(gè)子節(jié)點(diǎn)。查找操作的時(shí)間復(fù)雜度為O(log n)，其中n是樹中的元素個(gè)數(shù)。
5. 插入和刪除操作：插入和刪除操作需要保證樹的平衡性，插入時(shí)可能會(huì)導(dǎo)致節(jié)點(diǎn)分裂，刪除時(shí)可能會(huì)引起節(jié)點(diǎn)合并或借用關(guān)鍵字。所有這些操作都在O(log n)時(shí)間內(nèi)完成。

他的單個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)數(shù)據(jù)和多個(gè)指針，每個(gè)節(jié)點(diǎn)也可以有多個(gè)分支，因此他的每一層級(jí)可以存放大量數(shù)據(jù)，同樣遵循左邊大右邊小的存儲(chǔ)規(guī)則，因此B樹的查找效率是十分優(yōu)秀的，B樹通常用于數(shù)據(jù)庫和文件系統(tǒng)中，用于存儲(chǔ)和管理大量數(shù)據(jù)

但是MySQL中使用的數(shù)據(jù)結(jié)構(gòu)并不是B樹，而是B+樹，相比B樹，B+樹更加優(yōu)秀

B+樹

B+樹是B樹的變種，它具有與B樹類似的結(jié)構(gòu)和特點(diǎn)，但在某些方面有所改進(jìn)，特別是在存儲(chǔ)和查找效率上。B+樹通常用于數(shù)據(jù)庫和文件系統(tǒng)中，作為一種高效的索引結(jié)構(gòu)

所有數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)中：

• 在B樹中，數(shù)據(jù)可以存儲(chǔ)在內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)中，而在B+樹中，所有的數(shù)據(jù)（即關(guān)鍵字）都僅存儲(chǔ)在葉子節(jié)點(diǎn)中。內(nèi)部節(jié)點(diǎn)只存儲(chǔ)關(guān)鍵字，用于引導(dǎo)查找過程。
• 這種設(shè)計(jì)可以減少內(nèi)部節(jié)點(diǎn)的存儲(chǔ)空間，提高查詢效率。

葉子節(jié)點(diǎn)通過鏈表連接：

• B+樹的葉子節(jié)點(diǎn)通常是通過一個(gè)鏈表連接起來的，這使得范圍查詢（例如查找某個(gè)區(qū)間內(nèi)的所有數(shù)據(jù)）變得更加高效。
• 通過遍歷鏈表，可以一次性返回區(qū)間內(nèi)的所有數(shù)據(jù)，而不需要回溯到其他節(jié)點(diǎn)。

樹的高度較小：

• 由于所有數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)中，B+樹的內(nèi)部節(jié)點(diǎn)只需要存儲(chǔ)關(guān)鍵字和指向子節(jié)點(diǎn)的指針。
• 因此，相比于B樹，B+樹可以將更多的數(shù)據(jù)存儲(chǔ)在每個(gè)節(jié)點(diǎn)中，從而使樹的高度變得更小，查找操作的效率更高。

查找操作的效率更高：

• B+樹的查找操作通常僅限于葉子節(jié)點(diǎn)，而B樹在查找時(shí)可能需要在內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)之間反復(fù)跳轉(zhuǎn)。
• 由于葉子節(jié)點(diǎn)之間有鏈表連接，B+樹在范圍查詢時(shí)特別高效。

B+樹相較于B樹，在查找和范圍查詢上有顯著的優(yōu)勢(shì)，尤其在數(shù)據(jù)庫和文件系統(tǒng)中，因?yàn)樗軌蛴行У販p少磁盤I/O操作，并提高查詢效率。因此，MySQL選擇了B+樹作為索引的數(shù)據(jù)結(jié)構(gòu)

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論