MySQL之B-tree学习

一，B tree定义：
B-树是一种平衡的多路查找树，它在文件系统中很有用，一棵m阶B树满足下列性质：
1，节点：
a，每个节点最多可以有m个子节点
b，根节点若非叶子节点，至少2个子节点，最多m个子节点
c，每个非根，非叶子节点至少[m/2]子节点或叫子树([]表示向上取整)，最多m个子节点

2，关键字：
a，根节点的关键字个数1~m-1
b，非根非叶子节点的关键字个数[m/2]-1~m-1

3、所有的叶子结点都位于同一层

4、每个结点中关键字从小到大排列

5，叶子结点不包含关键字

6，性能分析：
设B-树包含N个关键字，因此有N+1个叶子结点，叶子都在第L层。因为根至少有两个孩子，因此第二层至少有2个结点。除根和叶子外，其它结点至少有┌m/2┐个孩子，因此在第三层至少有2┌m/2┐个结点，在第四层至少有2(┌m/2┐^{2)个结点，．．．，在第L层至少有2*(┌m/2┐}(L-2) )个结点，于是有：
N+1 ≥ 2*┌m/2┐^(L-2)
即： L ≤ log┌m/2┐((N+1)/2 )+2
这个公式保证了B-树的查找效率是相当高的。

如果要计算数据检索时间复杂度的话，还得考虑每个节点进行关键字的查找（二分法）

一般数据库采用的是b-tree的变体：b+tree
和b-tree相比，区别在于：
1，每个节点关键字个数和子节点个数相等。
2，b+tree的每个非叶子节点只有key，没有data，而且叶子节点没有指针。
一般数据库会对b+tree进行优化，比如在叶子节点上增加了顺序访问指针，提高区间查询效率。