彻底搞定篇--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章