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

創新互聯專注于興安盟烏蘭浩特網站建設服務及定制，我們擁有豐富的企業做網站經驗。 熱誠為您提供興安盟烏蘭浩特營銷型網站建設，興安盟烏蘭浩特網站制作、興安盟烏蘭浩特網頁設計、興安盟烏蘭浩特網站官網定制、微信小程序開發服務，打造興安盟烏蘭浩特網絡公司原創品牌,更為您提供興安盟烏蘭浩特網站排名全網營銷落地服務。

一、前言

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

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

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

二、索引的本質

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

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

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

這種查詢時間復雜度低的數據結構，我們稱之為索引。所以通俗來說，索引其實就是某種數據結構，能充當索引的數據結構是多種多樣的。

三、索引的選擇

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

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

二叉樹

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

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

平衡二叉樹(紅黑樹)

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

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

那么有沒有能在大數據量的情況下，還能保持一個較小樹高的樹型結構呢?

B樹和B+樹

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

圖片來源網絡

但是以B樹的結構作為索引仍有可以優化的地方，我們先看看最終的B+樹，再仔細分析B+樹在B樹的基礎上作了哪些改進，為什么B+樹最終能夠勝任索引的工作：

圖片來源網絡

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

改進點一：

但仔細看可以發現，B樹的節點中既存儲索引，也存儲表對應的數據;而B+樹的非葉子節點是不存儲數據的，只存儲索引，數據全部存儲在葉子節點上。

為什么要做這樣的改進?我們做一次算術就知道了。

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

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

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

改進點二：

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

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

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

以上就是MySQL的常用引擎為什么默認使用B+樹作為索引，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注創新互聯行業資訊頻道。

文章名稱：MySQL的常用引擎為什么默認使用B+樹作為索引
文章分享：http://vcdvsql.cn/article12/pdeegc.html

成都網站建設公司_創新互聯，為您提供自適應網站、虛擬主機、服務器托管、關鍵詞優化、App開發、網站制作

廣告

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