首頁 > mysql教程 閱讀:0更新時間:2020-12-13 05:41:25

MySQL索引為什么要使用B+樹

mysql索引為什么要使用B+樹

1. 二叉搜索樹

MySQL索引為什么要使用B+樹
缺點:第一個插入的數據始終在最上面,如果我們要查詢0006號數據,它將對比5次,將會不能方便快速查找。
所以引入紅黑樹,紅黑樹可以解決上面的問題。

2. 紅黑樹

MySQL索引為什么要使用B+樹

我的插入順序為1~9,順序插入,得到上面這個數據結構。它每插入一個數據,都會重新平衡,對比得到可能處于中間位置的一個值放到最頂層,這樣每一次對比就過濾掉一半的數據。同樣查找0006號數據,我們只需要對比兩次就可以了。
缺點:如果我們有1千萬個數據,也會對比很多次,而且會出現樹高的問題,且每插入一個值將進行重平衡,非常的費時。

所以為了解決上述問題,我們引入了B樹

3. B樹

MySQL索引為什么要使用B+樹

我們插入如上圖所示的16個數據,可以看到它把之前的每個節點存一個數據變成了存多個數據,底層存數據段的形式。這就解決了紅黑樹樹高的問題。
缺點:有這樣一種業務場景:我們現在要取出0008 — 0015區間的所有數據。此時我們需要用0008去匹配,然后用0009去匹配一直到0015。這樣每一個數據都走一遍索引去搜索非常的費時間。
所以為了解決B樹的這個問題,引入了B+樹。

4. B+樹

MySQL索引為什么要使用B+樹
可以看到同樣的15個數據,從數據結構上面看為什么B+樹要比B樹復雜些呢?
答:這是B樹與B+樹的區別:B樹的具體數據保存在自身所在位置的節點中,B+樹的具體數據保存在葉子節點(最底層)上面。
與B樹對比的話,B+樹多了一個鏈表。這樣我們取區間數據的時候可以不用每一個數據都走一遍索引。降低了空間復雜度。

這就是為什么MySQL要使用B+數作為索引的底層數據結構。

上述所有的圖形都是通過以下網站繪制:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

beylze編程學院,一個分享編程知識和seo優化知識的網站。跟著beylze一起學習,每天都有進步。

通俗易懂,深入淺出,一篇文章只講一個知識點。

文章不深奧,不需要鉆研,在公交、在地鐵、在廁所都可以閱讀,隨時隨地漲姿勢。

文章不涉及代碼,不燒腦細胞,人人都可以學習。

當你決定關注beylze(公眾號:beylze),你已然超越了90%的其他從業者!

相關文章

国产亚洲欧美日韩