B树和B+树区别

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等排序操作，这对于一些查询和分析操作非常有用。