為什麼MongoDB使用B-Tree，Mysql使用B+Tree ?

推薦學習

除了 B+ 樹，你可能還聽說過 B 樹、 B- 樹，實際上， B- 樹就是 B 樹，英文翻譯都是 B-Tree ，這裡的 “-” 並不是相對 B+ 樹中的 “+” ，而只是一個連接符。而 B 樹實際上是低級版的B+ 樹，或者說 B+ 樹是 B 樹的改進版。

B+ tree

B+ tree 實際上是一顆m叉平衡查找樹(不是二叉樹)

平衡查找樹定義：樹中任意一個節點的左右子樹的高度相差不能大於 1

<code>/**
* 這是B+樹非葉子節點的定義。
*
* 假設keywords=[3, 5, 8, 10]
* 4個鍵值將數據分為5個區間：(-INF,3), [3,5), [5,8), [8,10), [10,INF)
* 5個區間分別對應：children[0]...children[4]
*
* m值是事先計算得到的，計算的依據是讓所有信息的大小正好等於頁的大小：
* PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小]
*/
public class BPlusTreeNode {
  // 5叉樹
  public static int m = 5;

  // 鍵值，用來劃分數據區間
  public int[] keywords = new int[m-1];

  // 保存子節點指針
  public BPlusTreeNode[] children = new BPlusTreeNode[m];
}
/**
* 這是B+樹中葉子節點的定義。
*
* B+樹中的葉子節點跟內部結點是不一樣的,
* 葉子節點存儲的是值，而非區間。
* 這個定義裡，每個葉子節點存儲3個數據行的鍵值及地址信息。
*
* k值是事先計算得到的，計算的依據是讓所有信息的大小正好等於頁的大小：
* PAGE_SIZE = k*4[keyw..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小]
*/
public class BPlusTreeLeafNode {
  public static int k = 3;

  // 數據的鍵值
  public int[] keywords = new int[k];

  // 數據地址
  public long[] dataAddress = new long[k];

  // 這個結點在鏈表中的前驅結點
  public BPlusTreeLeafNode prev;

  // 這個結點在鏈表中的後繼結點 
  public BPlusTreeLeafNode next;
}/<code>

在B+ 樹中，樹中的節點並不存儲數據本身，而是隻是作為索引。除此之外，所有記錄的節點按大小順序存儲在同一層的葉節點中，並且每個葉節點通過指針連接。

總結下,B+樹有以下特點

1. B +樹的每個節點可以包含更多節點，其原因有兩個，其一是降低樹的高度(索引不會全部存儲在內存中,內存中可能撐不住,所以一般都是將索引樹存儲在磁盤中，只是將根節點放到內存中，這樣對每個節點的訪問,實際上就是訪問磁盤,樹的高度就等於每次查詢數據時磁盤 IO 操作的次數),另一種是將數據範圍更改為多個間隔。間隔越大，數據檢索越快(可以想象跳錶)
2. 每個節點不在是存儲一個key,而是存儲多個key
3. 葉節點來存儲數據，而其他節點用於索引
4. 葉子節點通過兩個指針相互鏈接，順序查詢性能更高。

這樣設計還有以下優點：

1. B +樹的非葉子節點僅存儲鍵，佔用很小的空間，因此節點的每一層可以索引的數據範圍要寬得多。換句話說，可以為每個IO操作搜索更多數據
2. 葉子節點成對連接，符合磁盤的預讀特性。例如，葉節點存儲50和55，它們具有指向葉節點60和62的指針。當我們從磁盤讀取對應於50和55的數據時，由於磁盤的預讀特性，我們將順便提一下60和62。讀出相應的數據。這次是順序讀取，而不是磁盤搜索，加快了速度。
3. 支持範圍查詢，局部範圍查詢非常高效，每個節點都可以索引更大，更準確的範圍，這意味著B +樹單磁盤IO信息大於B樹，並且I / O效率更高
4. 由於數據存儲在葉節點層中，並且有指向其他葉節點的指針，因此範圍查詢僅需要遍歷葉節點層，而無需遍歷整個樹。

由於磁盤訪問速度和內存之間存在差距，為了提高效率，應將磁盤I / O最小化。磁盤通常不是嚴格按需讀取的，而是每次都被預讀。磁盤讀取所需的數據後，它將向後讀取內存中的一定長度的數據。這樣做的理論基礎是計算機科學中眾所周知的本地原理：

B-Tree

B-Tree實際上也是一顆m叉平衡查找樹

1. 所有的key值分佈在整個樹中
2. 所有的key值出現在一個節點中
3. 搜索可以在非葉子節點處結束
4. 在完整的關鍵字搜索過程中，性能接近二分搜索。

B樹和B+樹之間的區別

1. B +樹中的非葉子節點不存儲數據，並且存儲在葉節點中的所有數據使得查詢時間複雜度固定為log n。
2. B樹查詢時間的複雜度不是固定的，它與鍵在樹中的位置有關，最好是O（1）。
3. 由於B+樹的葉子節點是通過雙向鏈表鏈接的，所以支持範圍查詢，且效率比B樹高
4. B樹每個節點的鍵和數據是一起的

為什麼MongoDB使用B-Tree,Mysql使用B+Tree ?

B +樹中的非葉子節點不存儲數據，並且存儲在葉節點中的所有數據使得查詢時間複雜度固定為log n。B樹查詢時間複雜度不是固定的，它與鍵在樹中的位置有關，最好是O(1)。

我們已經說過，儘可能少的磁盤IO是提高性能的有效方法。MongoDB是一個聚合數據庫，而B樹恰好是鍵域和數據域的集群。

至於為什麼MongoDB使用B樹而不是B +樹，可以從其設計的角度考慮它。 MongoDB不是傳統的關係數據庫，而是以BSON格式(可以認為是JSON)存儲的nosql。目的是高性能，高可用性和易於擴展。

Mysql是關係型數據庫，最常用的是數據遍歷操作(join)，而MongoDB它的數據更多的是聚合過的數據，不像Mysql那樣表之間的關係那麼強烈,因此MongoDB更多的是單個查詢。

由於Mysql使用B+樹，數據在葉節點上,葉子節點之間又通過雙向鏈表連接,更加有利於數據遍歷，而MongoDB使用B樹,所有節點都有一個數據字段。只要找到指定的索引，就可以對其進行訪問。毫無疑問，單個查詢MongoDB平均查詢速度比Mysql快。

Hash索引

簡而言之，哈希索引使用某種哈希算法將鍵值轉換為新的哈希值。不需要像B +樹那樣從根節點到葉節點逐步搜索。只需要一種哈希算法,就可以立即找到對應的位置，速度非常快。(此處可以想想Java中的HashMap)。

B+樹索引和Hash索引的區別

1. 如果是等價查詢，則哈希索引顯然具有絕對優勢，因為只需一種算法即可找到相應的鍵值；當然，前提是鍵值是唯一的,如果存在hash衝突就必須鏈表遍歷了。
2. 哈希索引不支持範圍查詢(不過改造之後可以,Java中的LinkedHashMap通過鏈表保存了節點的插入順序,那麼也可以使用鏈表將數據的大小順序保存起來)

這樣做雖然支持了範圍查詢但是時間複雜度是O(n),效率比跳錶和B+Tree差

3. 哈希索引無法使用索引排序以及模糊匹配
4. 哈希索引也不支持多列聯合索引的最左邊匹配規則。
5. 鍵值大量衝突的情況下,Hash索引效率極低

作者：think123
原文鏈接：https://juejin.im/post/5ea273f951882573cd41c7a4