B树与B+树

一、内存与磁盘

1. 区别
   内存：速度快，断电以后数据消失
   磁盘：速度慢，数据持久存储
2. 大小
   CPU < 内存 < 磁盘
   CPU可以通过CPU指令访问内存，但不可以访问磁盘

二、B树
特征：多叉树，叉的个数不限，是平衡的

性质：
一棵M阶B树，满足以下条件
B树是一棵多路平衡的查找树，每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中所有关键字都小于它，右子树中的所有关键字都大于它。
1）每个结点至多拥有M棵子树 （结点有5个元素/关键字，最多拥有6棵子树）
2）根结点至少拥有两棵子树
3）除了根节点以外，其余每个分支结点至少拥有M/2棵子树
4）所有的叶结点都在同一层上
5）有k棵子树的分支结点存在k-1个关键字，关键字按照递增顺序进行排序
6）关键字数量满足ceil(M/2)-1<=M-1
ceil 是向上取整，最后结果比原数据大（eg，ceil(1.2)=2; ceil(-1.3)=-1）

用代码表示B树的一个结点

typedef int KEY_VALUE;
struct btree_node {
	KEY_VALUE* keys; // 通过malloc来创建结点
	struct btree_node** childrens; // 多个子结点
	
	int num; // 每个结点中元素个数
	int leaf; // 是否是叶子结点 bool
};