###### tags: `Index研究`
# 各種樹

### Binary Search Tree

### B-tree


1. 每個節點(包括根節點)最多擁有m個子樹
2. 根節點至少有2個子樹()
3. 分支節點至少擁有m or 2顆子樹（除根節點和葉子節點外都是分支節點）
4. 所有葉子節點都在同一層、每個節點最多可以有m-1個key，並且以升序排列
5. B樹查詢時間的複雜度不是固定的，它與鍵在樹中的位置有關，最好是O1）。
### B+tree
1. 每個葉子節點都帶有指向下一個節點的指針，形成有序鏈表，加速範圍查詢
2. 只有葉子節點帶數據，父節點只帶關鍵字與指針，單一節點更省空間，讓查詢 I/O 變小
3. 所有的葉子節點都在同一層
4. 所有數據都存在葉節點使得查詢時間複雜度固定為O(log n)
5. B+樹的葉子節點是通過雙向鍊表連結的，所以支持範圍查詢，且效率比B樹高

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

MongoDB 作為面向文檔的數據庫，與數據之間的關係相比，它更看重以文檔為中心的組織方式，所以選擇了查詢單個文檔性能較好的B樹，這個選擇對遍歷數據的查詢也可以保證可以接受的時延。

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

{%hackmd theme-dark %}