🪴qql1's digital garden

B树 B-树

7分钟阅读

1. 适用范围:

  1. 减少对硬盘中不同数据块的切换次数
  2. 加快访问硬盘中的数据
    1. 与主存的访问时间相比，磁盘的 I/O 操作相当耗时
    2. 而B-树就可以减少数据块之间的切换, 减少磁盘I/O 操作次数
  3. 存储大量数据, 又要保证查找性能

2. 梗概:

B/B-树是一种平衡的多路查找树: B-树有两种定义: 最小度定义 和 m阶定义 最小度定义:

  1. 所有的叶子结点都在同一层
  2. 每个结点包含的 子树总数有上界和下界
    1. 即 非根结点的子树总数∈[t,2t]
      1. 用一个被称为 B-树的 最小度数 的固定整数 t 来表示这些界 ，其中 t 取决于磁盘块的大小
      2. 因此非根结点包含的 关键字数量∈[t-1,2t-1]
    2. 根结点 子树总数∈[2,2t]
  3. 每个结点的子树要么全为空, 要么全非空

3. 性质:

  1. 关键字与左右子树的位置关系
    1. keys[i]的左子树为Children[i]
    2. keys[i]的右子树为Children[i+1]
    3. Children[i+1]=keys[i]的右子树=keys[i+1]的左子树
  2. B-树插入结点是从叶子往根生长变高的

4. 操作:

  1. 遍历
  2. 查找
  3. 分裂
  4. 插入
    1. 插入前先查找到要插入的位置
    2. 查找插入往往需要伴随着分裂
      1. 分裂与插入顺序有两种关系:
        1. 查找的时候就分裂沿途已满的结点
        2. 插入后再往上逐渐分裂已满的结点
      2. 分裂的具体操作:
        1. 需要知道该已满结点在双亲结点中的子树位置i
        2. 把已满结点的中位关键字单独分离出来
          1. 但其左右子树并不分离
        3. 从中位把已满结点分为长度相等的两半
          1. 左边那一半包括第一个子树~中位关键字的左子树
          2. 右边那一半包括最后一个子树~中位关键字的右子树
        4. 双亲结点将多插入一个关键字和一个子树
          1. 中位关键字插在第i位
            1. 这时自然地, 中位关键字的左子树为左半分裂结点
          2. 右半分裂结点插入在第i+1位
            1. 作为中位关键字的右子树
  5. 删除

5. 在c语言中的实现

1. 定义:

代码:

#define t 3
typedef struct BTreeNode{
    /*如果已满,中位数为keys[t-1]*/
    int keys[2*t-1];
    /*keys[i]的左孩子为Children[i],右孩子为i+1*/
    struct BTreeNode* Children[2*t];
    int keynum;
    char leaf;//用来标记是否叶子节点
}BTreeNode,*BTree;

2. 遍历:

void traverse(BTree root){
    if(!root)return;
    int i;
    /*递归通过关键字逐个递归遍历所有子树*/
    for(i=0;i<root->keynum;++i){
        if(!root->leaf)
            traverse(root->Children[i]);
        /*操作root->keys[i]*/
    }
    /*遍历递归最右子树*/
    if (!root->leaf)
        traverse(root->Children[i]);
}

3. 查找:

递归方式:

BTreeNode *search(BTree root,int key){
    if(!root)return NULL;
    int i=0;
    /*在当前结点中找到大于等于关键字的*/
    for(;i<root->keynum && root->keys[i]<key;++i);
    /*递归出口*/
    if(root->keys[i]==key)
        return root;
    else if(root->leaf)return NULL;
    /*对应子树下递归搜索*/
    else return serach(root->Children[i],key);
}

4. 插入操作:

4.1. 前置插入的方式:

梗概:

  1. 采用递归的方式
    1. 方便回溯沿途结点
      1. 方便找到沿途已满的结点, 然后分裂它
  2. 在递归前先初始化
    1. 初始化空树
    2. 初始化已满的根结点
  3. 递归查找并插入
    1. 递归出口: 当前结点为叶结点
      1. 把关键字插入到当前叶结点
    2. 递归的同时分裂沿途上已满的结点
      1. 分裂操作:
        1. 创建一个新的结点保存右半分裂部分
        2. 把中位关键字和右半分裂部分别插入双亲结点中
          1. 中位关键字对应左半分裂部分的位置(i)
          2. 右半分裂部分对应中位关键字的右子树位置(i+1) 代码:
void insertNonFull(BTree root,int key);
void splitChild(BTreeNode *parent,int i,BTreeNode *son);
 
void insert(BTree* root,int key){
    /*为递归插入初始化树*/
    if(*root ==NULL){
        BTreeNode* s=(BTreeNode*)calloc(1,sizeof(BTreeNode));
        s->keys[0]=key;s->keynum=1;s->leaf=0;
        *root = s;
    }
    /*为递归插入初始化分裂根结点*/
    else if((*root)->keynum>=2*t-1){
        /*往上生长,构建新根*/
        BTreeNode *s=(BTreeNode*)calloc(1,sizeof(BTreeNode));
        s->Children[0]=*root;
        /*把新根作为整个树的根*/
        *root=s;
        splitChild(s,0,*root);
        /*分裂后有两个子树,查找需要往那颗子树递归插入*/
        int i=0;
        for(;s->keys[0]<key;++i)
        insertNonFull(s->Children[i],key);
    }
    else insertNonFull(*root,key);
}
 
void insertNonFull(BTree root,int key){
    int i=root->keynum-1;//从后往前遍历
    if(root->leaf){//递归出口
        /*采用直接插入排序法*/
        for(;i>=0 && root->keys[i]>key;--i)
            root->keys[i+1]=root->keys[i];
        root->keys[i+1]=key; root->keynum++;
        return;
    }
    /*找到已有键值中最接近的,然后根据下标找到对应的子树*/
    for(;i>=0 && root->keys[i]>key;)--i;
    /*查找插入位置的同时分裂沿途已满的结点*/
    if(root->Children[i+1]->keynum==2*t-1){
        splitChild(root,i+1,root->Children[i+1]);
        /*下层分裂后有关键字新增到i+1处,判断其是否是递归插入的目标*/
        if(root->keys[i+1])i++;
    }
    /*递归找到叶结点并插入*/
    insertNonFull(root->Children[i+1],key);
}
 
void splitChild(BTreeNode *parent,int i,BTreeNode *son){
//把parent结点下的第i颗子树son分裂
    BTreeNode *z=(BTreeNode*)calloc(1,sizeof(BTreeNode));
    z->keynum=t-1;//对半分裂后剩t个,抽去最前面一个键值,减1个
    z->leaf=son->leaf;
    /*把原结点son的中位数以后的树都赋给新结点z*/
    for(int j=0;j<t-1;j++)
        z->keys[j]=son->keys[j+t];
    son->keynum=t-1;//更新分裂后的关键字数量
    /*把原结点son的后半子树都赋给新节点z*/
    if(!(son->leaf))
        for(int j=0;j<t;++j)
            z->Children[j]=son->Children[j+t];
    /*因为要有新关键字插入parent,所以要在i处腾空位*/
    for(int j=parent->keynum-1;j>=i;--j)
        parent->keys[j+1]=parent->keys[j];
    parent->keys[i]=son->keys[t-1];parent->keynum++;
    /*因为有新的子树插入parent,所以要在i+1处腾空位*/
    for(int j=parent->keynum+1;j>=i+1;--j)
        parent->Children[j+1]=parent->Children[j];
    parent->Children[i+1]=z;
}

关系图谱

反向链接