B-Tree 的定義

這一部分引用算導的定義方法~

一顆 B-Tree T 具有以下性質，

• 每個結點 x 有以下屬性：
• x.n，表示存儲在結點 x 中的關鍵字個數
• x.n 個關鍵字本身非降序存放
• x.leaf 表示 x 是否為葉子節點
• 內部結點包含 x.n+1 個指針指向它的孩子
• 每個葉子結點具有相同的深度，即樹的高度?
• 每個結點中的關鍵字個數有上界和下界，這裡使用 B-Tree 的最小度即 t 來表示，?
• 除了根結點和葉子結點外，每個結點的孩子個數為 ?
• 除了根結點和葉子結點外，每個結點的關鍵字個數為?
• B+Tree 中非葉子結點的孩子個數和關鍵字個數相同

B-Tree vs B+Tree

看完圖，來總結一下~

B-Tree，

• 每個結點上都有對應數據的存儲
• 每個關鍵字出現且僅在一個結點上出現
• 搜索可能在非葉子結點結束

B+Tree，

• 非葉子結點不存儲數據
• 葉子結點增加了一個雙向鏈表，所以從圖中也可以看出，葉子結點上包含了所有關鍵字

B+Tree 的優勢，

• 由於非葉子結點不存儲實際的數據，所以內存中存儲更多的關鍵字，也就是說單次磁碟 IO 信息量會大於 B-Tree
• 葉子結點增加了順序鏈表，更適合區間查詢

Why B-Tree

事實上，紅黑樹也可以用作索引，為什麼 MySQL 中使用的是 B/B+ Tree 來實現索引嘞。因為 MySQL 是基於磁碟的資料庫，索引的查找過程勢必會涉及到磁碟 IO，所以索引性能的兩個關鍵點就是，

• 磁碟 IO 的次數
• CPU 計算速度

所以，在設計索引的時候就要盡量減少磁碟 IO 的次數，而 MySQL 將記錄按照頁的方式進行管理，B-Tree 每次新建結點的時候，直接申請一個頁的空間，這樣就保證了一個結點物理上也存儲在一個頁里，並且計算機存儲分配都是按頁對齊，所以就實現了一個結點只需要一次 IO。在樹中一次檢索最多需要 h - 1 次 IO，因為根結點常駐內存，B-Tree 因為可以有很多結點個數，所以 h 很小，而結點的個數與頁的大小相關，同樣的數據，紅黑樹的 h 明顯要深很多，所以通常都是用 B/B+Tree 作為索引結構。

B-Tree 的漸進時間複雜度為，這裡記 N 為關鍵字個數，d 為內結點出度的 1/2，?

紅黑樹的漸進時間複雜度為， ?

所以，為什麼 MySQL 使用 B/B+Tree 來實現索引也就不言而喻啦。

B-Tree 的操作

這裡針對 B-Tree 的一些操作就不給出圖示了，因為算導中已經給出偽代碼以及非常詳細的圖示啦~只做一個簡單總結，

• 插入關鍵字：先找到關鍵字應該插入的葉子結點，如果結點是滿的，即關鍵字個數為 ?，此時應該根據這個葉子結點中的關鍵字的中間的關鍵字進行分裂，中間的關鍵字會被上移到該節點的父節點中，如果父節點也是滿的，那麼重複上述操作，直到根結點為止，如果到根結點，那麼就說明高度增加了一層
• 刪除關鍵字：刪除關鍵字要比插入關鍵字複雜一些，因為刪除的不只是葉子結點，還可以是內結點，這時候我們就需要考慮如何安置內結點的孩子們，並且還要保證刪除後的 B-Tree 符合要求，所以刪除關鍵字分幾種情況，
• 如果 k 在結點 x 中，且 x 為葉子結點，那麼直接從 x 中刪除 k 即可
• 如果 x 中前於 k 的結點 u1 中的關鍵字個數為 t，那麼找到 u1 中最大的關鍵字 key，刪除 u1 中的 key，並在 x 中用 key 代替 k
• 如果 x 中前於 k 的節點 u1 中的關鍵字個數小於 t，那麼找到 x 中後於 k 的結點 u2，如果 u2 中的關鍵字個數為 t，那麼找到 u2 中最小的關鍵字 key，刪除 u2 中的 key，並在 x 中用 key 代替 k
• 如果前後兩個節點的關鍵字個數都是 t-1，那麼合併 u1 和 u2，並在 x 中刪除 k，將 x 中的指針指向新的結點
• 如果 k 不在當前的內結點中，那麼找到 k 所在的內結點後，執行上述操作即可

B-Tree 索引

以 B-Tree 為結構的索引是最常見的索引類型，比如 InnoDB 和 MyISAM 都是以 B-Tree 為索引結構的索引，事實上是以 B+ Tree 為索引結構，B-Tree 和 B+Tree 區別在於，B+ Tree 在葉子節點上增加了順序訪問指針，方便葉子節點的範圍遍歷。這裡主要介紹一下 InnoDB 和 MyISAM 兩種不同的索引。

InnoDB

InnoDB 支持聚簇索引，聚簇索引和非聚簇索引嚴格來說不是一種索引，而是一種數據存儲方式，這個名字跟它本身的存儲方式有關係，「聚簇「表示數據行和相鄰的鍵值存儲在一起，簡單的說，就是葉子節點中存儲的實際是真實的數據。InnoDB 通過主鍵聚集數據，所以一個表只能有一個聚簇索引，且必須有主鍵，如果沒有定義主鍵，且不存在非空索引可以代替，InnoDB 會隱式定義一個主鍵作為聚簇索引。

聚簇索引的二級索引存儲的不是指向行的物理位置的指針，而是行的主鍵值，所以如果通過二級索引查找行，需要找到二級索引的葉子結點獲得對應的主鍵值，然後再去查找對應的行。對於 InnoDB，自適應哈希索引可以減少這樣的重複工作。

MyISAM

MyISAM 支持非聚簇索引，和 InnoDB 的區別在於，葉子結點上存的是指向對應行的物理地址，也就是說索引和數據實際是分開存儲的。

MyISAM 採用了前綴壓縮技術，從而使得更多索引可以放入到內存中，默認只壓縮字元串，但是通過參數設置也可以對整數做壓縮。壓縮方法為，完整保存索引塊中的第一個IE之，然後將其他值和第一個值進行比較得到相同前綴的位元組數和剩餘的不同後綴部分，把這部分存儲起來即可。例如，索引塊中的第一個值是「perform」，第二個值是「performance」，那麼第二個值的前綴壓縮後存儲的是類似「7，ance」這樣的形式。MyISAM 對行指針也採用類似的前綴壓縮方式。

壓縮可以使索引使用更少的空間，在某種程度上性能有所提升，但是代價是某些操作可能更慢。因為每個值的壓縮前綴都依賴前面的值，所以 MyISAM 查找時無法在索引塊使用二分查找，只能從頭開始掃描，正序掃描速度還不錯，逆序掃描的話查找某一行的操作平均都需要掃描半個索引塊。對於 CPU 密集型應用，掃描需要隨機查找，所以壓縮索引會使得索引查找慢很多，而對於 I/O 密集型應用，對於某些查詢的優化更明顯。

鎖

InnoDB 使用的是行鎖，所以支持事務，而 MyISAM 使用的是表鎖，不支持事務。

適用範圍

B-Tree 索引適用於區間查詢，因為 B-Tree 存儲後的葉子節點本身就是有序的，並且 B+ Tree 結構還增加了葉子節點的連續順序指針，對於區間查詢來說就更加方便了。

哈希索引

哈希索引是基於哈希表實現的，只有精確匹配索引所有列的查詢才有效。方法是，對所有的索引列計算一個 hash code，hash code 作為索引，在哈希表中保存指向每個數據行的指針。

優點

• 索引本身只存儲 hash code，所以結構很緊湊，並且查找速度很快

限制

• 索引中的 hash code 是順序存儲的，但是 hash code 對應的數據並不是順序的，所以無法用於排序
• 不支持部分索引列匹配查找，因為哈希索引是使用索引列的全部內容來計算 hash code
• 只支持等值比較，不支持範圍查詢
• 如果哈希衝突嚴重時，必須遍歷鏈表中所有行指針
• 哈希衝突嚴重的話，索引維護操作的代價也很高

InnoDB 的自適應哈希索引

首先，請注意，自適應哈希索引對於用戶來說是無感知的，這是一個完全自動、內部的行為，用戶無法控制或者配置，但是可以關閉。

當 InnoDB 注意到某個索引值被使用的非常頻繁時，它會在內存中基於 B-Tree 索引之上再創建一個哈希索引，這樣 B-Tree 也可以具有哈希索引的一些優點，比如快速的哈希查找。

當然如果存儲引擎不支持哈希索引，用戶也可以自定義哈希索引，這樣性能會比較高，缺陷是需要自己維護哈希值，如果採用這種方法，不要使用 SHA1() 和 MD5() 作為哈希函數，因為這兩個是強加密函數，設計目標是最大限度消除衝突，生成的 hash code 是一個非常長的字元串，浪費大量的空間，哈希索引中對於索引的衝突要求沒有那麼高。

索引的優點

• 使用索引可以減少伺服器需要掃描的數據量
• 使用索引可以幫助伺服器避免排序和臨時表
• 使用索引可以將隨機 I/O 變為順序 I/O

但是不是所有情況下，索引都是最好的解決方案，對於非常小的表來說，大部分情況下簡單的全表掃描更高效，對於中到大型表，索引就比較有效，對於特大型的表來說，分區會更加有效。

Reference

B 樹與 B+ 樹

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

《演算法導論》

《高性能 MySQL》