知識星球作者：猴子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
這個值很難確定，一般需要join的欄位要求是0.1以上，即平均1條掃描10條記錄。
參考：
從B樹、B+樹、B*樹談到R 樹
MySQL索引原理及慢查詢最佳化
●編號408，輸入編號直達本文
●輸入m獲取文章目錄
Web開發
更多推薦《18個技術類微信公眾號》
涵蓋：程式人生、演演算法與資料結構、駭客技術與網路安全、大資料技術、前端開發、Java、Python、Web開發、安卓開發、iOS開發、C/C++、.NET、Linux、資料庫、運維等。
