B树与B+树最简知识总结与对比

B树：平衡的多路搜索树

B树中所有节点的孩子节点数的最大值称为B树的阶，通常用m表示，m约束了每个节点子树的最大数量(定义)，也约束了子树的最少数量(m/2向上取整)。定义如下

• 每个节点至多有m棵子树(m-1个关键字)。
• 除根节点外所有非叶节点至少有m/2(向上取整)棵子树.
• 所有的叶子节点都出现在同一层，且不携带信息，绝对平衡。
• 所有非叶节点的结构为n,P0,K1,P1,K2,...,Kn,Pn.其中Ki为关键字，Pi为指向子树根节点的指针。且Ki-1<Pi-1(表示所指向子树的所有节点的关键字)<Ki，B树的每个节点既存储数据又存储所用

B树特点

B树的根节点可以常驻内存，其余节点全部存放在磁盘上！

B树每次读入的节点可以包含很多关键字(上限由m决定)，与外存的批量访问的特点相对应。

B树更加关注常系数的优化。常系数的单位为万或者10万。

当m取256时，相比平衡BST的高度，BST在最坏情况下树高(IO次数)降低其1/7,最好情况下树高降低1/8。

B树查找

与BST很类似，只是每个节点都是多个关键字的有序表。B树的查找包含两个基本操操作：1.在B树中找节点(磁盘IO操作)；2.在节点内找关键字(在内存中)

B树插入：上溢然后分裂。

B数的插入(定位+插入)，因插入是使得节点的关键字数量增加，当个数在[m/2-2,m-1]外(b树定义)时，必须对节点进行分裂，分裂的过程等价于在父节点中插入一个关键码，所以，分裂过程可能一直进行到根节点。B树长高的唯一方式：根节点出发生了上溢操作，此时分裂后，根的子树仅为2.

B树的删除：下溢然后合并。

当直接删除后满足B树定义，则ok，否则，然后看兄弟够借，为了保证有序性，具体是通过三角借债的方式完成，最后才是合并。

B+树：范围查询+查询性能稳定

定义

• 所有的关键码都出现在叶子节点上，B+树内部节点只存储索引
• 所有的非叶节点的关键码是下一层相应节点中最大关键码(最小关键码)的拷贝
• 节点的子树个数与关键字个数相同。
• 叶子节点之间通过链表串联在一起

区别

• B+中内结点只作索引使用, 去掉了其中指向data record的指针, 使得每个结点中能够存放更多的key, 因此能有更大的出度. 这有什么用? 这样就意味着存放同样多的key, 树的层高能进一步被压缩, 使得检索的时间更短.、
• Because B trees contain data with each key, frequently accessed nodes can lie closer to the root, and therefore can be accessed more quickly.

https://stackoverflow.com/questions/870218/what-are-the-differences-between-b-trees-and-b-trees

B树与B+树最简知识总结与对比

原文：https://www.cnblogs.com/justisme/p/12853594.html