圖解MySQL索引(二)—為什麼使用B+Tree_網頁設計

※推薦評價好的iphone維修中心

擁有專業的維修技術團隊，同時聘請資深iphone手機維修專家，現場說明手機問題，快速修理，沒修好不收錢

失蹤人口回歸，近期換工作一波三折，耽誤了不少時間，從今開始每周更新~

索引是一種支持快速查詢的數據結構，同時索引優化也是後端工程師的必會知識點。各個公司都有所謂的MySQL"軍規"，其實這些所謂的優化和規定，並不是什麼高深的技術，只是要求大家正確建立和使用索引而已。工欲善其事必先利其器，想要正確運用索引，需要了解其底層實現原理，本文將探索關於索引的"是什麼"以及"為什麼"。

MySQL中關於索引的概念有很多，為了避免混淆，在上一篇文章中關於索引在不同維度分類設計到的一些名詞進行了解釋，如輔助索引，唯一索引，覆蓋索引，B+Tree索引…., 牆裂建議不明白的小夥伴可以先去看看圖解MySQL索引(上)—聊聊索引的分類，本文中關於索引類型的各種定義不再複述。

一，磁盤IO問題

1.1 磁盤IO

所謂磁盤IO，簡單來講就是就是將磁盤中的數據讀取到內存或者是從內存寫入磁盤。在系統開發與設計過程中，磁盤IO的瓶頸往往不可忽略，因為這是一個相對比較耗時的操作。

上圖是一個机械硬盤，雖然速度不如SSD，但是由於價格低廉，目前仍是主流的存儲介質。它的IO操作通常需要尋道，旋轉和傳輸三個步驟。

尋道，是指將讀寫磁頭移動到正確的磁道，尋道時間越短，IO操作越快，目前磁盤的平均尋道時間一般在3-15ms左右。

旋轉，是指將盤片旋轉到請求數據所在的扇區，這部分所需要的時間由硬盤的配置所決定。旋轉延遲由磁盤轉速所決定，也就是常說的7200轉和5400轉等。

例如，7200轉是指每分鐘可以旋轉7200圈，那麼旋轉一圈所需要的時間就是60*1000/7200 ≈ 8.33ms，而旋轉延遲通常取旋轉一周時間的1/2，也就是大約4.17ms。

傳輸，磁盤傳輸的速度通常在幾十到上百M每秒，假設速度為20M/s，要傳輸的數據為64kb，則傳輸時間則是 64 / 1024 / 20 * 1000 = 3.125ms。不過目前流行的SSD傳輸速度大幅度提升，SATA Ⅱ可以達到300M/s，傳輸速度往往遠小於前兩步操作所以傳輸時間往往可以忽略不記。

机械硬盤的連續讀寫性能很好，但隨機讀寫性能很差，這主要是因為磁頭移動到正確的磁道上需要時間，隨機讀寫時，磁頭需要不停的移動，時間都浪費在了磁頭尋址上，所以性能不高。

上述過程是對傳統机械磁盤IO延遲的粗略介紹，目的是告訴大家磁盤IO過程是個耗時的過程，內存操作往往與之速度不在同一個數量級。即使是目前比較流行的SSD，想必內存中數據讀取性能也差之千里。

1.2 局部性原理

由於磁盤IO是一個比較耗時的操作，而操作系統在設計時則定義一個空間局部性原則，局部性原理是指CPU訪問存儲器時，無論是存取指令還是存取數據，所訪問的存儲單元都趨於聚集在一個較小的連續區域中。

在操作系統的文件系統中，數據也是按照page劃分的，一般為4k或8k。當計算機訪問一個地址數據時，不僅會加載當前數據所在的數據頁，還會將當前數據頁相鄰的數據頁一同加載到內存。而這個過程實際上只發生了1次磁盤IO，這個理論對於索引的數據結構設計非常有幫助。

二，索引數據結構演進

索引是一種支持快速查找的數據結構，在運用中往往還要求能夠支持順序查詢，而常見的數據結構有很多，比如數組，鏈表，二叉樹，散列表，二叉搜索樹，平衡搜索二叉樹，紅黑樹，跳錶等。僅僅從數據結構那麼為什麼選擇B+Tree呢？

首先對於數組，鏈表這種線性表來說，適合存儲數據，而不是查找數據，同樣，對於普通二叉樹來說，數據存儲沒有特定規律，所以也不適合。

2.1 哈希索引不能滿足業務需求

哈希（Hash）是一種非常快的查找方法，在一般情況下這種查找的時間複雜度為O（1），即一般僅需要一次查找就能定位到數據。在各種編程語言和數據庫中應用廣泛，如Java，Python，Redis中都有使用。

哈希結構在單條數據的等值查詢是性能非常優秀，但是只能用來搜索等值的查詢， 對於範圍查詢，模糊查詢（最左前綴原則）都不支持，所以不能很好的支持業務需求；所以MySQL並沒有顯式支持Hash索引，而是根據數據的訪問頻次和模式自動的為熱點數據頁建立哈希索引，稱之為自適應哈希索引。

並且由於哈希函數的隨機性，Hash索引通常都是隨機的內存訪問，對於緩存不友好，會造成頻繁的磁盤IO。

2.2 二叉搜索樹退化成鏈表

二叉搜索樹，如果左子樹不為空，則左子樹上所有節點均小於根節點，右子樹節點均大於根節點；由其屬性不難看出，這種樹非常適合數據查找。不過有個致命的缺點是二叉搜索樹的樹型取決於數據的輸入順序，極端情況下會退化成鏈表。

2.3 平衡二叉搜索樹過於嚴格

為了解決上述問題，平衡二叉搜索樹就誕生了。在保證數據順序的基礎上，又能維持樹型，保證每個節點的左右子樹高度相差不超過1。

※網頁設計最專業,超強功能平台可客製化

窩窩以「數位行銷」「品牌經營」「網站與應用程式」「印刷品設計」等四大主軸，為每一位客戶客製建立行銷脈絡及洞燭市場先機。

不過由於要維持樹的平衡，在插入數據時可能要進行大量的數據移動。平衡搜索二叉樹過於嚴格的平衡要求，導致幾乎每次插入和刪除節點都會破壞樹的平衡性，使得樹的性能大打折扣。

2.4 紅黑樹高度過高，磁盤IO次數頻繁

有沒有一種數據結構，即能夠快速查找數據，又不需要頻繁的調整以維持平衡呢？這時紅黑樹就閃亮登場了。

紅黑樹和其他二叉搜索樹類似， 都是在進行插入和刪除操作時通過特定操作保持二叉查找樹的性質，從而獲得較高的查找性能。與之不同的是，紅黑樹的平衡性並不像平衡搜索二叉樹一樣嚴格的同時，又能保證在， O(log n) 時間複雜度內做查找和刪除。

紅黑樹通過改變節點的顏色，可以有效減少節點的移動次數，由於紅黑樹的實現比較複雜，本文不再展開，感興趣的小夥伴可以去深入學習。

看似紅黑樹是一種完美的數據結構，能夠勝任索引的工作。但MySQL並未使用其作為索引的實現，主要原因在於紅黑樹的深度過大，數據檢索時造成磁盤IO頻繁，假設一個每個節點存儲在一個page中，樹的高度為10，則每次檢索可能就需要進行10次磁盤IO。

2.5 B-Tree不支持順序查詢

B-Tree是一種自平衡的多叉搜索樹，一個節點可以擁有兩個以上的子節點。適合讀寫相對大的數據塊的存儲系統，例如磁盤。

由於MySQL索引一般都存儲在內存中，如果使用B-Tree作為索引的話，索引和數據存儲在一塊，分佈在各個節點中；而內存資源往往比較寶貴，一定內存的情況下可以存儲的索引數量相對有限，畢竟每條數據的大小一般遠大於索引列的大小，導致內存使用率不高。

數據查詢過程中往往會有順序查詢，而B-Tree和紅黑樹對於順序查詢並不友好。

2.6 為什麼選B+Tree

B+Tree是在B-Tree基礎上演進而來的。與之不同的是B+Tree的數據頁只存儲在恭弘=叶 恭弘子節點中，並且恭弘=叶 恭弘子節點之間通過指針相連，為雙向鏈表結構。

B+Tree的優點可以分為以四個：

1. 充分利用空間局部性原理，適合磁盤存儲。




2. 樹的高度很低，能夠在存儲大量數據情況下，進行較少的磁盤IO【見下文介紹】。




3. 能夠很好支持單值，範圍查詢，有序性查詢。




4. 索引和數據分開存儲，讓更多的索引存儲在內存中。

三，MySQL中索引實現

3.1 巧妙利用B+Tree

MySQL中的數據存儲通常以Page為單位，俗稱數據頁，每個Page對應B+Tree的一個節點。頁是InnoDB磁盤管理的最小單位，默認每個數據頁的大小為16kb，也可以通過參數innodb_page_size將頁的大小設置成其他值。

數據庫的頁大小和操作系統類似，是指存放數據時，每一塊連續區域數據的大小。比如一個1M的數據存放在數據庫中時， 需要大概64個頁來存放（1024=64*16）。如果是在操作系統上安裝的數據庫，最好將數據庫頁大小設置為操作系統頁大小的倍數，才是最佳設置。

3.2 樹的高度-有效減少磁盤IO次數

通常情況下，一張MySQL表中有成千上萬條數據，而磁盤IO次數往往與數的高度成正比。默認情況下一個Page的大小為16kb，由於每個Page中數據通過指針相連，且每個指針大小為6字節。

在工作中，我們通常使用長度為8個字節的bigint類型作為主鍵id的類型。已知，每一條數據都會包含一個6字節的指針（數據頁中每條記錄都有指向下一條記錄的指針，但是沒有指向上一條記錄的指針）；所以一條索引數據大約佔用8+6=14個字節，一個Page中能存儲16 * 1024 / 14 ≈ 1170條索引數據。高度為2的B+Tree大約能存儲1170*16 = 18720條這樣的記錄。同理，高度為3的B+Tree的B+Tree大約能存儲1170 * 1170 * 16 = 21902400，大約兩千萬條數據。 （每個節點大約能存儲1170條記錄，可以理解為此時B+Tree為1170叉樹）

例如，要檢索id=008的數據，則需要進行三次磁盤IO找到對應的數據頁（最多三次，因為Page可能在緩存中），然後在數據頁中進行二分查找，定位到對應的記錄。

四，總結

大家耳熟能詳的B+Tree索引是一種非常優秀的數據結構，也是面試熱點問題。本文從數據結構和磁盤IO兩個方面分析了為什麼使用B+Tree，以及MySQL的InnoDB存儲引擎的索引實現。在筆者面試過程中，被問到MySQL索引時通常也是從底層數據結構特點以及結合磁盤IO兩個角度去分析，屢試不爽。

學習一門技術時，我們不僅要知道其優點更要了解其缺點和瓶頸。在分析MySQL索引的實現時，不妨試試從其他數據結構的缺點入手！在Redis中使用跳錶實現了有序集合Zset，同樣支持高效的順序查詢，對比MySQL索引實現，跳錶能否替換B+Tree？如果不行，是因為什麼呢？

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

※台北網頁設計公司這麼多該如何選擇?

網動是一群專業、熱情、向前行的工作團隊,我們擁有靈活的組織與溝通的能力,能傾聽客戶聲音,激發創意的火花,呈現完美的作品

---

Orignal From: 圖解MySQL索引(二)—為什麼使用B+Tree_網頁設計