B树
B Tree
Created 2021.04.08 by William Yu; Last modified: 2021.04.08-V1.0.2
Contact: windmillyucong@163.com
Copyleft! 2021 William Yu. Some rights reserved.
References
- https://zhuanlan.zhihu.com/p/24309634
Basic Concepts
- AVL树 红黑树 都是二叉树
- B树 的每个节点拥有2个以上的子节点
- B树是一颗多路平衡查找树
-
广泛应用于数据库检索MySQL等和文件系统中
-
阶数
- 阶数：一个节点可以拥有的最大子节点的数目
- 一个节点最多拥有n个key，那么这个节点最多拥有n+1个子节点，这棵树就叫 n+1 阶树
- Q: 为什么 +1
- A: 2叉树 有1个key，有2个子节点；3叉树有2个key，有3个子节点…
- 关系逻辑是 左1子节点 < 左1key < 左2子节点 < 中间key < 右2子节点 < 右1key < 右1子节点
-
特性
- 一个m阶B-tree 每个节点最多有m个子节点
- 除根节点和叶子节点，其它每个节点至少有 [m/2] （[]操作是向上取整数的意思）个子节点
- 如果根节点不是叶子节点，则至少有2个子节点
- 所有的NULL节点到根节点的高度都一样，平衡
- 除根节点外，其他节点都包含x个key，x满足 [m/2] -1 <= x <= m-1
节点结构
- m阶 B Tree
- 最多 m-1 个key
- 最多 m 个子节点
1
2
3
template <class T>
查找
同二叉树查找
插入
- 直接向node中插入key
- 如果node是满的，进行分裂操作
分裂操作
- node已满时，将元素插入后先排序
- 然后将中间位置的元素拿出，将左边元素分为一个node，将右边元素分裂为另一个node
- 将中间元素放入父节点中
- 如果父节点也是满的，继续对父节点进行上述操作
e.g.新插入元素900
删除
// todo
Contact
Feel free to contact me windmillyucong@163.com anytime for anything.
License
