B+树和B*树的底层实现原理以及与b-树的区别
B+树和B*树的底层实现原理以及与b-树的区别
B+树
B+树是B-树的变形，也是一种多路平衡树：
- 其定义基本与B-树相同，除了：
- 非叶子节点的子树指针与关键字个数相同
- 非叶子节点的子树指针p[i]，指向关键字值属于(k[i]，k[i+1])的子树
- 为所有叶子节点增加一个链指针
- 所有关键字都在叶子节点出现
B+树的特性：
- 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。
- 不可能在非叶子节点中命中。
- 非叶子节点相当于是叶子节点的索引(稀疏索引)，叶子节点相当于是存储数据的数据层。
- 更适合文件索引系统
B+树在节点访问时间远远超过节点内部访问时间的时候，可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。
B+背后的想法是内部节点可以有在预定范围内的可变数目的子节点。因此，B+树不需要象其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。
查找
查找以典型的方式进行，类似于二叉查找树。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。在节点内部典型的使用是二分查找来确定这个位置。
插入
节点要处于违规状态，它必须包含在可接受范围之外数目的元素。
首先，查找要插入其中的节点的位置。接着把值插入这个节点中。
如果没有节点处于违规状态则处理结束。
如果某个节点有过多元素，则把它分裂为两个节点，每个都有最小数目的元素。在树上递归向上继续这个处理直到到达根节点，如果根节点被分裂，则创建一个新根节点。为了使它工作，元素的最小和最大数目典型的必须选择为使最小数不小于最大数的一半。
删除
首先，查找要删除的值。接着从包含它的节点中删除这个值。
如果没有节点处于违规状态则处理结束。
如果节点处于违规状态则有两种可能情况：
它的兄弟节点，就是同一个父节点的子节点，可以把一个或多个它的子节点转移到当前节点，而把它返回为合法状态。如果是这样，在更改父节点和两个兄弟节点的分离值之后处理结束。
它的兄弟节点由于处在低边界上而没有额外的子节点。在这种情况下把两个兄弟节点合并到一个单一的节点中，而且我们递归到父节点上，因为它被删除了一个子节点。持续这个处理直到当前节点是合法状态或者到达根节点，在其上根节点的子节点被合并而且合并后的节点成为新的根节点。
B*树
B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。
B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3(代替B+树的1/2) ;
B+树的分裂:当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针; B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针;
B树的分裂:当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了) ;如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针;所以，B树分配新结点的概率比B+树要低，空间使用率更高;
B-树和B+树和B*树的区别
**B-树:**多路搜索平衡树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点;所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中;
**B+树:**在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引; B+树总是到叶子结点才命中;
**B*树:**在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3;