B樹和B+樹的區別

B樹

B樹被稱為平衡樹，在B樹中，一個節點可以有兩個以上的子節點。B樹的高度為log M N。在B樹中，數據按照特定的順序排序，最小值在左側，最大值在右側。

B樹是一種平衡的多分樹，通常我們說m階的B樹，它必須滿足如下條件：

• 每個節點最多只有m個子節點。
• 每個非葉子節點（除了根）具有至少? m/2?子節點。
• 如果根不是葉節點，則根至少有兩個子節點。
• 具有k個子節點的非葉節點包含k -1個鍵。
• 所有葉子都出現在同一水平，沒有任何信息（高度一致）。

B+樹

B+樹（B+ Tree）是一種常用于數據庫索引和文件系統中的平衡樹數據結構，它具有優秀的查找性能和范圍查詢性能.

B樹和B+樹的區別

1. 節點結構：
   • B樹：B樹的每個節點既可以包含數據，也可以包含子節點的指針。葉子節點和內部節點的結構相似，都可以存儲數據。
   • B+樹：B+樹的內部節點只包含鍵值和子節點的指針，而數據只存在于葉子節點中。內部節點主要用于索引和導航。
2. 葉子節點連接：
   • B樹：B樹的葉子節點之間沒有特殊連接，每個葉子節點獨立存儲數據。
   • B+樹：B+樹的葉子節點通過鏈表連接，形成有序的雙向鏈表。這種結構有利于范圍查詢和順序遍歷。

適用場景

• B樹：適用于文件系統等需要隨機訪問的場景，對于范圍查詢性能較差。
• B+樹：適用于數據庫索引等需要范圍查詢和有序遍歷的場景，對于范圍查詢性能優越。

為什么說B+樹比B樹更適合數據庫索引？

1）B+樹的磁盤讀寫代價更低

B+樹的內部結點并沒有指向關鍵字具體信息的指針。因此其內部結點相對B 樹更小。如果把所有同一內部結點的關鍵字存放在同一盤塊中，那么盤塊所能容納的關鍵字數量也越多。一次性讀入內存中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了；

2）B+樹查詢效率更加穩定

由于非終結點并不是最終指向文件內容的結點，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率相當；

**3）B+樹便于范圍查詢（**最重要的原因，范圍查找是數據庫的常態）

B樹在提高了IO性能的同時并沒有解決元素遍歷的我效率低下的問題，正是為了解決這個問題，B+樹應用而生。B+樹只需要去遍歷葉子節點就可以實現整棵樹的遍歷。而且在數據庫中基于范圍的查詢是非常頻繁的，而B樹不支持這樣的操作或者說效率太低。

4）支持排序

B+樹的有序性能夠支持ORDER BY等排序操作，這對于一些查詢和分析操作非常有用。