教育行業(yè)A股IPO第一股（股票代碼 003032）

全國咨詢/投訴熱線：400-618-4000

什么是索引？MySQL索引的底層數據結構

更新時間:2023年04月26日11時33分 來源:傳智教育 瀏覽次數:

好口碑IT培訓

索引(index)是幫助MySQL高效獲取數據的數據結構(有序)。在數據之外，數據庫系統(tǒng)還維護著滿足特定查找算法的數據結構(B+樹)，這些數據結構以某種方式引用(指向)數據，這樣就可以在這些數據結構上實現(xiàn)高級查找算法，這種數據結構就是索引。

MySQL默認使用的索引底層數據結構是B+樹。再聊B+樹之前，我們先聊聊二叉樹和B樹。

二 叉 樹和 B 樹

B-Tree，B樹是一種多叉路衡查找樹，相對于二叉樹，B樹每個節(jié)點可以有多個分支，即多叉。以一顆最大度數(max-degree)為5(5階)的b-tree為例，那這個B樹每個節(jié)點最多存儲4個key。MySQL的默認的存儲引擎InnoDB采用的B+樹的數據結構來存儲索引，選擇B+樹的主要的原因是：第一階數更多，路徑更短，第二個磁盤讀寫代價B+樹更低，非葉子節(jié)點只存儲指針，葉子階段存儲數據，第三是B+樹便于掃庫和區(qū)間查詢，葉子節(jié)點是一個雙向鏈表。

B-Tree

B+Tree是在BTree基礎上的一種優(yōu)化，使其更適合實現(xiàn)外存儲索引結構，InnoDB存儲引擎就是用B+Tree實現(xiàn)其索引結構。

B樹與B+樹的區(qū)別:①：磁盤讀寫代價B+樹更低;②：查詢效率B+樹更加穩(wěn)定;③：B+樹便于掃庫和區(qū)間查詢

第一：在B樹中，非葉子節(jié)點和葉子節(jié)點都會存放數據，而B+樹的所有的數據都會出現(xiàn)在葉子節(jié)點，在查詢的時候，B+樹查找效率更加穩(wěn)定。

第二：在進行范圍查詢的時候，B+樹效率更高，因為B+樹都在葉子節(jié)點存儲，并且葉子節(jié)點是一個雙向鏈表。

0 分享到：
和我們在線交談！