B树和B+树的区别

原文链接：B树和B+树的区别
发布时间：2021-11-25 08:15:19

文章目录

B树

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
```cpp
class BTreeNode 
{ 
 int *keys; // 存储关键字的数组
 int t;  // 最小度 (定义一个结点包含关键字的个数 t-1 <= num <= 2t -1">"> 
 BTreeNode **C; // 存储孩子结点指针的数组
 int n;  // 记录当前结点包含的关键字的个数
 bool leaf; // 叶子结点的一个标记，如果是叶子结点则为true,否则false
public: 
 BTreeNode(int _t, bool _leaf);

 // 
 void traverse(); 

 // 查找一个关键字
 BTreeNode *search(int k); // 如果没有出现，则返回 NULL

// 设置友元，以便访问BTreeNode类中的私有成员
friend class BTree; 
};

几个特点：

  • 每个节点其实是一个数组，数组的长度是有限制的。
  • 子节点也用一个数组存储，一个节点的子节点节点比数组长度多1。
  • 每个节点都保存数据。
  • 查询次数不稳定，上图中最好的情况是1次，最坏的情况是3次。

参考资料： https://zhuanlan.zhihu.com/p/146252512

B+树

特点：

  • 非叶子节点，不存储数据，也可以理解为控制节点。
  • 叶子节点存储数据，可以看到非叶子节点的key在叶子节点中都存在，比如15，59。
  • 查询次数稳定，IO次数就是树的高度，上图中是3吃次，必须从根节点查到叶节点。
  • 每个子节点之间用指针相连，其实连起来是一个双向链表，区间查询时，只需要查询一次，然后沿着链表遍历就能得到所有数据。

参考资料 https://zhuanlan.zhihu.com/p/149287061

比较

  • 如果是等值查询，平均效率一样。
  • 如果是区间查询，B数据效率降低，B+依然能保持同样的效率。
  • 最大的区别就是B+叶节点连接起来形成了双向链表。

疑问

每个子节点内部的数据一定是有序的吗？

我们知道B+树用于数据库的索引，每个叶节点就是一页数据，在物理上是顺序存储的，难道主键也是顺序的？

是的。

这就要求，主键一定要自动递增的，这就保证了数据的物理顺序与逻辑顺序一致。

进入叶节点后，查询的复杂度是怎么样的？

由于每次读取一页数据放到内存，可以用数组保存起来，使用二分查找，效率很高，这部分时间可以忽略。

“>