算法笔记:B树

zhenghaoz 等级 510 1 0

B树广泛应用于各种文件系统,文件系统中,数据都是按照数据块来进行读取操作。结合二叉树的优点和文件系统的特点,于是就有了B树:

算法笔记:B树

B树当中每个节点存储着一组数据,数据的数量由B树的来决定。

B树中的节点包含以下内容:

  • 大小(size):用来记录当前节点中元素的个数;

  • 关键字(key):B树是有序集合,关键字是可比的,用于在集合中定位卫星数据;

  • 是否为叶子节点(leaf):节点类型可以分为内部节点和叶子节点。

  • 孩子节点(children):如果当前节点是一个内部节点的话,那么就有更加底层的孩子节点。如果是叶子节点。那就没有孩子节点。孩子节点的数量总是比数据的数量多一个。

对于一个度数为N的B树,需要保持以下性质:

  • 一个节点中的数据量不小于N-1并且不大于2N-1,一个例外就是根节点可以包含小于N-1数量的数据;

  • 所有的叶子节点高度相等;

  • 在节点中,所有的数据关键字保持递增关系(key[0] < ... < key[size-1]);

  • 对于一个孩子节点children[i],children[i]子树中所有关键大于key[i-1]并且小于key[i](key[-1]=-∞,key[size]=+∞)。

度数小于2的B树是没有意义的,因此度数最小的取值为2。完整的B树实现见Gist

节点定义

B树中不存在循环引用,因此可以大胆使用shared_ptr来代替原生指针,简化析构操作。B树的拷贝可以通过递归进行,因此数据结构地拷贝也就简单了很多。

struct Node
{
    bool _leaf;
    int _size;
    vector<Key> _keys = vector<Key>(2*N-1);
    vector<Value> _values = vector<Value>(2*N-1);
    vector<shared_ptr<Node>> _children = vector<shared_ptr<Node>>(2*N);
    Node() = default;
    Node(const Node &node): _leaf(node._leaf), _size(node._size), _keys(node._keys), _values(node._values)
    {
        if (!_leaf)
            for (int i = 0; i <= _size; i++)
                _children[i] = std::make_shared<Node>(*node._children[i]);
    }
};

创建

创建一个空地叶子结点,作为根节点。

BTree()
{
    root = std::make_shared<Node>();
    root->_leaf = true;
    root->_size = 0;
}

查找

如果在当前节点找到关键字,返回卫星数据指针。如果没有找到关键字,那么需要检查当前节点是否为叶节点,如果是叶节点,那么说明关键字不存在,返回指针,如果是内部节点,那么在子树中查找关键字。

Value* find(shared_ptr<Node> node, Key key)
{
    // search key in node
    int i = 0;
    while (i < node->_size && key > node->_keys[i])
        i++;
    if (i < node->_size && key == node->_keys[i])
        return &node->_values[i];
    else if (node->_leaf)
        return nullptr;
    else return find(node->_children[i], key);
}

分裂

当一个节点数据量到达2N-1时后,如果想要继续插入,就需要对节点进行分裂。把孩子节点中间元素提升到父节点中,然后产生两个新的孩子节点分别插入中间元素两侧。

算法笔记:B树

// split a full node (child.size == 2*N-1)
void split(shared_ptr<Node> parent, int i, shared_ptr<Node> child)
{
    shared_ptr<Node> nchild = std::make_shared<Node>();
    nchild->_leaf = child->_leaf;
    nchild->_size = child->_size = N-1;
    // move k-v
    for (int j = 0; j < N-1; j++) {
        nchild->_keys[j] = child->_keys[j + N];
        nchild->_values[j] = child->_values[j + N];
    }
    // move children
    if (!child->_leaf)
        for (int j = 0; j < N; j++)
            nchild->_children[j] = child->_children[j + N];
    // move child->key[N-1] up
    for (int j = parent->_size; j > i; j--) {
        parent->_keys[j] = parent->_keys[j-1];
        parent->_values[j] = parent->_values[j-1];
        parent->_children[j+1] = parent->_children[j];
    }
    parent->_keys[i] = child->_keys[N-1];
    parent->_values[i] = child->_values[N-1];
    parent->_children[i+1] = nchild;
    parent->_size++;
}

合并

合并操作是分裂操作的逆向过程。

// combine children[i] and children[i+1]
void combine(shared_ptr<Node> parent, int i)
{
    shared_ptr<Node> prev = parent->_children[i];
    shared_ptr<Node> next = parent->_children[i+1];
    // move parent->key[i] down
    prev->_keys[prev->_size] = parent->_keys[i];
    prev->_values[prev->_size] = parent->_values[i];
    prev->_size++;
    // move k-v from next to prev
    for (int j = 0; j < next->_size; j++) {
        prev->_keys[j + prev->_size] = next->_keys[j];
        prev->_values[j + prev->_size] = next->_values[j];
    }
    if (!prev->_leaf)
        for (int j = 0; j <= next->_size; j++)
            prev->_children[j + prev->_size] = next->_children[j];
    prev->_size += next->_size;
    // remove parent->key[i]
    parent->_size--;
    for (int j = i; j < parent->_size; j++) {
        parent->_keys[j] = parent->_keys[j+1];
        parent->_values[j] = parent->_values[j+1];
        parent->_children[j+1] = parent->_children[j+2];
    }
}

插入

当根节点满了,需要创建一个新的根节点,然后将旧的根节点分裂,成为新的根节点的子节点。 算法笔记:B树

// insert k-v in root node
void insert(Key key, Value value)
{
    shared_ptr<Node> ptr = root;
    if (ptr->_size == 2*N-1) {    // split root node
        root = std::make_shared<Node>();
        root->_leaf = false;
        root->_size = 0;
        root->_children[0] = ptr;
        split(root, 0, ptr);
        insert(root, key, value);
    } else insert(root, key, value);
}
  • 插入叶节点:直接插入即可。

  • 插入内部节点:首先,找到新关键字所在的子节点,如果子节点满,进行分裂。然后插入到合适的子节点中。

算法笔记:B树

void insert(shared_ptr<Node> node, Key key, Value value)
{
    // find insert position
    int i = 0;
    while (i < node->_size && key > node->_keys[i])
        i++;
    if (node->_leaf) {    // insert k-v in a leaf
        for (int j = node->_size; j > i; j--) {
            node->_keys[j] = node->_keys[j-1];
            node->_values[j] = node->_values[j-1];
        }
        node->_keys[i] = key;
        node->_values[i] = value;
        node->_size++;
    } else {            // insert k-v in subnode
        shared_ptr<Node> ptr = node->_children[i];
        if (ptr->_size == 2*N-1) {
            split(node, i, ptr);
            if (key > node->_keys[i])
                i++;
        }
        insert(node->_children[i], key, value);
    }
}

删除

和插入操作一样,删除操作也是自顶向下对B树进行调整,必须保证要删除的关键字位于B树中,否则会产生意想不到的后果,对于删除操作,处理方式如下:

算法笔记:B树

  • 情况1,当前节点是叶子节点,找到关键字:直接删除关键字即可。

  • 情况2,当前节点是内部节点,找到关键字key[i]:

    • 情况2a,如果关键字的左孩节点children[i]->size>=N:用children[i]中的最大元素(关键字的前驱)代替关键字,然后在children[i]中删除最大元素。

    • 情况2b,如果关键字的右孩节点children[i+1]->size>=N:用children[i+1]中的最小元素(关键字的后继)代替关键字,然后在children[i+1]中删除最小元素

    • 情况2c,如果关键字的左右两个子节点都小于N-1:这时可以合并两个子节点,于是关键字key[i]落入新合并成的节点中,接着在新的节点中删除关键字。

  • 情况3,当前节点是内部节点,找到关键字所在的子树children[i]:如果children[i]->size<N,那么还需要进行一些调整之后再删除。

    • 情况3a,如果children[i]的某个相邻兄弟节点children[x]->size>=N:通过移动操作,使得children[x]元素数量减一,children[i]元素数量加一。

    • 情况3b,如果children[i]的所有相邻兄弟节点children[x]->size < N:将children[i]和任意一个children[x]合并。(到底和左边的合并好还是右边的好,好纠结~)

// remove key from node, key must be in node
void remove(shared_ptr<Node> node, Key key)
{
    // find delete position
    int i = 0;
    while (i < node->_size && key > node->_keys[i])
        i++;
    if (node->_leaf) {                                        // case 1: remove k-v from leaf
        node->_size--;
        for (int j = i; j < node->_size; j++) {
            node->_keys[j] = node->_keys[j+1];
            node->_values[j] = node->_values[j+1];
        }
    } else if (i < node->_size && key == node->_keys[i]) {    // case 2: find key in internal node
        shared_ptr<Node> prevChild = node->_children[i];
        shared_ptr<Node> nextChild = node->_children[i+1];
        if (prevChild->_size >= N) {                        // case 2a: move precursor to the position of key
            shared_ptr<Node> maxNode = max(prevChild);
            node->_keys[i] = maxNode->_keys[maxNode->_size-1];
            node->_values[i] = maxNode->_values[maxNode->_size-1];
            remove(prevChild, maxNode->_keys[maxNode->_size-1]);
        } else if (nextChild->_size >= N) {                    // case 2b: move successor to the position of key
            shared_ptr<Node> minNode = min(nextChild);
            node->_keys[i] = minNode->_keys[0];
            node->_values[i] = minNode->_values[0];
            remove(nextChild, minNode->_keys[0]);
        } else {                                            // case 2c: combine previous child and next child
            combine(node, i);
            remove(node->_children[i], key);
        }
    } else {                                                        // case 3
        shared_ptr<Node> subNode = node->_children[i];
        if (subNode->_size < N) {
            shared_ptr<Node> prevBrother, nextBrother;
            if (i > 0)                prevBrother = node->_children[i-1];
            if (i < node->_size)    nextBrother = node->_children[i+1];
            if (prevBrother && prevBrother->_size >= N) {            // case 3a
                // remove node->key[i] into subNode
                for (int j = subNode->_size; j > 0; j--) {
                    subNode->_keys[j] = subNode->_keys[j-1];
                    subNode->_values[j] = subNode->_values[j-1];
                }
                if (!subNode->_leaf)
                    for (int j = subNode->_size; j >= 0; j--)
                        subNode->_children[j+1] = subNode->_children[j];
                subNode->_keys[0] = node->_keys[i-1];
                subNode->_values[0] = node->_values[i-1];
                subNode->_children[0] = prevBrother->_children[prevBrother->_size];
                subNode->_size++;
                // remove prevBrother->key[prevBrother->size-1] into node
                node->_keys[i-1] = prevBrother->_keys[prevBrother->_size-1];
                node->_values[i-1] = prevBrother->_values[prevBrother->_size-1];
                prevBrother->_size--;
            } else if (nextBrother && nextBrother->_size >= N) {    // case 3a    
                // remove node->key[i] into subNode
                subNode->_keys[subNode->_size] = node->_keys[i];
                subNode->_values[subNode->_size] = node->_values[i];
                subNode->_children[subNode->_size+1] = nextBrother->_children[0];
                subNode->_size++;
                // remove nextBrother->key[0] into node
                node->_keys[i] = nextBrother->_keys[0];
                node->_values[i] = nextBrother->_values[0];
                nextBrother->_size--;
                for (int j = 0; j < nextBrother->_size; j++) {
                    nextBrother->_keys[j] = nextBrother->_keys[j+1];
                    nextBrother->_values[j] = nextBrother->_values[j+1];
                }
                if (!nextBrother->_leaf)
                    for (int j = 0; j <= nextBrother->_size; j++)
                        nextBrother->_children[j] = nextBrother->_children[j+1];
            } else if (nextBrother) {    // case 3b: combine child[i] and child[i+1]
                combine(node, i);
            } else {                    // case 3b: combine child[i-1] and child[i]
                i--;
                combine(node, i);
            }
        }
        remove(node->_children[i], key);
    }
}

算法笔记:B树

随着删除不断进行,会出现根节点变为空的情况,这时候需要把空的根节点删除。如果B树中的元素被全部删除,那么需要重新创建一个根节点。由于删除过程会改变B树结构,需要再删除前检查关键字是否存在。

void remove(const Key &key)
{
    if (find(root, key))
        remove(root, key);
    if (root->_size == 0)
        root = root->_children[0];
    if (root == nullptr) {
        root = std::make_shared<Node>();
        root->_leaf = true;
        root->_size = 0;
    }
}
收藏
评论区

相关推荐

c语言中static 用法
static在c里面可以用来修饰变量,也可以用来修饰函数。 先看用来修饰变量的时候。变量在c里面可分为存在全局数据区、栈和堆里。其实我们平时所说的堆栈是栈而不是堆,不要弄混。 c int a ; int main() { int b ; int c (int )malloc(sizeof(int)); } a是全局变量,b是栈变
JavaScript 中的二叉树以及二叉搜索树的实现及应用
接下来让我们一起来探讨js数据结构中的树。这里的树类比现实生活中的树,有树干,树枝,在程序中树是一种数据结构,对于存储需要快速查找的数据非有用,它是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点以及零个或多个子节点。如下所以为一个树结构:) (https://imghelloworld.osscnbe
数据库系统概论
一、范式与规范 1.1 一个二元组一定属于BCNF eg: R {A, B, C},{B C, BA } 等价于{B AC} 1.2 求候选码 1. 列出左右出现的元素:L, R, LR,N。(当右边出现组合元素时,拆分开来) 1. 从(L N) 中的元素开始求闭包,能推出所有元素则一定是唯一的候选码。 1. 如果L中的闭包推不出
Object.keys()详解
Object.keys():遍历对象的所有属性,该方法返回一个数组,数组内容就是对象的所有键名。 传入对象,返回属性名 var obj {'a':'meng','b':'lin'} console.log(Object.keys(obj)); // 'a','b' var obj{ 100: "a", 2: "b", 7: "c"}; cons
统计字符串中字符出现的次数(Python版)
字符串转list python s 'aabbccd' list1 list(s) 方法一: python list1 'a', 'a', 'b', 'c', 'c', 'c', 'c' dict_cnt {} for value in list1: dict_cntvalue dict_cnt.get(value,
彻底搞懂系列B-树、B+树、B-树、B*树
(https://blog.csdn.net/chai471793/article/details/99563704)平衡二叉树 概念 平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构; 特点 平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索,大大
算法笔记:红黑树
红黑树,一种平衡二叉树,最为著名的应用就是C STL中的map,是有序集合最为理想的存储方式之一。除了二叉树所具有的属性之后,红黑树中每个节点多了一个“颜色”属性,可以是红色或者是黑色。一棵红黑树应该满足一下的性质: 1. 每个节点是红色或者黑色的; 2. 根节点是黑色的; 3. 每个叶节点nil是黑色的(使用哨兵节点在删除调整时可以方便不少); 4. 如
算法笔记:B树
B树广泛应用于各种文件系统,文件系统中,数据都是按照数据块来进行读取操作。结合二叉树的优点和文件系统的特点,于是就有了B树: btree(https://imghelloworld.osscnbeijing.aliyuncs.com/imgs/ae3caa193bc4c55f0519114b15313721.png) B树当中每个节点存储
Flutter/Dart - Dart中一个类实现多个接口 以及Dart中的Mixins
Dart中implements实现多个接口 abstract class A { String name; printA(); } abstract class B { printB(); } class C implements A,B{ @override String name;
二叉树题集(持续更新中)
对于二叉搜索树,我们规定任一结点的左子树仅包含严格小于该结点的键值,而其右子树包含大于或等于该结点的键值。 1\. 求二叉搜索树最大深度输入格式:输入给出一行整数序列作为二叉搜索树的键值,数字间以空格分隔,输入0结束(0不计入该二叉树键值)。输入样例:8 6 8 5 10 9 11 0输出样例:4常规的求二叉搜索树深度的做法是递
Dart中一个类实现多个接口以及Dart中的 Mixins
一、Dart中一个类实现多个接口 abstract class A{ String name; printA(); } abstract class B{ printB(); } class C implements A,B{
js实现二叉树、二叉查找树
树是一种数据结构,该章节讨论二叉树(二叉树的每个节点的子节点不允许超过两个),二叉树中有又分为完全二叉树和不完全二叉树..... 不在本章节赘述相关概念,感兴趣可以去查阅《数据结构》。 你将会获得: 1.如何使用js实现二叉查找树。 2.学会前、中、后序遍历。 3.了解相关实现原理 阅读时长5min,可选择直接调试代码 特点    二叉查找树中序遍历后
动图图解二叉查找树的基本原理及其实现
本文为系列专题的第 12 篇文章。1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 1. 是什么?二叉查找树(Binary Search Tree)必须满足以下特点: 若左子树不为空,则左子树的所有结点值皆小于根结点值 若右子树不为空,则右子树的所有结点值皆大于根结点值 左右子树也是二叉排序树如下图,是一颗二叉查找树:如果你对二叉查找树进行中序
面试官突击一问:深入理解mysql技术
京东Java研发岗一面(基础面,约1小时) 自我介绍,主要讲讲做了什么和擅长什么 springmvc和springboot区别 @Autowired的实现原理 Bean的默认作用范围是什么?其他的作用范围? 索引是什么概念有什么作用?MySQL里主要有哪些索引结构?哈希索引和B+树索引比较? Java线程池的原理?线程池有哪些?线程池
高级java面试题,附答案+考点
蚂蚁金服一面1. 两分钟的自我介绍2. 二叉搜索树和平衡二叉树有什么关系,强平衡二叉树(AVL 树)和弱平衡二叉树 (红黑树)有什么区别3. B 树和 B+树的区别,为什么 MySQL 要使用 B+树4. HashMap 如何解决 Hash 冲突5. epoll 和 poll 的区别,及其应用场景6. 简述线程池原理,FixedThreadPoo

热门文章

分布式系统基石:Paxos算法笔记:红黑树

最新文章

算法笔记:红黑树分布式系统基石:Paxos