彻底搞定篇–B+Tree（1）
- 2019 年 10 月 5 日
- 筆記
对话
老王：最近怎么没精打采的呢？
小王：最近面试卡住了，B+ tree 没回答上来
老王：不对呀，你不早就学过吗，经典教程都写这呢？
小王：别提啦，当时脑中一片空白。
当时情况是这样的！
大王：谈谈你对B+ tree理解？
小王：这个我知道，就是数据全部存储到叶子节点上，在同一层次 ！
大王；然后呢。。。。
小王：支支吾吾 说不上来了。
大王：还有没有补充的
小王：查询效率很高。
大王：怎么查询的？
小王：。。。。。。。
大王：过，就到这里。
老王：我来讲一讲
（老王） 我演示一下如何查找
- 查找元素6
- 查找元素12
- 查找元素17 （慢速）
（小王）我知道如何查找了
查询tree_search (k, root) 逻辑
- 如果root为null，直接返回查询失败。
- 如果是root是叶子节点，if k=ki，返回查找成功，不然就失败。
- root 如果是非叶子节点。 循环遍历 如果 k <key1
从对应子树 继续寻找tree_search (k, root.1.child) 递归遍历
- 循环遍历结束。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位置这个key进行拆分到paernt节点上去。
- 继续对父节点做做平衡检查。如果超过上界，选择中间元素+1位置这个key进行拆分到paernt节点上去
- 重复步骤 3
（老王）请看下面删除演示
删除元素 5
删除元素 7
7.gif
（小王）这个有点复杂，需要借助相邻的元素，这个操作我描述不出来
基本分为三个步骤
- 从叶子节点查询到该元素，然后删除
- 判断是是否低于最低数量，从该节点借一个记录代替自己。如果没有从邻居借去一个代替自己
- 重复步骤 2
但是漏洞很多，无法具体描述。开始支支吾吾了
(老王) 你说对，这个情况比较复杂。未完待续
最后，小王偷偷写下这么几句话
B+ tree 是一个 M 阶平衡搜索树 （Balanced multiway search trees）
- 为了维持平衡，每个非叶子节点中子树个数上下界：M/2<=x <<M。也就是说 每个结点最多有m-1个关键字
- 每次对叶子节点 中key的 插入，删除等操作会引起关键字超过上下界，因此需要继续进行拆分或者合并操作。
- 因为全部信息都存储到叶子节点，这就为什么每次查询，插入，删除等操从找到叶子节点开始。
哈哈哈
你一已经猜到 一个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章
