算法笔记:B树

zhenghaoz 等级 855 1 0
标签: b树C/C++

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;
    }
}
收藏
评论区

相关推荐

彻底搞懂系列B-树、B+树、B-树、B*树
(https://blog.csdn.net/chai471793/article/details/99563704)平衡二叉树 概念 平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构; 特点 平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索,大大
算法笔记:B树
B树广泛应用于各种文件系统,文件系统中,数据都是按照数据块来进行读取操作。结合二叉树的优点和文件系统的特点,于是就有了B树: btree(https://imghelloworld.osscnbeijing.aliyuncs.com/imgs/ae3caa193bc4c55f0519114b15313721.png) B树当中每个节点存储
高级java面试题,附答案+考点
蚂蚁金服一面1. 两分钟的自我介绍2. 二叉搜索树和平衡二叉树有什么关系,强平衡二叉树(AVL 树)和弱平衡二叉树 (红黑树)有什么区别3. B 树和 B+树的区别,为什么 MySQL 要使用 B+树4. HashMap 如何解决 Hash 冲突5. epoll 和 poll 的区别,及其应用场景6. 简述线程池原理,FixedThreadPoo
B
B-Tree ------ B-Tree又叫做B树,和平衡二叉树不同的地方在于B树是多叉树(平衡多路查找树),Oracle和MongoDB的索引技术就是基于B树的数据结构,B树也可以看作是对2-3查找树的一种扩展。 一个m阶的B-Tree有以下性质 1. 每个节点最多有m个子节点; 2. 每个非叶子节点(根节点除外)至少含有m/2个子节点; 3.
B树C语言代码实现
在这里实现的是在主存中的操作,没有进行文件的存储和修改。 头文件btree.h: #ifndef _BTREE_H    #define _BTREE_H      #define MIN_T 3  #define MAX_T (MIN_T * 2) typedef struct BTreeNod
B树与B+树的区别?
1.B树简介 ------ B树是一种多路平衡搜索树。它由二叉树变换而来的。定义如下: 1.1每个节点最多有m-1个关键字 1.2根节点最少有1个关键字 1.3非根节点至少有m/2个关键字 1.4每个节点的关键字都是按照从小到大的顺序排列,每个关键字的左子树中的关键字都小于它,而右子树中所有关键字都大于它。 1.5所有的叶子节点都处于同
MySQL知识体系——索引
    本文直切主题,针对InnoDB引擎描述索引及优化策略。在开始之前,需要读者了解:1)二叉查找树(包括2-3查找树、红黑树等数据结构)2)MySQL的InnoDB引擎基础知识 索引初探 ==== 要了解索引,当然要了解其数据结构。树有很多应用,流行的用法之一是包括UNIX和DOS在内的许多常用操作系统中的目录结构,二叉查找树又是Java中两种集合
MySQL索引底层:B+树详解
### 前言 当我们发现SQL执行很慢的时候,自然而然想到的就是加索引。对于范围查询,索引的底层结构就是B+树。今天我们一起来学习一下B+树哈~ 公众号:**「捡田螺的小男孩」** * 树简介、树种类 * B-树、B+树简介 * B+树插入 * B+树查找 * B+树删除 * B
MySQL索引(二)B+树在磁盘中的存储
MySQL索引(二)B+树在磁盘中的存储 ==================== 回顾 -- ![w200](https://oscimg.oschina.net/oscnet/bb8c395de7ffd25b8826c09d6cfe97ebbc0.jpg) 上一篇文章[《MySQL索引为什么要用B+树》](https://www.oschina.
MySQL调优系列——MySQL B+Tree索引和Hash索引的区别?🔥
1、B+Tree索引 ---------- ![](https://oscimg.oschina.net/oscnet/up-d956cc992de6df62c8502441583bb210ea4.png) > 1、B+Tree首先是有序结构,为了不至于树的高度太高,影响查找效率,在叶子节点上存储的不是单个数据,提高了查找效率; > > 为了更好的支持
MySQL面试(二)
1、为什么索引遵循最左匹配原则?   当B+树的数据项是符合的数据结构,比如(name,age,sex)的时候,B+树是按照从左到右的顺序建立搜索树的。比如当(张三,20,F)这样的数据来检索的时候,b+树会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据;但当(20,F)这样的没有name的数据来的时候
mysql面试题
MySQL面试 ======= 索引相关 ---- 1. **什么是索引?** 索引是一种数据结构,可以帮助我们快速的进行数据的查找. 1. **索引是个什么样的数据结构呢?** 索引的数据结构和具体存储引擎的实现有关, 在MySQL中使用较多的索引有Hash索引,B+树索引等,而我们经常使用的InnoDB存储引擎的默认索引实现为:B+树索引.
B+树原理以及Java代码实现
最初查找二叉树,由于树的高度会随着有序序列输入而急剧增长,后来出现平衡二叉树,红黑树。B树可以海量数据的快速查询检索,B树主要分为B树(B-树),B+树,B\*树等。 **B树(B-树)** M路搜索树,参数M定义节点的分支个数; 对于根节点孩子数目为\[2,M\],对于其余节点孩子数目为\[M/2,M\]; 每个节点含有关键字属性,至少M/2-1
MongoDB索引存储BTree与LSM树(转载)
**1、为什么 MongoDB 使用B-树,而不是B+树** ------------------------------ MongoDB 是一种 nosql,也存储在磁盘上,被设计用在数据模型简单,性能要求高的场合。性能要求高,我们看B-树与B+树的区别: _**B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。
Sorry!Hbase的LSM Tree就是可以为所欲为!
我们先抛出一个问题: ![file](https://oscimg.oschina.net/oscnet/up-d5d01172c006977f680f3d99ad039ce7279.png) LSM树是HBase里使用的非常有创意的一种数据结构。在有代表性的关系型数据库如MySQL、SQL Server、Oracle中,数据存储与索引的基本结构就是我们

热门文章

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

最新文章

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