Skip to content

Latest commit

 

History

History
26 lines (22 loc) · 1.77 KB

BTREE和B+TREE的区别.md

File metadata and controls

26 lines (22 loc) · 1.77 KB

在实际应用中,B+树由于其读写性能稳定和叶子节点的顺序链表特性,使得它更适合用于数据库索引。而B树则有时候用于那些需要频繁对数据进行更新的场景。

共同点

  1. 都是多路平衡查找树,有高度平衡的性质。
  2. 节点可以拥有多个子项(children),不仅是两个,因此是多叉的。
  3. 树中的每个节点都是按照键值有序排列的,并且每个节点中的键分隔了其子节点的范围。
  4. 搜索、插入、删除操作的时间复杂度都是O(log n)。

主要区别

  1. 键和数据的存储
    • 在B树中,每个节点都包含键和数据。因此,数据可以在非叶子节点找到。
    • 在B+树中,所有的数据都保留在叶子节点中,并且通常以链表的方式进行连接,非叶子节点只存储键信息。
  2. 叶子节点的性质
    • B树的叶子节点没有特别的标记,它们与内部节点大体相似。
    • B+树的叶子节点通过指针串联成一个链表,方便全范围扫描和顺序访问。
  3. 空间利用率
    • B+树的内部节点不存储数据,所以能存更多的键,这样树可以更矮更胖,减少IO次数。
    • B树的内部节点存储数据,可能导致树更高一些,增加IO次数。
  4. 搜索效率
    • B树中,搜索可以在找到第一个匹配的键时停止,无论它在内部节点还是叶子节点。
    • B+树中,搜索总是会走到叶子节点,因为数据只能在叶子节点找到。
  5. 复制和维护
    • B+树由于所有数据都存在于叶子节点且通过指针连接,所以更适合做全库扫描。
    • B树在更新数据时,修改更简单,因为数据可以直接在找到的节点中修改。