MySQL索引為什么是B+樹(shù)

索引是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，在數(shù)據(jù)之外，數(shù)據(jù)庫(kù)還維護(hù)著滿(mǎn)足特定查找算法的數(shù)據(jù)結(jié)構(gòu)B+樹(shù)，這些數(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歲的用戶(hù)：

select * from user where age = 35

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

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

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

二叉樹(shù)

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

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

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

紅黑樹(shù)

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

紅黑規(guī)則：

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

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

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

B樹(shù)

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

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

1. 平衡性：B樹(shù)是一種平衡樹(shù)，所有葉子節(jié)點(diǎn)的深度相同。通過(guò)這種結(jié)構(gòu)，B樹(shù)保證了對(duì)所有節(jié)點(diǎn)的訪(fǎng)問(wèn)時(shí)間是相同的，從而提高了查找效率。
2. 多路性：B樹(shù)的每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)（通常是 m 個(gè)子節(jié)點(diǎn)）。這使得B樹(shù)能夠存儲(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樹(shù)的查找操作類(lèi)似于二叉查找樹(shù)，但是每個(gè)節(jié)點(diǎn)具有多個(gè)子節(jié)點(diǎn)。查找操作的時(shí)間復(fù)雜度為O(log n)，其中n是樹(shù)中的元素個(gè)數(shù)。
5. 插入和刪除操作：插入和刪除操作需要保證樹(shù)的平衡性，插入時(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樹(shù)的查找效率是十分優(yōu)秀的，B樹(shù)通常用于數(shù)據(jù)庫(kù)和文件系統(tǒng)中，用于存儲(chǔ)和管理大量數(shù)據(jù)

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

B+樹(shù)

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

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

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

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

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

樹(shù)的高度較小：

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

查找操作的效率更高：

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

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

總結(jié)

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

最新評(píng)論