B树系列解析

• 我最近开了几个专栏，诚信互三！
  ====> |||《算法专栏》：：刷题教程来自网站《代码随想录》。|||
  ====> |||《C++专栏》：：记录我学习C++的经历，看完你一定会有收获。|||
  ====> |||《Linux专栏》：：记录我学习Linux的经历，看完你一定会有收获。|||
  ====> |||《C#专栏》：：记录我复习C#的经历，深度理解，查漏补缺，不定期更新。|||
  ====> |||《计算机网络专栏》：：记录我学习计算机网络，看完你一定会有收获。|||
  ====> |||《mysql数据库》：：记录我学习数据库，看完你一定会有收获。|||

B树的优势

B树系列都擅长外查询，及查询磁盘中的数据，B树都是一棵多叉树，对于二叉搜索树来说，查询到一个结点的时间复杂度位logN，而一颗B树，查询都一个结点的时间复杂的位logM^N，着两者在内存级别时，差别不大，但是在磁盘级别能节约多次磁盘IO的时间，从而大大加快查询的速度。
因此，该数据结构常常用于需要大量进行磁盘IO的情况，如文件系统以及数据库的索引。

B树的结构

B树满足以下几点要求，假设这是一颗M叉树。
1).B树的根结点至少有两个孩子。
2).B树的每个结点要有k个孩子和k-1个关键字，up(M/2)<=k<=M。
3).叶子结点没有孩子只有关键字。
4).B树关键字的左孩子的关键字比当前关键字都小，右孩子关键字比当前关键字大。

B树在设计结构的时候，我们往往会多设计一个关键字结点和孩子结点，这样好判断分裂的情况。

B树的增加

B树插入值时，是插入到叶子结点，此时有两者情况。
1).叶子结点没满，则直接插入。
2).叶子结点满了，则会进行分裂，将结点的关键字的二分之一拷贝到另一个结点，以及其所对应的孩子，同时提取第一个结点的中位数，加入到父节点，让两个结点连接到父节点的中位数下。

更具上述对于B树的插入描述，可知，B树是向右，向上成长的，所以B树天然平衡。

B+树的结构

B+树是B树的新版本，也是mysql中索引使用的数据结构，它相较于B+树存在一些优势。
1).结构更简单，B+树有K个关键字和K个孩子，K[i]号关键字的孩子C[i]比K[i]大，C[i - 1]比K[i]小。
2).B+树的所有插入的值都在叶子结点，叶子结点通过指针相互连接起来。
3).综上，B+树的分支结点存的是索引，而不是值。
4).B+树遍历查询十分方便，所以查询某个范围的值效率高。

B+树也是向右向上生长，所以也天然平衡。

B+树的插入

B+树插入值时，需要先分裂一个结点，插入情况如下。

插入第一个结点，需要先分裂一个，随后每次插入都往叶子结点插入。
如果插入的结点小于叶子结点的最小值，则需要更新父节点的关键字，如果满了，则直接分裂一半关键字和孩子，不需要提取中位数，直接将第二个结点的最小值付给父节点的关键字。

B*树了解

B*树是对B+树的一次优化，以减少B+树的空间浪费。
插入关键字导致结点满了后，将该结点给兄弟结点，如果兄弟结点也满了，则两个结点各自分出1/3给一个新结点。