【数据结构】B树-EW帮帮网

B-树概念

1970年，R.Bayer和E.mccreight提出了一种适合外查找的树，它是一种平衡的多叉树，称为B树

后面介绍一个B的改进版本B+树，然后有些地方的B树写的的是B-树，注意不要误读成“B减树”。

一棵m阶（m>2）的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：

根节点至少有两个孩子
每个分支节点都包含k - 1个关键字和k个孩子，其中ceil(m/2) ≤ k ≤ m （ ceil是向上取整函数）
每个叶子节点都包含k - 1个关键字，其中ceil(m/2) ≤ k ≤ m
所有的叶子节点都在同一层
每个节点中的关键字从小到大排列，节点当中k - 1个元素正好是k个孩子包含的元素的值域划分
每个结点的结构为：（n，A₀，K₁，A₁，K₂，A₂，… ，K_n，A_n）其中，K_i(1≤i≤n)为关键字，且K_i<K~i + 1~(1≤i≤n - 1)。A_i(0≤i≤n)为指向子树根结点的指针。且A_i所指子树所有结点中的关键字均小于K_i + 1。
n为结点中关键字的个数，满足ceil(m/2)-1≤n≤m - 1。

B-树插入

插入操作是指插入一条记录，即（key, value）的键值对。

如果B树中已存在需要插入的键值对，则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。

根据要插入的key的值，找到叶子结点并插入。
判断当前结点key的个数是否小于等于m-1，若满足则结束，否则进行第3步。
以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入到父结点中，这个key的左子树指向分裂后的左半部分，这个key的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第3步。（当阶数m为偶数时，需要分裂时就不存在排序恰好在中间的key，那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。）

示例

以5阶B树为例，介绍B树的插入操作，

根B定义规则2（至少有Math.ceil(m/2)-1个关键字），在5阶B树中，结点最多有4个key，最少有2个key。

在空树中插入39
继续插入22、97、41
继续插入53

插入后超过了最大允许的关键字个数4，所以以key值为41为中心进行分裂，结果如下图所示，分裂后当前结点指针指向父结点，满足B树条件，插入操作结束。

当阶数m为偶数时，需要分裂时就不存在排序恰好在中间的key，那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。

在这里插入图片描述

依次插入13、21、40

同样会造成分裂，结果如下图所示
依次插入30、27、 33 、36、35、34、 24、29
插入26
当前结点需要以27为中心分裂，并向父结点进位27，然后当前结点指向父结点，结果如下图所示

进位后导致当前结点（即根结点）也需要分裂，分裂的结果如下图所示

总结

如果树为空，直接插入新节点中，该节点为树的根节点
树非空，找待插入元素在树中的插入位置(注意：找到的插入节点位置一定在叶子节点中)
检测是否找到插入位置(假设树中的key唯一，即该元素已经存在时则不插入)
按照插入排序的思想将该元素插入到找到的节点中
检测该节点是否满足B-树的性质：即该节点中的元素个数是否等于M，如果小于则满足
如果插入后节点不满足B树的性质，需要对该节点进行分裂：
- 申请新节点
- 找到该节点的中间位置
- 将该节点中间位置右侧的元素以及其孩子搬移到新节点中
- 将中间位置元素以及新节点往该节点的双亲节点中插入，即继续步骤4
如果向上已经分裂到根节点的位置，插入结束

代码实现

B-树的节点设计

// M叉树：即一个节点最多有M个孩子，M-1个数据域
// 为实现简单期间，数据域与孩子与多增加一个(原因参见上文对插入过程的分析)
template<class K, int M = 3>
struct BTreeNode
{
    K _keys[M]; // 存放元素
    BTreeNode<K, M>* _pSub[M + 1]; // 存放孩子节点，注意：孩子比数据多一个
    BTreeNode<K, M>* _pParent; // 在分裂节点后可能需要继续向上插入，为实现简单增加parent域
    size_t _size; // 节点中有效元素的个数

    BTreeNode()
        : _pParent(NULL)
       , _size(0)
    {
        for (size_t i = 0; i <= M; ++i)
            _pSub[i] = NULL;
    }
};

查找节点

std::pair<Node *, int> Find(const K &key)
    {
        Node *parent = nullptr;
        Node *cur = _root;

        while (cur)
        {
            // 在一个节点查找
            size_t i = 0;
            while (i < cur->_n)
            {
                if (key < cur->_keys[i])
                {
                    break;
                }
                else if (key > cur->_keys[i])
                {
                    ++i;
                }
                else
                {
                    return make_pair(cur, i);
                }
            }

            // 往孩子去跳
            parent = cur;
            cur = cur->_subs[i];
        }

        return make_pair(parent, -1);
    }

插入key

按照插入排序的思想插入key，注意：在插入key的同时，可能还要插入新分裂出来的节点。

void _Insertkey(PNode pCur, const K& key, PNode pSub)
{
    // 按照插入排序思想插入key
    int end = pCur->_size - 1;
    while (end >= 0)
    {
        if (key < pCur->_keys[end])
        {
            // 将该位置元素以及其右侧孩子往右搬移一个位置
            pCur->_keys[end + 1] = pCur->_keys[end];
            pCur->_pSub[end + 2] = pCur->_pSub[end + 1];
            end--;
        }
        else
        {
            break;
        }
    }

    // 插入key以及新分裂出的节点
    pCur->_keys[end + 1] = key;
    pCur->_pSub[end + 2] = pSub;

    // 更新节点的双亲
    if (pSub)
        pSub->_pParent = pCur;

    pCur->_size++;
}

插入实现

bool Insert(const K& key)
{
    // 如果树为空，直接插入
    if (NULL == _pRoot)
    {
        _pRoot = new Node();
        _pRoot->_keys[0] = key;
        _pRoot->_size = 1;
        return true;
    }

    // 找插入位置，如果该元素已经存在，则不插入
    pair<PNode, int> ret = Find(key);
    if (-1 != ret.second)
        return false;

    K k = key;
    PNode temp = NULL;
    PNode pCur = ret.first;
    
    while (true)
    {
        // 将key插入到pCur所指向的节点中
        _Insertkey(pCur, k, temp);

        // 检测该节点是否满足B-树的性质，如果满足则插入成功返回，否则，对pCur节点进行分裂
        if (pCur->_size < M)
            return true;

        // 申请新节点
        temp = new Node;

        // 找到pCur节点的中间位置
        // 将中间位置右侧的元素以及孩子搬移到新节点中
        int mid = (M >> 1);
        for (size_t i = mid + 1; i < pCur->_size; ++i)
        {
            temp->_keys[temp->_size] = pCur->_keys[i];
            temp->_pSub[temp->_size++] = pCur->_pSub[i];

            // 跟新孩子节点的双亲
            if (pCur->_pSub[i])
                pCur->_pSub[i]->_pParent = temp;
        }

        // 注意：孩子比关键字多搬移一个
        temp->_pSub[temp->_size] = pCur->_pSub[pCur->_size];
        if (pCur->_pSub[pCur->_size])
            pCur->_pSub[pCur->_size]->_pParent = temp;

        // 更新pCur节点的剩余数据个数
        pCur->_size -= (temp->_size + 1);

        // 如果分裂的节点为根节点，重新申请一个新的根节点，将中间位置数据以及分裂出的新节点插入到新的根节点中，插入结束
        if (pCur == _pRoot)
        {
            _pRoot = new Node;
            _pRoot->_keys[0] = pCur->_keys[mid];
            _pRoot->_pSub[0] = pCur;
            _pRoot->_pSub[1] = temp;
            _pRoot->_size = 1;
            pCur->_pParent = temp->_pParent = _pRoot;
            return true;
        }
        else
        {
            // 如果分裂的节点不是根节点，将中间位置数据以及新分裂出的节点继续向pCur的双亲中进行插入
            k = pCur->_keys[mid];
            pCur = pCur->_pParent;
        }
    }

    return true;
}

B-树性能分析

对于一棵节点为N度为M的B-树，查找和插入需要 $log_{(M - 1)}N$ ~ $log_{(M/2)}N$ 次比较，这个很好证明：对于度为M的B-树，每一个节点的子节点个数为M/2 ~ (M - 1)之间，因此树的高度应该在要 $log_{(M - 1)}N$ 和 $log_{(M/2)}N$ 之间，在定位到该节点后，再采用二分查找的方式可以很快的定位到该元素。

B-树的效率是很高的，对于N = 62*100000000个节点，如果度M为1024，则 $log_{(M/2)}N$ <= 4，即在620亿个元素中，如果这棵树的度为1024，则需要小于4次即可定位到该节点，然后利用二分查找可以快速定位到该元素，大大减少了读取磁盘的次数。

B-树的删除

删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步
该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。
如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。

否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。

有些结点它可能即有左兄弟，又有右兄弟，那么我们任意选择一个兄弟结点进行操作即

B+树

B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了以下几点改进优化：

分支节点的子树指针与关键字个数相同
分支节点的子树指针p[i]指向关键字值大小在[k[i], k[i + 1])区间之间
所有叶子节点增加一个链接指针链接在一起
所有关键字及其映射数据都在叶子节点出现

B+树的特性：

所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。
不可能在分支节点中命中。
分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层。

B+树的分裂：
当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

B*树

B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。

B*树的分裂：
当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

总结

通过以上介绍，大致将B树，B+树，B树总结如下：
B树：有序数组+平衡多叉树；
B+树：有序数组链表+平衡多叉树；
B树：一棵更丰满的，空间利用率更高的B+树。

B-树的应用

索引

B-树最常见的应用就是用来做索引。

索引通俗的说就是为了方便用户快速找到所寻之物，比如：书籍目录可以让读者快速找到相关信息，hao123网页导航网站，为了让用户能够快速的找到有价值的分类网站，本质上就是互联网页面中的索引结构。

MySQL官方对索引的定义为：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说：索引就是数据结构。

当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，该数据结构就是索引。

MyISAM

MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎，不支持事物，支持全文检索，使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址，其结构如下：

在这里插入图片描述
上图是以以Col1为主键，MyISAM的示意图，可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果想在Col2上建立一个辅助索引，则此索引的结构如下图所示：
在这里插入图片描述
同样也是一棵B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”的。

InnoDB

InnoDB存储引擎支持事务，其设计目标主要面向在线事务处理的应用，从MySQL数据库5.5.8版本开始，InnoDB存储引擎是默认的存储引擎。

InnoDB支持B+树索引、全文索引、哈希索引。但InnoDB使用B+Tree作为索引结构时，具体实现方式却与MyISAM截然不同。

第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而InnoDB索引，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

在这里插入图片描述
上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录，这种索引叫做聚集索引。

因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

第二个区别是InnoDB的辅助索引data域存储相应记录主键的值而不是地址,所有辅助索引都引用主键作为data域。

在这里插入图片描述
聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

【数据结构】B树

B-树概念

B-树插入

示例

总结

代码实现

B-树性能分析

B-树的删除

B+树

B*树

总结

B-树的应用

索引

MyISAM

InnoDB

网站公告

今日签到

热门文章

最新发布