深度原理學習之–一看就懂的Mysql B+樹索引原理

深度原理學習之–一看就懂的Mysql B+樹索引原理

MySQL的MyISAM、InnoDB引擎默認均使用B+樹索引(查詢時都顯示為“BTREE”),本文討論兩個問題:

  • 為什麼MySQL等主流數據庫選擇B+樹的索引結構?
  • 如何基於索引結構,理解常見的MySQL索引優化思路?

為什麼索引無法全部裝入內存

索引結構的選擇基於這樣一個性質:大數據量時,索引無法全部裝入內存

為什麼索引無法全部裝入內存?假設使用樹結構組織索引,簡單估算一下:

  • 假設單個索引節點12B,1000w個數據行,unique索引,則葉子節點共佔約100MB,整棵樹最多200MB。
  • 假設一行數據佔用200B,則數據共佔約2G。

假設索引存儲在內存中。也就是說,每在物理盤上保存2G的數據,就要佔用200MB的內存,索引:數據的佔用比約為1/10。1/10的佔用比算不算大呢?物理盤比內存廉價的多,以一臺內存16G硬盤1T的服務器為例,如果要存滿1T的硬盤,至少需要100G的內存,遠大於16G。

考慮到一個表上可能有多個索引、聯合索引、數據行佔用更小等情況,實際的佔用比通常大於1/10,某些時候能達到1/3。在基於索引的存儲架構中,索引:數據的佔用比過高,因此,索引無法全部裝入內存

其他結構的問題

由於無法裝入內存,則必然依賴磁盤(或SSD)存儲。而內存的讀寫速度是磁盤的成千上萬倍(與具體實現有關),因此,核心問題是“如何減少磁盤讀寫次數”。

首先不考慮頁表機制,假設每次讀、寫都直接穿透到磁盤,那麼:

  • 線性結構:讀/寫平均O(n)次
  • 二叉搜索樹(BST):讀/寫平均O(log2(n))次;如果樹不平衡,則最差讀/寫O(n)次
  • 自平衡二叉搜索樹(AVL):在BST的基礎上加入了自平衡算法,讀/寫最大O(log2(n))次
  • 紅黑樹(RBT):另一種自平衡的查找樹,讀/寫最大O(log2(n))次

BST、AVL、RBT很好的將讀寫次數從O(n)優化到O(log2(n));其中,AVL和RBT都比BST多了自平衡的功能,將讀寫次數降到最大O(log2(n))。

假設使用自增主鍵,則主鍵本身是有序的,樹結構的讀寫次數能夠優化到樹高,樹高越低讀寫次數越少;自平衡保證了樹結構的穩定。如果想進一步優化,可以引入B樹和B+樹。

B樹解決了什麼問題

很多文章將B樹誤稱為B-(減)樹,這可能是對其英文名“B-Tree”的誤解(更有甚者,將B樹稱為二叉樹或二叉搜索樹)。特別是與B+樹一起講的時候。想當然的認為有B+(加)樹就有B-(減)樹,實際上B+樹的英文名是“B+-Tree”。

如果拋開維護操作,那麼B樹就像一棵“m叉搜索樹”(m是子樹的最大個數),時間複雜度為O(logm(n))。然而,B樹設計了一種高效簡單的維護操作,使B樹的深度維持在約log(ceil(m/2))(n)~logm(n)之間,大大降低樹高

深度原理學習之–一看就懂的Mysql B+樹索引原理

再次強調:

不要糾結於時間複雜度,與單純的算法不同,磁盤IO次數才是更大的影響因素。讀者可以推導看看,B樹與AVL的時間複雜度是相同的,但由於B樹的層數少,磁盤IO次數少,實踐中B樹的性能要優於AVL等二叉樹。

同二叉搜索樹類似,每個節點存儲了多個key和子樹,子樹與key按順序排列。

頁表的目錄是擴展外存+加速磁盤讀寫,一個頁(Page)通常4K(等於磁盤數據塊block的大小,見inode與block的分析),操作系統每次以頁為單位將內容從磁盤加載到內存(以攤分尋道成本),修改頁後,再擇期將該頁寫回磁盤。考慮到頁表的良好性質,可以使每個節點的大小約等於一個頁(使m非常大),這每次加載的一個頁就能完整覆蓋一個節點,以便選擇下一層子樹;對子樹同理。對於頁表來說,AVL(或RBT)相當於1個key+2個子樹的B樹,由於邏輯上相鄰的節點,物理上通常不相鄰,因此,讀入一個4k頁,頁面內絕大部分空間都將是無效數據。

假設key、子樹節點指針均佔用4B,則B樹節點最大m * (4 + 4) = 8m B;頁面大小4KB。則m = 4 * 1024 / 8m = 512,一個512叉的B樹,1000w的數據,深度最大log(512/2)(10^7) = 3.02 ~= 4。對比二叉樹如AVL的深度為log(2)(10^7) = 23.25 ~= 24,相差了5倍以上。震驚!B樹索引深度竟然如此!

另外,B樹對局部性原理非常友好。如果key比較小(比如上面4B的自增key),則除了頁表的加成,緩存還能進一步預讀加速。美滋滋~

B+樹解決了什麼問題

B樹的剩餘問題

然而,如果要實際應用到數據庫的索引中,B樹還有一些問題:

  1. 未定位數據行
  2. 無法處理範圍查詢

問題1

數據表的記錄有多個字段,僅僅定位到主鍵是不夠的,還需要定位到數據行。有3個方案解決:

  1. 直接將key對應的數據行(可能對應多行)存儲子節點中。
  2. 數據行單獨存儲;節點中增加一個字段,定位key對應數據行的位置。
  3. 修改key與子樹的判斷邏輯,使子樹大於等於上一key小於下一key,最終所有訪問都將落於葉子節點;葉子節點中直接存儲數據行或數據行的位置。

方案1直接pass,存儲數據行將減少頁面中的子樹個數,m減小樹高增大。

方案2的節點中增加了一個字段,假設是4B的指針,則新的m = 4 * 1024 / 12m = 341.33 ~= 341,深度最大log(341/2)(10^7) = 3.14 ~= 4。

方案3的節點m與深度不變,但時間複雜度變為穩定的O(logm(n))。

方案3可以考慮。

問題2

實際業務中,範圍查詢的頻率非常高,B樹只能定位到一個索引位置(可能對應多行),很難處理範圍查詢。改動較小的是2個方案:

  1. 不改動;查詢的時候先查到左界,再查到右界,然後DFS(或BFS)遍歷左界、右界之間的節點。
  2. 在“問題1-方案3”的基礎上,由於所有數據行都存儲在葉子節點,B樹的葉子節點本身也是有序的,可以增加一個指針,指向當前葉子節點按主鍵順序的下一葉子節點;查詢時先查到左界,再查到右界,然後從左界到有界線性遍歷。

乍一看感覺方案1比方案2好——時間複雜度和常數項都一樣,方案1還不需要改動。但是別忘了局部性原理,不管節點中存儲的是數據行還是數據行位置,方案2的好處在於,依然可以利用頁表和緩存預讀下一節點的信息。而方案1則面臨節點邏輯相鄰、物理分離的缺點。

引出B+樹

綜上,問題1的方案2與問題2的方案1可整合為一種方案(基於B樹的索引),問題1的方案3與問題2的方案2可整合為一種(基於B+樹的索引)。實際上,數據庫、文件系統有些採用了B樹,有些採用B+樹。

由於某些猴子暫未明白的原因,包括MySQL在內的主流數據庫多選擇了B+樹。即:

深度原理學習之–一看就懂的Mysql B+樹索引原理

主要變動如上所述:

  • 修改key與子樹的組織邏輯,將索引訪問都落到葉子節點
  • 按順序將葉子節點串起來(方便範圍查詢)

B樹和B+樹的增、刪、查過程

B樹的增刪過程暫時可參考從B樹、B+樹、B*樹談到R 樹的“6、B樹的插入、刪除操作”小節,B+樹的增刪同理。此處暫不贅述。

Mysql索引優化

根據B+樹的性質,很容易理解各種常見的MySQL索引優化思路。

暫不考慮不同引擎之間的區別。

優先使用自增key作為主鍵

前面的分析中,假設用4B的自增key作為索引,則m可達到512,層高僅有3。使用自增的key有兩個好處:

  1. 自增key一般為int等整數型,key比較緊湊,這樣m可以非常大,而且索引佔用空間小。最極端的例子,如果使用50B的varchar(包括長度),那麼m = 4 * 1024 / 54m = 75.85 ~= 76,深度最大log(76/2)(10^7) = 4.43 ~= 5,再加上cache缺失、字符串比較的成本,時間成本增加較大。同時,key由4B增長到50B,整棵索引樹的空間佔用增長也是極為恐怖的(如果二級索引使用主鍵定位數據行,則空間增長更加嚴重)。
  2. 自增的性質使得新數據行的插入請求必然落到索引樹的最右側,發生節點分裂的頻率較低,理想情況下,索引樹可以達到“滿”的狀態。索引樹滿,一方面層高更低,一方面刪除節點時發生節點合併的頻率也較低。

優化經歷:

猴子曾使用varchar(100)的列做過主鍵,存儲containerId,過了3、4天100G的數據庫就滿了,DBA小姐姐郵件裡委婉表示了對我的鄙視。。。之後增加了自增列作為主鍵,containerId作為unique的二級索引,時間、空間優化效果相當顯著。

最左前綴匹配

索引可以簡單如一個列(a),也可以複雜如多個列(a, b, c, d),即聯合索引。如果是聯合索引,那麼key也由多個列組成,同時,索引只能用於查找key是否存在(相等),遇到範圍查詢(>、

如有索引(a, b, c, d),查詢條件a = 1 and b = 2 and c > 3 and d = 4,則會在每個節點依次命中a、b、c,無法命中d。也就是最左前綴匹配原則。

=、in自動優化順序

不需要考慮=、in等的順序,mysql會自動優化這些條件的順序,以匹配儘可能多的索引列。

如有索引(a, b, c, d),查詢條件c > 3 and b = 2 and a = 1 and d < 4與a = 1 and c > 3 and b = 2 and d < 4等順序都是可以的,MySQL會自動優化為a = 1 and b = 2 and c > 3 and d < 4,依次命中a、b、c。

索引列不能參與計算

有索引列參與計算的查詢條件對索引不友好(甚至無法使用索引),如from_unixtime(create_time) = '2014-05-29'。

原因很簡單,如何在節點中查找到對應key?如果線性掃描,則每次都需要重新計算,成本太高;如果二分查找,則需要針對from_unixtime方法確定大小關係。

因此,索引列不能參與計算。上述from_unixtime(create_time) = '2014-05-29'語句應該寫成create_time = unix_timestamp('2014-05-29')。

能擴展就不要新建索引

如果已有索引(a),想建立索引(a, b),儘量選擇修改索引(a)為索引(a, b)。

新建索引的成本很容易理解。而基於索引(a)修改為索引(a, b)的話,MySQL可以直接在索引a的B+樹上,經過分裂、合併等修改為索引(a, b)。

不需要建立前綴有包含關係的索引

如果已有索引(a, b),則不需要再建立索引(a),但是如果有必要,則仍然需考慮建立索引(b)。

選擇區分度高的列作索引

很容易理解。如,用性別作索引,那麼索引僅能將1000w行數據劃分為兩部分(如500w男,500w女),索引幾乎無效。

區分度的公式是count(distinct

) / count(*),表示字段不重複的比例,比例越大區分度越好。唯一鍵的區分度是1,而一些狀態、性別字段可能在大數據面前的區分度趨近於0。

這個值很難確定,一般需要join的字段要求是0.1以上,即平均1條掃描10條記錄。

) / count(*),表示字段不重複的比例,比例越大區分度越好。唯一鍵的區分度是1,而一些狀態、性別字段可能在大數據面前的區分度趨近於0。

參考:

  • 從B樹、B+樹、B*樹談到R 樹
  • MySQL索引原理及慢查詢優化


分享到:


相關文章: