B树系列文章
1. B树-介绍
2. B树-查找
3. B树-插入
4. B树-删除
什么是B树
B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。
使用B树这种数据结构，可以在 对数时间范围内完成对数据的查找、插入和删除操作。
B树减少定位记录时所经历的中间过程，从而加快存取速度。
因此B树可应用于数据库和文件系统的实现
B树有什么特性
一棵m阶B树有如下属性(m >= 2)
- 每一个结点最多有m个子结点
- 每一个非叶子结点（除根结点）最少有 ⌈ m/2⌉ 个子结点
- 如果根结点不是叶子结点，那么它至少有两个子结点
- 有k个子结点的非叶子结点拥有 k − 1 个键
- 所有的叶子结点都在同一层
- 结点内键值有序排列，
- 以父结点中某个键作为分隔值，该分隔值与左右儿子结点的键值的构成排列也是有序的
下图是一棵3阶B树，
取该B树父结点中某个键作为分隔值
该分隔值的左儿子结点的键值均小于该分隔值，右儿子结点的键值均大于该分隔值
图一 3阶B树
根据B树的定义及特性，定义B树结点的基本数据结构，这里多加了一个限制，即 键不会重复
每个B树结点都包含了键值列表和儿子结点列表，默认键值按升序排列
// 非并发安全
type BTree struct {
m int // 阶数
root *BTreeNode
}
type BTreeNode struct {
isLeaf bool // 是否为叶子结点
keyNum int // key个数
keyList []int // key 有序
leafList []*BTreeNode
}
完整代码
参考
Original: https://www.cnblogs.com/amos01/p/16488667.html
Author: Amos01
Title: B树详解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/611210/
转载文章受原作者版权保护。转载请注明原作者出处！