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

創(chuàng)新互聯(lián)專注于興安盟烏蘭浩特網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗。 熱誠為您提供興安盟烏蘭浩特營銷型網(wǎng)站建設(shè)，興安盟烏蘭浩特網(wǎng)站制作、興安盟烏蘭浩特網(wǎng)頁設(shè)計、興安盟烏蘭浩特網(wǎng)站官網(wǎng)定制、微信小程序開發(fā)服務(wù)，打造興安盟烏蘭浩特網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供興安盟烏蘭浩特網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。

一、前言

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

我記得剛剛學(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ù)據(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é)點只有兩個孩子節(jié)點，如果一張表的數(shù)據(jù)量特別大，整棵樹的高度也會隨之上升。一個千萬級別的表如果用平衡二叉樹作為索引的話，樹高將會達(dá)到二十多層。這也就意味著做一次查詢需要二十多次磁盤io，這是一個不小的開銷。

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

B樹和B+樹

答案就是B樹。上面我們說到了平衡二叉樹的瓶頸在于一個節(jié)點只有兩個孩子節(jié)點，而B樹一個節(jié)點可以存放N個孩子節(jié)點，這就完美解決了樹高的問題，我們可以把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)點一：

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

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

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

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

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

改進(jìn)點二：

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

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

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

以上就是MySQL的常用引擎為什么默認(rèn)使用B+樹作為索引，小編相信有部分知識點可能是我們?nèi)粘９ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學(xué)到更多知識。更多詳情敬請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

文章名稱：MySQL的常用引擎為什么默認(rèn)使用B+樹作為索引
文章分享：http://aaarwkj.com/article12/pdeegc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、虛擬主機、服務(wù)器托管、關(guān)鍵詞優(yōu)化、App開發(fā)、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)