B树
B树
引言
恶补一下数据结构，一切按照心中所想进行。
概况
如果要处理的数据规模很大，就只能存取到硬盘之中，采用分批次的方法进行进一步处理。
当要处理数据的时候直接调到内存中。
CPU不能直接与硬盘进行交互。
一次硬盘IO是非常缓慢的，访问成本比较高，这个时候AVL数和红黑树就不是很适合了。（因为硬盘访问次数与树高成正比）
这个时候就需要降低树高的平衡二叉树出现了，因此就出现了B树，一种多叉平衡搜索树。
B 树（B-tree）是一种自平衡的搜索树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。
在 B 树中，有两种节点：
- 内部节点（internal node）：存储了数据以及指向其子节点的指针。
- 叶子节点（leaf node）：与内部节点不同的是，叶子节点只存储数据，并没有子节点。
性质
一颗m阶B树，m表示这个树的每一个节点最多可以拥有的子节点个数。
性质如下：
- 每个节点最多有
m个子节点。 - 每个非叶子节点（除了根节点之外）最少有
(m+1)/2个节点，也就是向上取整。 - 如果根节点不是叶子节点，那么它至少有两个子节点。
- 所有的叶子节点都在同一层。
B树的特性：
平衡：所有的叶结点都在同一层。
有序：任一元素的左子树都小于它，右子树都大于它。
多路：最多
m个分支,m-1个元素。最少：（根节点：2个分支，1个元素），其他结点：(m+1)/2个分支，(m+1)/2-1个元素。
操作
查找
总体与二叉搜索树的查找很像，但在内部需要顺序查找或者说折半查找。
（节点内的比较：比他大向左子树走，比他小，那就继续向右走）
比如查找28。
- 遇到17，向右子树走。
- 遇到23，28>23，继续向右走。
- 遇到35，28<35，往35的左子树走。
- 遇到27，27<28，向右走。
- 遇到34，34>28，因此往34的左子树走。
- 遇到空结点了，也就是查找失败了。
插入
如上图的三阶B树。
步骤如下
- 先找到要插入的位置进行插入。比如20，会找到叶子结点，也就是23的左边，并没有出现上溢出。
- 如果上溢出了怎么办呢？比如下图的17，毫无疑问插入到14的右边。
不可避免的超过了2个结点的限制，接下来需要调整。
- 调整
(m+1)/2个元素，向上走，然后两边分裂开来。
- 如果父节点也上溢出了呢？如果插入53：
很明显，又是上溢出。以53为分割点，上移即可。
这时候上面也溢出了，那么就需要继续进行分裂了。
- 如果根节点也出现上溢出之后呢？
先查找到插入的位置进行插入(插入位置一定在叶结点) 如果没有上溢出，无需调整 否则中间元素(
(m+1)/2)上移,两边分裂 (直到没有上溢出为止)
构建
构建的操作严格遵循插入即可。
删除
删除操作比较容易出现下溢出的情况，因为有可能会少于最少的情况，如果是5阶B树那么最少要有2个元素，3个分支。
- 删除非叶结点元素最终会换成删除叶子结点，因为可以用前驱和后继元素进行替代，也就是所谓的最左的最右，和最右的最左。
- 这里用后继替换，并没有出现下溢出的情况。
- 删除68。之后就出现了下溢出的情况，少于两个元素了。先从左右兄弟借一个出来。先把65放下去，然后把60挪上去。也就是父亲下来，兄弟下去。当然整个过程需要满足有序性质。
- 如果左右兄弟不够借的时候，进行合并。父亲下移动，然后并过来即可。（挑一个兄弟进行合并，父亲下移，然后并起来）
- 如果父亲结点也下溢出了呢？删除30之后，40提上去。
- 和右兄弟合并：
- 父亲结点也下溢出了，继续看40的左右兄弟够不够借，父下来，兄下去，注意子树也要挪过来。
- 继续删除57，正常删除。
- 删除53，之后看看能不能借，不够借，进行合并操作。
- 父结点也下溢出了那么进行合并操作，注意捎带上子树。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Totoroの旅！
相关推荐
评论
