共計 2259 個字符，預(yù)計需要花費(fèi) 6 分鐘才能閱讀完成。

本篇文章給大家分享的是有關(guān) MySQL 的常用引擎為什么默認(rèn)使用 B + 樹作為索引，丸趣 TV 小編覺得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著丸趣 TV 小編一起來看看吧。

一、前言

為了講清楚這個問題，阿粉先帶大家了解一下什么是索引。

我記得剛剛學(xué)習(xí)數(shù)據(jù)庫的時候，老師喜歡用書本的目錄來類比數(shù)據(jù)庫的索引，并告訴我們索引能夠像目錄一樣，讓我們更快地找到想要找到的數(shù)據(jù)。

如果是第一次接觸索引，這個比喻能夠讓我們有一個直觀的印象。但是當(dāng)深入去學(xué)習(xí)索引的時候，我們不能繼續(xù)持有索引即目錄的思想，我們要跳出來去思考索引的本質(zhì)是什么。

二、索引的本質(zhì)

在沒有索引的情況下，我們查找數(shù)據(jù)只能按照從頭到尾的順序逐行查找，每查找一行數(shù)據(jù)，意味著我們要到到磁盤相應(yīng)的位置去讀取一條數(shù)據(jù)。

如果把查詢一條數(shù)據(jù)分為到磁盤中查詢和比對查詢條件兩步的話，到磁盤中查詢的時間會遠(yuǎn)遠(yuǎn)大于比對查詢條件的時間，這意味著在一次查詢中，磁盤 io 占用了大部分的時間。更進(jìn)一步地說，一次查詢的效率取絕于磁盤 io 的次數(shù)，如果我們能夠在一次查詢中盡可能地降低磁盤 io 的次數(shù)，那么我們就能加快查詢的速度。

在知道了減少磁盤 io 能加快查詢速度后，我們就要聚焦于如何減少磁盤 io。如果按照原表逐行查詢的話，n 條數(shù)據(jù)就要查詢 n 次，也就是 O(N) 的時間復(fù)雜度，為了減少磁盤 io 的次數(shù)，我們必須用一種查詢時間復(fù)雜度更低的數(shù)據(jù)結(jié)構(gòu)來保存數(shù)據(jù)。

這種查詢時間復(fù)雜度低的數(shù)據(jù)結(jié)構(gòu)，我們稱之為索引。所以通俗來說，索引其實(shí)就是某種數(shù)據(jù)結(jié)構(gòu)，能充當(dāng)索引的數(shù)據(jù)結(jié)構(gòu)是多種多樣的。

三、索引的選擇

既然索引是一種便于查詢的數(shù)據(jù)結(jié)構(gòu)，如果大家對數(shù)據(jù)結(jié)構(gòu)有一定了解的話，大概率會首選樹型結(jié)構(gòu)。畢竟樹型結(jié)構(gòu)普遍有著 O(logN) 的查詢時間復(fù)雜度，而且插入刪除數(shù)據(jù)的性能也比較平均。(可能你會說數(shù)組，哈希表的查詢速度也很高啊，這個后面也會分析)

雖然我們都已經(jīng)知道 Mysql 中最常用的引擎像 InnoDB 和 MyISAM，最終都選擇了 B + 樹作為索引，但是這里我還是打算從最常見的二叉樹開始講起，推導(dǎo)一下為什么最終選擇了 B + 樹作為索引，并比較一下幾種樹型結(jié)構(gòu)在充當(dāng)索引時的優(yōu)劣。

二叉樹

最普通的二叉樹的問題在于他不能保證 O(logN) 的查詢時間復(fù)雜度，我們看下面的圖：

由于插入的元素逐漸增大，元素始終在右邊進(jìn)行插入，好好的一棵二叉樹最終變成了一條“鏈表”。在這種極端的情況下，二叉樹的查詢時間復(fù)雜度不再是 O(logN)，而是退化為 O(N)，這樣顯然不符合索引的要求。

平衡二叉樹 (紅黑樹)

像紅黑樹這樣的平衡二叉樹，無論如何插入元素，他都可以通過一些旋轉(zhuǎn)的方法調(diào)整樹的高度，使得整棵樹的查詢效率維持在 O(logN)，如下圖所示：

這么來說他已經(jīng)符合了成為索引的必備條件，但是最終沒有選擇他作為索引說明還有不足的地方。仔細(xì)看看可以發(fā)現(xiàn)平衡二叉樹的每個節(jié)點(diǎn)只有兩個孩子節(jié)點(diǎn)，如果一張表的數(shù)據(jù)量特別大，整棵樹的高度也會隨之上升。一個千萬級別的表如果用平衡二叉樹作為索引的話，樹高將會達(dá)到二十多層。這也就意味著做一次查詢需要二十多次磁盤 io，這是一個不小的開銷。

那么有沒有能在大數(shù)據(jù)量的情況下，還能保持一個較小樹高的樹型結(jié)構(gòu)呢?

B 樹和 B + 樹

答案就是 B 樹。上面我們說到了平衡二叉樹的瓶頸在于一個節(jié)點(diǎn)只有兩個孩子節(jié)點(diǎn)，而 B 樹一個節(jié)點(diǎn)可以存放 N 個孩子節(jié)點(diǎn)，這就完美解決了樹高的問題，我們可以把 B 樹稱為平衡多叉樹，B 樹作為索引如下圖所示：

圖片來源網(wǎng)絡(luò)

但是以 B 樹的結(jié)構(gòu)作為索引仍有可以優(yōu)化的地方，我們先看看最終的 B + 樹，再仔細(xì)分析 B + 樹在 B 樹的基礎(chǔ)上作了哪些改進(jìn)，為什么 B + 樹最終能夠勝任索引的工作：

圖片來源網(wǎng)絡(luò)

從圖片中可以看到 B + 樹同樣是一棵多差平衡樹，和 B 樹一樣很好地解決了樹高的問題。

改進(jìn)點(diǎn)一：

但仔細(xì)看可以發(fā)現(xiàn)，B 樹的節(jié)點(diǎn)中既存儲索引，也存儲表對應(yīng)的數(shù)據(jù); 而 B + 樹的非葉子節(jié)點(diǎn)是不存儲數(shù)據(jù)的，只存儲索引，數(shù)據(jù)全部存儲在葉子節(jié)點(diǎn)上。

為什么要做這樣的改進(jìn)? 我們做一次算術(shù)就知道了。

假設(shè)樹高為 2，主鍵 ID 為 bigint 類型，長度為 8 字節(jié)，節(jié)點(diǎn)指針為 6 字節(jié)，一行數(shù)據(jù)記錄的大小為 1k，一次 io 操作能獲得一頁 16k 的數(shù)據(jù)。

在索引為 B + 樹的情況下，根節(jié)點(diǎn)能存儲：16k / (6 + 8) = 1170 條索引指針; 到了第一層，一共能指向 1170 * 1170 =  1368900 條索引指針; 到了最底一層葉子節(jié)點(diǎn)，一個節(jié)點(diǎn)能存儲 16k / 1k = 16 條記錄，一共能存儲 1170 * 1170 * 16 =  21902400 條記錄

在 B 樹的情況下，由于非葉子節(jié)點(diǎn)使用了大量空間存儲數(shù)據(jù)，存放的索引指針肯定就少，最終整棵樹如果想要存儲和 B + 樹一樣多的數(shù)據(jù)就必須要增加樹高，這樣一來就增加了磁盤 io，所以說 B + 樹作為索引的性能比 B 樹高。

改進(jìn)點(diǎn)二：

葉子節(jié)點(diǎn)之間使用指針連接，提高區(qū)間訪問效率。如果我們要進(jìn)行范圍查詢，可以輕松通過 B + 樹葉子節(jié)點(diǎn)之間的指針進(jìn)行遍歷，減少了不必要的磁盤 io。

看到這里，相信大家對為什么 Mysql 的常用引擎都默認(rèn)使用 B + 樹作為索引已經(jīng)有了初步的認(rèn)知。我們只要牢記一點(diǎn)：索引是為了減少磁盤 io 提高查詢性能而存在的。

而數(shù)組雖然查詢的效率高，但是增加和刪除的效率低，由于記錄在增加和刪除的時候索引也得跟著維護(hù)，這會導(dǎo)致大數(shù)據(jù)量的情況下，增加或刪除一條記錄效率較低。

以上就是 MySQL 的常用引擎為什么默認(rèn)使用 B + 樹作為索引，丸趣 TV 小編相信有部分知識點(diǎn)可能是我們?nèi)粘９ぷ鲿姷交蛴玫降摹ＯＭ隳芡ㄟ^這篇文章學(xué)到更多知識。更多詳情敬請關(guān)注丸趣 TV 行業(yè)資訊頻道。