专栏首页架构说彻底搞定篇--B+Tree(1)

彻底搞定篇--B+Tree(1)

对话

老王:最近怎么没精打采的呢?

小王:最近面试卡住了,B+ tree 没回答上来

老王:不对呀,你不早就学过吗,经典教程都写这呢?

小王:别提啦,当时脑中一片空白。

当时情况是这样的!


大王:谈谈你对B+ tree理解?

小王:这个我知道,就是数据全部存储到叶子节点上,在同一层次 !

大王;然后呢。。。。

小王:支支吾吾 说不上来了。

大王:还有没有补充的

小王:查询效率很高。

大王:怎么查询的?

小王:。。。。。。。

大王:过,就到这里。

老王:我来讲一讲

(老王) 我演示一下如何查找

  • 查找元素6
  • 查找元素12
  • 查找元素17 (慢速)

(小王)我知道如何查找了

查询tree_search (k, root) 逻辑

  1. 如果root为null,直接返回查询失败。
  2. 如果是root是叶子节点,if k=ki,返回查找成功,不然就失败。
  3. root 如果是非叶子节点。 循环遍历 如果 k <key1

从对应子树 继续寻找tree_search (k, root.1.child) 递归遍历

  1. 循环遍历结束。k 大于任何一个key。指针多一个 tree_search (k, root.last.child) 伪代码
Function: tree_search (k, node)
  if node is a leaf then
    return node;
  switch k do
  case k ≤ k_0
    return tree_search(k, p_0);
  case k_i < k ≤ k_{i+1}
    return tree_search(k, p_{i+1});
  case k_d < k
    return tree_search(k, p_{d});

小王:

我有一个疑问,查询元素12时候,明明中间元素 已经存在,为什么还要继续查询走到叶子节点才算结束, 这不是浪费时间吗?

老王:

观察很仔细呀,漫画算法:什么是 B+ 树。

程序员小灰已经给出解释了,你不是看过一次,怎么忘记了!

小王:

我确实看过,不过对里面一句话根本不明白

有K个元素,K个指针 ,一个节点对应一个指针呀, 这个不对呀,2个元素会拆分3个指针呢?

(老王) 先别急着问为什么,我演示一下插入操作

在叶子节点 (1 2 3) 上插入新元素 4 ,B tree 结果是

在叶子节点 (1 2 3) 上插入新元素 4 ,B+ tree 结果是

顺序插入元素:1 2 3 4 5 6 7 9 10 11 创建 4 阶 B+ tree 完整演示(慢速10倍)

(小王)我知道如何插入了

插入关键字k的步骤

  1. 选择到叶子节点,然后插入对应位置
  2. 对叶子节点做平衡检查,如果超过上界,选择中间元素+1位置这个key进行拆分到paernt节点上去。
  3. 继续对父节点做做平衡检查。如果超过上界,选择中间元素+1位置这个key进行拆分到paernt节点上去
  4. 重复步骤 3

(老王)请看下面删除演示

删除元素 5

删除元素 7

7.gif

(小王)这个有点复杂,需要借助相邻的元素,这个操作我描述不出来

基本分为三个步骤

  1. 从叶子节点查询到该元素,然后删除
  2. 判断是是否低于最低数量,从该节点借一个记录代替自己。如果没有从邻居借去一个代替自己
  3. 重复步骤 2

但是漏洞很多,无法具体描述。开始支支吾吾了

(老王) 你说对,这个情况比较复杂。未完待续

最后,小王偷偷写下这么几句话

B+ tree 是一个 M 阶平衡搜索树 (Balanced multiway search trees)

  1. 为了维持平衡,每个非叶子节点中子树个数上下界:M/2<=x <<M。也就是说 每个结点最多有m-1个关键字
  2. 每次对叶子节点 中key的 插入,删除等操作会引起关键字超过上下界,因此需要继续进行拆分或者合并操作。
  3. 因为全部信息都存储到叶子节点,这就为什么每次查询,插入,删除等操从找到叶子节点开始。

哈哈哈

你一已经猜到 一个4阶B+tree,一个节点最多允许 3个key,4个子树指针。

因为B+ tree 结构是递归的,我只专心看最小子问题,就是一个节点组成

typedef struct BTNode{
        int keynum;       /// 结点中关键字的个数,ceil(ORDER/2)-1<= keynum <= ORDER-1
        KeyType key[ORDER-1];         /// 关键字向量为key[0..keynum - 1]
        struct BTNode* child[ORDER];   /// 孩子指针向量为child[0..keynum]
        char isLeaf;         /// 是否是叶子节点的标志
    }BTNode;

数据结构和算法结构化

FQA

  • 一个M阶的B+tree,M是什么意思,是节点个数,还是指针个数?目前我定义来看是孩子的最大个数?
  • 每个节点 n个key和m个指针 ,n和m一定相等吗?不一定

参考

B+ treeFrom Wikipedia

MySQL索引背后的数据结构及算法原理

漫画算法:什么是 B+ 树

算法导论 18章

本文分享自微信公众号 - 架构说(JiaGouS),作者:程序员小王

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-19

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 使用虚拟节点改进的一致性哈希算法

    1 作者:@lionets 分析缺点 连接:http://my.oschina.net/lionets/blog/288066 2 作者:@糖拌咸鱼 ...

    程序员小王
  • 突破僵固型思维:如何“正确地”犯错?

    成长型思维认为人的能力是不断成长的,因此会把注意的重点放到通过努力来获得能力成长上。

    程序员小王
  • stl map key 可以被修改吗?

    stl map key 可以被修改吗 image.png 不可以修改 map节点存储key是const std::pair<const char, int>...

    程序员小王
  • 使用 tree 命令格式化输出目录结构

    今天在写一个 Markdown 文件的时候需要将一个目录的结构表示出来,于是找了找有没有相关命令,找到一个叫做 tree 的命令,Windows 和 Linux...

    Alan Lee
  • 《剑指offer》第13天:两个数组的交集

    思路:设定两个为0的指针,比较两个指针的元素是否相等。如果指针的元素相等,我们将两个指针一起向后移动,并且将相等的元素放入空白数组。

    程序员小浩
  • 如今大火的算法框架TensorFlow,都有哪些值得一看的好书呢?

    TensorFlow™是一个基于数据流编程(dataflow programming)的符号数学系统,被广泛应用于各类机器学习(machine learning...

    程序员书单
  • 干货 | React Fiber 初探

    携程技术
  • 避免这7个数据错误,让你的数据分析更有效率!

    ? 编译 Harris 本文转自机房360,转载需授权 数据正在成为现代企业的一个更重要的工具,几乎可以作为一种货币,它可以从衡量营销活动的有效性到评估员...

    CDA数据分析师
  • 开发丨TensorFlow 1.0 正式发布,你需要知道的都在这里

    谷歌表示,仅仅在发布的第一年里,TensorFlow 就帮助研究人员、工程师、艺术家、学生以及其他行业人员取得了巨大研究进展。这包括机器翻译、早期皮肤癌检测、防...

    AI科技评论
  • Google宣布TensorFlow Lite 可支持 Core ML!

    文 /TensorFlow 团队 11 月 14 日,我们宣布了 TensorFlow Lite 的开发者预览版,TensorFlow Lite 是 Tenso...

    企鹅号小编

扫码关注云+社区

领取腾讯云代金券