歡迎光臨
每天分享高質量文章

淺談MySQL的B樹索引與索引優化

作者:猴子007

鏈接:https://monkeysayhi.github.io/2018/03/06/淺談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)之間,大大降低樹高。


再次強調:

不要糾結於時間複雜度,與單純的演算法不同,磁盤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 / 8 = 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中,資料行通常非常大,儲存資料行將減少頁面中的子樹個數,m減小樹高增大。假設資料行占用200B,可忽略組織B樹的指標,則新的m = 4 * 1024 / 200 = 20.48 ~= 21,深度最大 log(21/2)(10^7) ~= 7。增加了一倍以上的IO,不考慮。


方案2中,節點增加了一個欄位。假設是4B的指標,則新的m = 4 * 1024 / 12 = 341.33 ~= 341,深度最大 log(341/2)(10^7) = 3.14 ~= 4。與3差別不大,可以考慮。

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


問題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+樹。即:


主要變動如上所述:


  • 修改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條記錄。


參考:

  • 從B樹、B+樹、B*樹談到R 樹

  • MySQL索引原理及慢查詢優化


●編號408,輸入編號直達本文

●輸入m獲取文章目錄

推薦↓↓↓

 

Web開發

更多推薦18個技術類微信公眾號

涵蓋:程式人生、演算法與資料結構、黑客技術與網絡安全、大資料技術、前端開發、Java、Python、Web開發、安卓開發、iOS開發、C/C++、.NET、Linux、資料庫、運維等。

赞(0)

分享創造快樂