B树基本概念

本是古典何须时尚 2023-02-23 05:27 23阅读 0赞

# B树基本概念 #

## 概念 ##

*  为磁盘或其它存储设备设计的一种平衡搜索树
 *  类似红黑树，区别：在降低磁盘IO操作数上更好，结点可以有很多孩子
 *  红黑树每个结点1个关键字，且至多左右2个子节点。B树一个结点有n个关键字，则有n+1的子节点，n个关键字是n+1子节点的分隔域。
 *  B树也叫B-树
 *  B树其它变种，如B+树

## 性质 ##

具有惟一根结点的B树性质如下：

> 1.  结点x的属性
>     
>      *  x.n：存储在结点x中的关键字个数
>      *  x.key：表示结点x中的关键字，如x.key1、x.key2、x.key3...x.keyn，有序存放（非降序）,x.key1<=x.key2<=...x.keyn
>      *  x.leaf：bool变量，结点x是否为叶结点，true:是,false:不是
>      *  另外，每个节点都存储有值，或者指向值的指针
> 2.  非叶子结点包含x.n + 1个指向孩子的指针，叶子结点没有孩子，这个指针属性没有意义
> 3.  结点中的关键字x.key是其子结点中关键字范围的分割线。如：结点x的关键字为k1<=k2<=k3,x有4个子结点c1,c2,c3,c4，c1中的关键字 <= k1 <= c2中的关键字 <= k2 <= c3中的关键字 <= k3 <= c4中的关键字.
> 4.  每个叶结点具有相同的深度（树的高度）
> 5.  每个结点包含的关键字个数有上/下界。使用一个最小度数(固定整数t，t>=2)来表示。
>     
>      *  树非空，根结点至少一个关键字
>      *  根结点以外的每个结点至少t-1的关键字（下限），即t个子结点
>      *  每个结点至多2t-1个关键字（上限），即2t个子结点，达到上限称为满叶结点

如下是一棵B树，其中的数字是关键字，t 是3，高度只画了2层，再往下也类似，以关键字分隔，n个关键字分隔n+1个子结点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3g3NjM3OTUxNTE_size_16_color_FFFFFF_t_70][]

## 基本操作 ##

p.s. 下面的所有操作假定都在内存中，没有发生磁盘IO操作

### 创建空树 ###

1.  创建一个根结点
2.  设置其关键字个数为0
3.  设置其为叶结点

### 插入 ###

从根结点开始

1.  如果是叶子结点，根据大小开始检索插入位置：从最后一个关键字向前遍历，将比其大的后移一位，直到找到合适位置并插入，关键字个数加1
2.  非叶子结点：从当前结点递归向下查找，直到找到合适的叶子结点，进行步骤一。
    
    在查找过程中，遇到满结点（2t-1个关键字）进行分裂，分裂过程：
    
     *  满结点是根结点：创建一个空结点作为新的根结点，将原根结点从中间(第t个关键字处)一分为2，作为新根结点的左右2个子树，第t个关键字上升为新根结点的关键字。此时树的高度加1。
     *  满结点x为非根结点：
        
        1.  从中间（第t个关键字，关键字x.keyt）一分为2，分为y,z两个结点，y结点是原来的x结点，z是新建结点，把其中的另一半关键字copy到z上。
        2.  将关键字x.keyt上升到父结点上，作为父结点的关键字
    
    以上步骤，忽略属性赋值过程，如：新建z结点时，z结点的leaf属性和原x结点一样;分为左右子结点时，其父结点需要一个增加一个指针指向新建的右子结点。

### 删除 ###

增加结点，保证结点关键字个数不能超过2t-1，遇满结点分裂；删除结点，要求除根结点外，结点关键字个数不能少于t个（最小度数），否则需要合并。

从结点x中删除关键字k，从根结点t开始向下：

1.  x是叶子结点且k是结点x的关键字，删除k
2.  x是非叶子结点且k是x的关键字：
    
     *  如果x的k关键字的左边子结点有至少t个关键字，从左子结点树中找到k的前驱kp，将kp的值覆盖x结点k的值（k已删除），递归删除kp
     *  x的k关键字的右边子结点有至少t个关键字，从右子结点树中找到k的后继kn，将kn的值覆盖x结点k的值（k已删除），递归删除kn
     *  x的k关键字的左右子结点都只有t-1关键字，将x中的k和右子结点所有关键字都合并到左子结点，释放x的key和指向右子结点的指针；从左子结点递归删除k
3.  k不是x的关键字，且k在x的某个子树x.ck中：
    
     *  x.ck只有t-1个关键字且相邻兄弟有至少t个关键字：将父结点x的某个关键字给x.ck，将x.ck的兄弟结点的某个关键字给父结点x，这样x.ck就有t个关键字
     *  x.ck和它所有兄弟结点都是t-1个关键字：将x.ck和它某个兄弟合并，并把x的这个分隔的关键字拿下来作为合并后的中间关键字，此时如果x是根结点且这个时候空了，那就移除x，并且合并后的结点作为新的根结点

注意，一旦根结点关键字为空，则它的惟一子结点作为新的根结点，此时树高减1。

### 搜索 ###

类似二叉搜索树，但是此时是结点的个关键字个数为n，作n+1路搜索

## B+树 ##

B树变种，个人经验多用于数据库索引

和B树的不同是非叶子结点（叫内部结点），都不是值，或者指向值的属性。B树每个结点都携带有值。B+树是只有叶子节点包含的有值，或者指向存值位置的指针。

B+树相比B树更适合索引的原因：具体涉及到内存、磁盘、IO操作数等建议看专业资料理解。简单理解：查询效率由IO操作数决定（回盘多少次），数据最终都是持久化到磁盘中，查询数据时候的，内存以页为单位从磁盘加载数据。如果内部结点只有关键字没有值，一次可加载更多关键字，数据更紧密，可减少更多IO操作。个人理解，仅供参考。

## 参考资料 ##

《算法导论 第三版》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3g3NjM3OTUxNTE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200705200944527.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3g3NjM3OTUxNTE=,size_16,color_FFFFFF,t_70