b树、b+树原理

首先，b树和b-树是一种东西，不存在什么“b减树”。
“B-tree，B即Balanced，平衡的意思。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解，可能会以为B-树是一种树，而B树又是另一种树。而事实上是，B-tree就是指的B树。特此说明。”

b树

概述：
b-树是一种多叉平衡查找树，一个结点可以存放多个关键字（从小到大排序），每个关键字有左右两个指针分别指向子节点，左子树中的所有关键字小于它，右子树中的所有关键字大于它。

对于一个m阶b树需要满足以下条件：

• 树中的节点最多可以有m个子节点；且M>2
• 每个内部节点（非叶和非根）的子节点数目[(M/2)(向上舍入), M]，根的子节点数目[2, M]
• 具有k个子节点的非叶节点应具有k-1键（这一点可以推出，每个结点存放至少M/2-1（取上整）和至多M-1个关键字）
• 所有叶子结点位于同一层
• (大小关系)非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树。简要理解就是，左指针指向小的，右指针指向大的。

下图中的左右白色长方形，就分别代表左右指针，叶子节点的指针为空

b树的构建，其实是一个不断插入结点并根据以上条件调整结构的过程。具体过程此处不再赘述，可以简略看一下这一篇文章，The Difference Between B-trees and B+trees。

b树的查找。简要来说，搜索当前结点的所有Key，找到第一个大于等于target的key，如果key==target就可以返回value，否则说明要去查找子节点。如果当前结点是叶子结点，没有子节点，则查找失败，返回null。否则递归查找第i个子节点。
注意，下面的图中，再单个结点的搜索用的是线性查找，可以使用二分查找进一步提高效率。

Search Algorithm

时间复杂度
B树查找的时间复杂度为O(Log2-N)，N为关键字总数。具体可以参考Best case and worst case heights与二叉树学习笔记之B树、B+树、B*树。
思路是：
B-树上的查找有两个基本步骤：
1.在B-树中查找结点，该查找涉及读盘DiskRead操作，属外查找；
2.在结点内查找，该查找属内查找。
查找操作的时间为：
1.外查找的读盘次数不超过树高h，故其时间是O(h)；
2.内查找中，每个结点内的关键字数目keynum<= m - 1(m是B-树的阶数)，如果算二分查找，时间是O(log2 m)

b+树

b+树是b树最著名的版本。具有两个b树不具备的特征：

• 叶子结点使用双向指针相互连接

• 数据仅存储在叶节点上。内部节点仅持有key并充当一种路由作用

  
  

b+树的插入、查找、删除等操作，具体可以看B+-trees。这里简要提一下它的查找操作，由于b+树的具体数据都储存在叶子结点，它的查找过程必须从根节点一直查到叶子。具体算法过程为：

b+树的两个特有特征，使得它相比于b树，更加适合实际应用中操作系统的文件索引和数据库索引。

• 更适合范围查询
  对于范围查询，只需要精确查找到范围中最小的key，然后跟着双指针直到查找到了最大的key
• B+-tree的磁盘读写代价更低
  B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。
  如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。
  一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
  举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。
  一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
• B+-tree的查询效率更加稳定
  由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
• B+树支持存储重复数据，且由于数据都存储在叶子结点，更加容易进行删除操作

参考

https://www.baeldung.com/cs/b-trees-vs-btrees
https://www.cnblogs.com/myseries/p/12532919.html
https://blog.csdn.net/weixin_42462202/article/details/104335419