B-Tree和B+Tree学习笔记

程序员文章站 2022-07-05 16:59:01

...

B-Tree和B+Tree学习笔记

文章目录

B-Tree和B+Tree学习笔记

1. B-Tree

1.1 定义

全称Balance-tree(平衡多路查找树)，平衡的意思是左边和右边分布均匀。多路的意思是相对于二叉树而言的，二叉树是二路查找树，而B-tree有多条路。

B-Tree的阶指的是节点最大的孩子数目。

我的理解是在二叉树的基础上增加了规则：

若根节点非叶子节点，则其至少有两棵子树
除了根节点和叶子节点之外，每个节点有k-1个key和k个孩子，其中**m/2上取整-1 ≤ k ≤ m-1**
所有叶子节点在同一层次
key按序排列

1.2 图例

如下图是一个阶m=3的B-Tree：

B-Tree和B+Tree学习笔记

1.3 用途

显著减少定位记录时经历的过程。一般用于数据库的索引。

因为B树相对AVL树之类的结构而言具有一个节点存多个数据以及较为矮胖的特性，所以可以显著降低访问磁盘带来的IO开销。

~~对比B树和平衡二叉树，是否因为显著减少层高，减少了磁盘IO？~~

1.4 代码实现

1.4.1 数据结构定义

节点类型

所有非终端节点中包含(n,A0,K1,A1,K2,A2…,Kn,An)。

其中n为关键字个数，Ki为关键字，Ai-1为小于Ki的节点指针，Ai为大于Ki的节点指针。

// 结点类型
typedef struct BTNode
{
    int keynum;                //结点关键字个数
    struct BTNode *parent;     //指向双亲结点
    KeyType key[m + 1];        //关键字数组，0号单元未用
    struct BTNode *ptr[m + 1]; //孩子结点指针数组
    Record recptr[m + 1];      //记录数组，0号单元未用
    BTNode() : keynum(), parent(), key(), ptr(), recptr() {}
} BTNode, *BTree;

查找结果类型

用于记录在B-Tree中的查找结果。

// 查找结果类型
struct Result
{
    BTNode *pt; //指向找到的结点
    int i;      //在结点中的关键字位置;
    bool found; //查找成功与否标志
    Result() : pt(), i(), found() {}
    Result(BTNode *pt, int i, bool found) : pt(pt), i(i), found(found) {}
};

1.4.2 实现查找

SearchBTNode()函数

在结点p中查找关键字k的位置 i

**i **使得：p->key[i] <= k < p->key[i+1]

找到对应key则 i 就是key的下标，没找到对应key则 i 就是继续向下查找的指针的下标
```
int SearchBTNode(BTNode *p, KeyType k)
{
    int i = 0;
    while (i < p->keynum && k >= p->key[i + 1])
        i++;
    return i;
}
```

SearchBTree()函数

在树t上查找关键字k,返回结果(pt,i,tag)

成功则tag=1,关键字k是指针pt所指结点中第i个关键字

失败则tag=0,关键字k的插入位置为pt结点的第i个

Result SearchBTree(BTree t, KeyType k)
{
    // 初始化，p指向待查节点，q指向p的双亲
    BTNode *p = t;
    BTNode *q = nullptr;
    bool found = false;
    int i = 0;
    //while循环查找过程，条件1：p非空（没到叶子节点），条件2：还没找到
    while (p && !found)
    {
        i = SearchBTNode(p, k);
        if (i > 0 && p->key[i] == k)
            found = true;
        else
        {
            q = p;
            p = p->ptr[i];
            found = false;
        }
    }
    if (found)
        return Result(p, i, 1); // 查找成功，返回其在B树中位置
    else
        return Result(q, i, 0); // 查找不成功，返回其插入位置
}

1.4.3 实现插入

InsertBTNode()函数

将关键字k和结点q分别插入到p->key[i+1]和p->ptr[i+1]中

void InsertBTNode(BTNode *&p, int i, KeyType k, BTNode *q)
{
    // i+1之后（包括原i+1）整体后移，空出位置i+1
    int j;
    for (j = p->keynum; j > i; j--)
    {
        p->key[j + 1] = p->key[j];
        p->ptr[j + 1] = p->ptr[j];
    }
    // 插入k和q
    p->key[i + 1] = k;
    p->ptr[i + 1] = q;
    if (q != nullptr)
        q->parent = p;
    p->keynum++;
}

SplitBTNode()函数

将插入新节点后的节点p（含有m个key，已经节点过大）分裂成两个结点，并返回分裂点x

KeyType SplitBTNode(BTNode *&p, BTNode *&q)
{
    int s = (m + 1) / 2;
    q = new BTNode;        //新建节点q
    q->ptr[0] = p->ptr[s]; //后一半移入节点q
    for (int i = s + 1; i <= m; i++)
    {
        q->key[i - s] = p->key[i];
        q->ptr[i - s] = p->ptr[i];
        q->recptr[i - s] = p->recptr[i];
    }
    q->keynum = p->keynum - s; //节点q存放m-s个
    q->parent = p->parent;
    //转移到节点q之后，修改双亲指针
    for (int i = 0; i <= q->keynum; i++)
    {
        if (q->ptr[i] != nullptr)
            q->ptr[i]->parent = q;
    }
    p->keynum = s - 1; //节点p存放s个，但保留s-1个，p中最后一个key作为分裂点x
    return p->key[s];
}

NewRoot()函数

当【t为空树】或【原根节点p分裂为p和q】时使用

生成新的根结点t，原结点p和结点q为子树指针

void NewRoot(BTree &t, KeyType k, BTNode *p, BTNode *q)
{
    t = new BTNode;
    t->keynum = 1;
    t->ptr[0] = p;
    t->ptr[1] = q;
    t->key[1] = k;
    // 调整结点p和结点q的双亲指针
    if (p != nullptr)
        p->parent = t;
    if (q != nullptr)
        q->parent = t;
    t->parent = nullptr;
}

InsertBTree()函数

在树t上结点p的key[i]之后插入关键字k

若引起结点过大，则尝试向上分裂

Status InsertBTree(BTree &t, int i, KeyType k, BTNode *p)
{
    bool finished = false;
    BTNode *q = nullptr;
    KeyType x = k;
    while (p && !finished)
    {
        InsertBTNode(p, i, x, q);
        if (p->keynum < m)
            finished = true;
        else
        {
            x = SplitBTNode(p, q);
            //若p的双亲存在，在双亲节点中找x的插入位置
            p = p->parent;
            if (p)	i = SearchBTNode(p, x);
        }
    }
    //未完成，情况1：t是空树（初始p为nullptr），情况2：根节点分裂为p和q
    if (!finished)
    {
        p = t; //原t即为p
        NewRoot(t, x, p, q);
    }
    return OK;
}

1.4.4 实现删除

AdjustBTree()函数

删除节点p中的第i个关键字后，调整B树

在删除操作后，如果非根节点出现节点关键字个数不足的情况，会使用AdjustBTree()函数来调整B树。

假设删除的key为k，它所在节点的双亲节点为p：
- k在p的最左孩子节点中：
  - 右兄弟够借：p的最左key移入k所在节点，右兄弟的最左key移入p。
  - 右兄弟不够借：将p中的Ki和右兄弟中的全部key一起合并到k所在节点。
- k在p的最右孩子节点中：
  - 左兄弟够借：p的最右key移入k所在节点，左兄弟的最右key移入p。
  - 左兄弟不够借：将p中的Ki和k所在节点剩余的key一起合并到左兄弟。
- k在p的中间孩子节点中：
  - 左兄弟够借：p的最右key移入k所在节点，左兄弟的最右key移入p。
  - 右兄弟够借：p的最左key移入k所在节点，右兄弟的最左key移入p。
  - 都不够借：将p中的Ki和k所在节点剩余的key一起合并到左兄弟。
```
void AdjustBTree(BTNode *p, int i)
{
    // 删除的是最左孩子节点中的关键字
    if (i == 0)
        if (p->ptr[1]->keynum > keyNumMin) //右节点够借
            MoveLeft(p, 1);
        else //右节点不够借
            Combine(p, 1);
    // 删除的是最右孩子节点中的关键字
    else if (i == p->keynum)
        if (p->ptr[i - 1]->keynum > keyNumMin) //左节点够借
            MoveRight(p, p->keynum);
        else //左节点不够借
            Combine(p, p->keynum);
    // 删除的是中间孩子节点中的关键字且左节点够借
    else if (p->ptr[i - 1]->keynum > keyNumMin)
        MoveRight(p, i);
    // 删除的是中间孩子节点中的关键字且右节点够借
    else if (p->ptr[i + 1]->keynum > keyNumMin)
        MoveLeft(p, i + 1);
    // 删除的是中间孩子节点中的关键字且左右都不够借
    else
        Combine(p, i);
}
```

BTNodeDelete()函数

在节点p中查找并删除关键字k，若未找到则递归向下删除

bool BTNodeDelete(BTNode *p, KeyType k)
{
    int i;
    bool found; //查找标志
    if (p == nullptr)
        return 0;
    else
    {
        found = FindBTNode(p, k, i); //返回查找结果
        //查找成功
        if (found)
        {
            //删除的是非叶子节点的关键字
            //理解i-1：若为非叶子节点，被删除关键字为key[i]，则ptr[i-1]一定存在
            if (p->ptr[i - 1] != nullptr)
            {
                p->key[i] = FindReplace(p->ptr[i]); //寻找相邻关键字(右子树中最小的关键字)
                BTNodeDelete(p->ptr[i], p->key[i]); //执行删除操作
            }
            else
                Remove(p, i); //从节点p中位置i处删除关键字
        }
        else
            found = BTNodeDelete(p->ptr[i], k); //沿孩子节点递归查找并删除关键字k
        // 非叶子节点删除后可能从右子树替补，可能会使右子树关键字个数不足
        if (p->ptr[i] != nullptr)
            if (p->ptr[i]->keynum < keyNumMin) //删除后关键字个数不足
                AdjustBTree(p, i);             //调整B树
        return found;
    }
}

BTreeDelete()函数

删除操作，在B树中删除关键字k

调用BTNodeDelete()函数

void BTreeDelete(BTree &t, KeyType k)
{
    bool deleted = BTNodeDelete(t, k); //删除关键字k
    //查找失败
    if (!deleted)
        printf("key[%d] is not exist!\n", k);
    //删除后根节点无key
    else if (t->keynum == 0)
    {
        BTNode *p = t;
        t = t->ptr[0];
        delete p;
    }
}

DestroyBTree()函数

递归释放B树

void DestroyBTree(BTree &t)
{
    if (!t)
        return;
    BTNode *p = t;
    for (int i = 0; i <= p->keynum; i++)
        DestroyBTree(p->ptr[i]);
    delete p;
    t = nullptr;
}

1.4.5 实现层序遍历

这部分主要使用队列进行广度优先搜索，完成层序遍历，打印B树

重点是使用length记录每次的队列长度，控制每轮循环打印的节点个数刚好等于这一层的节点数

LevelTraverse()函数

层序遍历

void LevelTraverse(BTree t)
{
    queue<BTNode *> que;
    BTNode *p;
    int length;    //队列长度，用于控制每一层的节点个数
    int level = 0; //记录层数

    que.push(t);
    while (!que.empty())
    {
        length = que.size(); // 获取当前队列长度，用于分层
        //打印当前层所有节点
        printf("\tLevel %-2d:", level++);
        for (int i = 0; i < length; i++)
        {
            // 弹出头节点作为当前节点
            p = que.front();
            que.pop();
            // 打印当前节点
            printf("[");
            printf("%d", p->key[1]);
            for (int j = 2; j <= p->keynum; j++)
            {
                printf(", %d", p->key[j]);
            }
            printf("]  ");
            // 把当前节点的所有非空子节点加入队列
            for (int j = 0; j <= p->keynum; j++)
            {
                if (p->ptr[j] && p->ptr[j]->keynum != 0)
                    que.push(p->ptr[j]);
            }
        }
        printf("\n");
    }
}

PrintBTree()函数

打印B树

Status PrintBTree(BTree t)
{
    if (t == NULL)
    {
        printf("\tEmpty B-Tree!\n");
        return EMPTY;
    }
    LevelTraverse(t);
    return OK;
}

1.4.6 测试

测试B树各项功能

测试流程：

创建一棵m阶（m=5）B树，其中的key从1到16
打印菜单，可选操作有：
- Init 初始化B树
- Insert 插入key
- Delete 删除key
- Destroy 销毁B树
- Exit 退出程序
进行操作观察输出

如下图是m=5，key从1到16的B树：

B-Tree和B+Tree学习笔记

2. B+Tree

2.1 B-Tree的不足

遍历时使用中序遍历，往返于节点之间，增加磁盘块读写开销
非叶子节点同时存储key和data，一个节点能存放的key数目受限，使树长高
查询性能不稳定
范围查询不友好

2.2 B+Tree的特点

叶子节点包含全部关键字
叶子节点之间用指针串接，遍历时直接从叶子节点的头指针开始
非叶子节点只存储key，data全部存放在叶子节点
所有非叶子节点可以看作索引，只存放其孩子的最大（或最小）key
查询性能稳定
范围查询友好

2.3 图例

如下图是一个阶m=4的B+Tree：

B-Tree和B+Tree学习笔记

图中非叶子节点存放的是其孩子的最小key，图左下的磁盘块4有问题，key=10的索引不应该出现在这个磁盘块里。

3. 对比B-Tree和B+Tree

3.1 差别

	B-Tree	B+Tree
n个关键字	n+1个分支	n个分支
节点内关键字个数	[m/2(上取整)-1,m-1]，根节点[1,m-1]	[m/2(上取整),m]，根节点[2,m]
叶子节点	关键字不全	包含全部关键字，指针指向记录
非叶子节点	含data	不含data，只存索引
叶子节点链表	无	有

3.2 图例

B-Tree和B+Tree学习笔记

相关标签：学习笔记数据结构指针

上一篇：实例说明软链接和硬链接的区别

下一篇： Halcon学习笔记：xyz_attrib_to_object_model_3d示例

B-Tree和B+Tree学习笔记

B-Tree和B+Tree学习笔记

文章目录

1. B-Tree

1.1 定义

1.2 图例

1.3 用途

1.4 代码实现

1.4.1 数据结构定义

1.4.2 实现查找

1.4.3 实现插入

1.4.4 实现删除

1.4.5 实现层序遍历

1.4.6 测试

2. B+Tree

2.1 B-Tree的不足

2.2 B+Tree的特点

2.3 图例

3. 对比B-Tree和B+Tree

3.1 差别

3.2 图例

Linux学习笔记（二）：文件目录管理和VIM编辑器的使用

JavaScript学习笔记整理_关于表达式和语句

pygame学习笔记（2）：画点的三种方法和动画实例

ES6学习笔记之正则表达式和字符串正则方法分析

Java学习笔记 DbUtils数据库查询和log4j日志输出使用

java学习笔记(基础篇)—关键字static和final

C++学习笔记之调用构造函数和析构函数的顺序

荐 opencv进阶学习笔记3：像素运算和图像亮度对比度调节

关于Vue.js一些问题和思考学习笔记（1）

关于Vue.js一些问题和思考学习笔记（2）

B-Tree和B+Tree学习笔记

B-Tree和B+Tree学习笔记

文章目录

1. B-Tree

1.1 定义

1.2 图例

1.3 用途

1.4 代码实现

1.4.1 数据结构定义

1.4.2 实现查找

1.4.3 实现插入

1.4.4 实现删除

1.4.5 实现层序遍历

1.4.6 测试

2. B+Tree

2.1 B-Tree的不足

2.2 B+Tree的特点

2.3 图例

3. 对比B-Tree和B+Tree

3.1 差别

3.2 图例

Linux学习笔记（二）：文件目录管理和VIM编辑器的使用

JavaScript学习笔记整理_关于表达式和语句

pygame学习笔记（2）：画点的三种方法和动画实例

ES6学习笔记之正则表达式和字符串正则方法分析

Java学习笔记 DbUtils数据库查询和log4j日志输出 使用

java学习笔记(基础篇)—关键字static和final

C++学习笔记之调用构造函数和析构函数的顺序

荐 opencv进阶学习笔记3：像素运算和图像亮度对比度调节

关于Vue.js一些问题和思考学习笔记（1）

关于Vue.js一些问题和思考学习笔记（2）

Java学习笔记 DbUtils数据库查询和log4j日志输出使用