B树是-多路平衡树（有序表）
1、根节点至少有两个孩子节点（子节点）
2、每个中间节点都包含k-1个元素和k个孩子，其中m/2=k=m
3、每个叶子节点都包含k-1个元素，其中m/2=k=m
4、所有叶子节点都位于同一层
5、每个节点元素从小到大排列
B-树的阶数m：阶数是人为规定的，没有明确说明的情况下指的是，树中最多元素节点的元素个数加1。
每个节点最多的分支数：非叶根节点至少有2个分支、非根非叶子节点至少有m/2向上取整个分支。
节点内关键字互不相等
建立B-树的过程5阶B-树为例：
1、根据规定的阶数m，插入m-1个关键字，在插入第m个关键字时，节点已满，需要做一个节点拆分动作。将m/2向上取整位置上的关键字，提出作为单独节点。
2、将6关键字，左右两边的关键字，拆分到两个新节点中。
3、继续插入新的关键字，即在B-树中查找位置，插入新关键字4。
4、继续插入，在节点超过阶数时，再次进行节点拆分操作。
向上提出m/2向上取整位置10，关键字到，父节点（未满），其左右关键字拆分到两个新节点。
5、继续插入，节点拆分
6、继续插入，拆分，并触发连锁拆分，得到最终B-树
B-树删除关键字操作删除8、16、15、4分别讨论
删除8关键字、删除叶子节点上的关键字，满足最小节点数规则（m/2=k=m即：[3,5])。叶子节点大于2，则可直接删除。
删除16关键字，删除非根非叶中间节点，用该关键字的右子树一直向左找到其最小关键字或左子树一直向右找到其最大关键字替换该关键字。实际情况是，如果使用左子树最大关键字替换，则不满足叶子节点=2。使用右子树最小关键字替换，则可删除。
删除15关键字，删除叶子节点关键字个数为下限的关键字，采取从其兄弟节点借关键字的方式删除。即父关键字下移，并借用兄弟节点18上移，后再删除15.
删除4关键字，此种情况是，该节点达到要求数目下限，并且其左右兄弟节点也无法被借用，则直接删除该关键字，并和其兄弟节点做一次合并操作即可。
与其右边兄弟节点合并：
此时父节点数目不满足要求，需要继续合并。
与其左兄弟合并结果：
B-树主要用于文件系统及部分数据库索引。如：Mongodb
B+树1、B+树中有n个关键字的节点就有n个分支。B-树中有n个关键字的节点有n-1个分支。
2、B+树中，非根节点中关键字个数的取值范围，(阶数除以2向上取整)m/2-1=n=m，根节点范围2=n=m。B-树对应取值范围：m/2-1=n=m-1，和1=n=m-1
3、在B+树中叶子节点包含信息，且包含全部关键字，叶子节点引出的指针指向记录。
4、在B+树中，所有的非叶子节点仅起到一个索引的作用。即节点中每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含该关键字对应的记录的存储地址；而B-树中每个关键字对应一个记录的存储地址。
5、在B+树中有一个指针P指向关键字最小的叶子节点，所有叶子节点链接成一个线性链表，B-树却没有。
为什么说B+树比B树更适合数据库索引？1、B+树的磁盘IO更低：B+树非叶节点只包含关键字不包含记录，相对B-树更小，同一磁盘中能容纳的节点也更多，一次性读入内存的关键字数量也越多。相对降低IO次数。
2、B+树的查询效率更稳定：非叶节点只包含指向叶子节点的索引，最终查找都要走到叶子节点，任何查找都会走出一条路径长度相同的从根到叶子节点的路，即每个查询的效率相当。
3、B+树所有数据存储在叶子节点，方便扫库，只需扫一遍叶子节点即可。B-树则需要进行一次中序遍历才能完成扫库。
B树在提高了IO性能的同时没有解决元素遍历效率低下的问题。而B+树，叶子节点包含所有关键而且链表指针链接成线性有序链表结构，只需扫一遍叶子节点即可完成整棵树遍历。而数据库中基于范围的查询是非常频繁的，而B-树相比较效率更低。
预览时标签不可点收录于话题#个上一篇下一篇