专栏首页JetpropelledSnakeSQL学习笔记之B+树的几点总结

SQL学习笔记之B+树的几点总结

本文主要以列表形式将B+树的特点以及注意点等列出来,主要参考《算法导论》、维基百科、各大博客的内容,结合自己的理解写的,如内容有不当之处,请各位雅正。

0x00 前言

B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。B树类似于红黑树,但它们在降低磁盘I/O操作数方面要更好一些。现在许多数据库系统使用B树或者B树的变种(B+树和B*树)来存储信息。B树用的比较普遍,许多书籍、博客都有详细的介绍,对于B树的严格定义也相对统一,在这里就不予赘述。 B+树是B树的一种变形,它把所有的卫星数据都存储在叶节点中,内部节点只存放关键字和孩子指针,因此最大化了内部节点的分支因子,所以B+树的遍历也更加高效(B树需要以中序的方式遍历节点,而B+树只需把所有叶子节点串成链表就可以从头到尾遍历)。 以下先放一张我所依据的B+树的图示(这张图有所简化,下面讲完定义后会贴一张更加详细的图,两图本质并无差异):

0x01 定义

B+树的定义我没有找到官方的定义(如果有找到的人望告知我),有些定义在论坛还有争议,但是这些并没有多大影响,只是一点小小的差异,下面的定义中有涉及争议的部分我会提及。

B+树的定义如下:

每个节点node有下面的属性: n个关键字key[1],key[2], … ,key[n],以非降序存放,使得key[1]≤key[2]≤…≤key[n]; isRoot,一个布尔值,如果node是根节点,则为TRUE;否则为FALSE; isLeaf,一个布尔值,如果node是叶子节点,则为TRUE;否则为FALSE; Node*类型的parent指针,指向该节点的父节点 每个内部节点还包含n个 指向其孩子children[0],children[1], … , children[n],叶子节点没有孩子。(注:此处有争议,B+树到底是与B 树n-1个关键字有n棵子树保持一致,还是B+树n个关键字的结点中含有n棵子树;两种定义都可以,只要自己实现的时候统一用一种就行。如无特殊说明,以下的都是后者:即n个关键字对应n棵子树); 内部节点的关键字对存储在各子树中的关键字范围加以分割:如果key[i]为任意一个存储在内部节点中的关键字,childNum[i]为该节点的对应下标的子树指针指向的节点的任意一个关键字,那么 key[1] ≤ childNum[1] < key[2] ≤ childNum[2] < key[3] ≤ childNum[3] < … < key[n] ≤ childNum[n] 内部节点并不存储真正的信息,而是保存其叶子节点的最小值作为索引。比如下图,标注1和标注2都是内部节点,里面保存的并不是真正的信息,而是标注3所示的节点中的最小值。(注:此处有争议以最大值作为索引,同样也是不影响的争议) 

任何和关键字相联系的“卫星数据(satellite information)” 将与关键字一样存放在叶子节点中,一般地,可能只是为每个关键字对应的”卫星数据”存放一个指针,指针指向存放实际数据的磁盘页,匹配了某个叶子节点的关键字即可通过该指针找到其他对应数据。 每个叶子节点还有指向下一个节点的指针next,方便遍历整棵B+树。 每个叶子节点具有相同的深度,即树的高度h。 每个节点所包含的关键字个数有上界和下界,用一个被B+树的最小度数(minmum degree)的固定整数t≥2来表示这些界: 除了根节点以外的每个节点必须至少有t个关键字。因此,除了根节点以外的每个内部节点至少有t个孩子 每个节点至多有2t个关键字,因此,一个内部节点至多可有2t个孩子。当一个节点恰好有2t个关键字时,称该节点是满的结合以上的具体定义,下面这张图更加详细的描述了一棵具体的B+树

0x02 注意点

在B+树的学习与实现过程中,也遇到不少的疑惑之处,现记录如下,持续更新: 内部节点并不存储真正的信息,而是保存其叶子节点的最小值作为索引。每次插入删除都进行更新(此时用到parent指针),保持最新状态。 关于所有叶子节点都处于同一深度是如何实现的?这与B+树具体的插入和删除算法有关。简单解释一下插入时的情况,根据插入值的大小,逐步向下直到对应的叶子节点。如果叶子节点关键字个数小于2t,则直接插入值或者更新卫星数据;如果插入之前叶子节点已经满了,则分裂该叶子节点成两半,并把中间值提上到父节点的关键字中,如果这导致父节点满了的话,则把该父节点分裂,如此递归向上。所以树高是一层层的增加的,叶子节点永远都在同一深度。下面是我实现的B+树中的插入代码的片段:

public void insert(Comparable key, Object obj, BPlusTree tree)
{
    // 叶子节点则插入
    if (isLeaf) {
        // 不需要分裂直接插入
        if (containsKeyword(key) || keywords.size() < tree.getDegree()) {
            insertInNotFull(key, obj);
            // 直接插入
            if (parent != null) {
                parent.updateAfterInsert(tree);     // 更新父节点的信息(将最小的值存到父节点的关键字中作为索引)
            }
        } else {    // 需要分裂成左右两个节点
            splitNode(key, obj, tree);
        }
    } else {        // 如果不是叶子节点则继续往下搜索
        Node leafNode = downToLeaf(key); // 逐步向下到对应的叶子节点
        leafNode.insert(key, obj, tree);
    }
}

0x03 结语

B+树还有一个最大的好处,方便扫库,B树必须用中序遍历的方法按序扫库,而B+树直接从叶子结点挨个扫一遍就完了,B+树支持range-query非常方便,而B树不支持。这是数据库选用B+树的最主要原因。 欢迎各位大牛批评指正。PS:我实现了一个小型B+树系统,使用Java写的,支持插入、搜索、遍历B+树,有需要的同学可以去下载。链接奉上:B+树实现(Java源码)

参考文献 [1].《算法导论》原书第3版中文版 [2]. 维基百科B+树条目 [3]. 很详细的一篇B树、B+树、R树的博客 [4]. 数据库实现的扼要说明

参考

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • SQL学习笔记之B+树

    任意节点,它的左子树如果不为空,那么左子树上所有节点的值都小于根节点的值; 任意节点,他的右子树如果不为空,那么右子树上的所有节点的值大于根节点的值。

    Jetpropelledsnake21
  • Linux学习笔记之Redis单机,伪集群,Sentinel主从复制的安装和配置

     Redis是一款开源的、高性能的键-值存储(key-value store)。它常被称作是一款数据结构服务器(data structure server)。

    Jetpropelledsnake21
  • SNMP学习笔记之SNMPv3的配置和认证以及TroubleShooting

    snmp v3安全级别有三种,分别为noAuthNoPriv(不认证也不加密)、authNoPriv(认证但是不加密)、authPriv(既认证又加密)

    Jetpropelledsnake21
  • 【深入学习MySQL】MySQL的索引结构为什么使用B+树?

    在MySQL中,无论是Innodb还是MyIsam,都使用了B+树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始,逐步说明各种树解决...

    Java_老男孩
  • 每日一题 | 解一个复杂的方程

    拜占庭将军问题是由著名的计算机大神图灵奖获得者兰伯特提出来的非常有名的问题,我们把这个问题外面包着的故事背景去除,实际上的内涵其实围绕的是分布式系统当中的一致性...

    TechFlow-承志
  • ES[7.6.x]学习笔记(二)ES的集群原理 ## 发现

    发现是节点之间彼此发现,形成集群的一个过程。这个过程发生的场景有很多,比如:你启动了一个集群节点,或者一个节点确认主节点已经挂掉了,或者一个新的主节点被选举了。

    小忽悠
  • MongoDB 事务 — 基础入门篇

    MongoDB 单文档原生支持原子性,也具备事务的特性,但是我们说起事务,通常是指在多文档中的实现,因此,MongoDB 在 4.0 版本支持了多文档事务,4....

    五月君
  • Stowaway:一款专为渗透测试人员设计的多级代理工具

    Stowaway是一款采用Go语言开发的多级代理工具,该工具专为渗透测试人员设计,广大用户可以使用该工具将外部流量通过多个节点代理至内网,并实现自定义管理功能。...

    FB客服
  • 动画 | 什么是红黑树?(与2-3-4树等价)

    二分搜索树是为了快速查找而生,它是一颗二叉树,每一个节点只有一个元素(值或键值对),左子树所有节点的值均小于父节点的值,右子树所有的值均大于父节点的值,左右子树...

    我脱下短袖
  • 数据结构之红黑树

      红黑树和红色和黑色这两种颜色有关,事实上,在红黑树中,对每一个节点都附着一个颜色,或者是红色或者是黑色。红黑树首先是一棵二分搜索树,这一点和AVL树是一样的...

    别先生

扫码关注云+社区

领取腾讯云代金券