MySQL索引為什么是B+樹

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

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

select * from user where age = 35

那么此時在user表中會逐個查找每一行，直到查找到最后一行，然后返回age為35的行

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

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

二叉樹

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

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

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

紅黑樹

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

紅黑規(guī)則：

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

但是當數(shù)據(jù)規(guī)模量巨大時，他也會暴露出來缺點：深度較大

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

B樹

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

B樹的特點包括：

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

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

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

B+樹

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

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

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

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

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

樹的高度較小：

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

查找操作的效率更高：

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

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

總結(jié)

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

最新評論