B树和B+树

B树的定义: 

B树是 多路 平衡 查找树. 

B树必须满足的特点: 

先上一张图: 

下图是一个3阶B树. 

m阶B树必须满足的条件:

1) 子树数量的限制: 

a)所有节点子树个数 <=m ;  

b)叶子节点很显然都没有子节点; 

c)根节点如果不是叶子节点至少要有2个子树; 否则如果是一个子树的话不可能平衡; 

d)根之外的非终端节点的子树个数 >= m/2 ; 

2) 节点的内容

a)非叶子节点中存储了节点数量,从小到大的key和各个指针;

b)叶子节点出现在同一个层次上,也就是说树的高度是绝对平衡的; 

3阶B树由于非终端节点的子树个数可能是2或者3,所以3阶B树也叫2-3树. 

B树的高度:

类比满2叉树, m阶B树的度至少是m/2, 所以 B树的高度大概是.  

B树的插入: 

1)插入的key必然在B书中不存在,所以在找插入位置时,必然会找到最底层的节点. 所以B树的插入必然是从最底层开始; 

2)B树插入的过程就是:  在最底层节点中合适的位置插入新的key, 如果插入之后不违反B树的子树约束则插入完成; 如果不满足条件则进行节点分裂,分裂的过程就是把当前节点中的keys从中间分成两部分,把中间的节点提升到父节点中,依次递归直至满足条件; 

B树节点的删除: 

分两种情况: 

1) 最底层节点上的key删除之后满足B树的要求,则删除完成; 

2)删除key之后,使用key右边的子树的最小值代替被删元素,由于右子树的最小节点肯定在B树的最底层,所以最终可以归结为删除最下层节点中key的问题,分为以下几种情况: 

 a) 删除后满足条件; OK

 b) 删除后key太少了,如果左右兄弟有富余,借来用; 

c) 删除后key太少了, 左右兄弟也没有富余, 则把被删节点剩余部分和父节点中的key合并后并入兄弟节点. 如果引起父节点key变少,则继续向上调整. 

m阶B+树和B树的区别:

1) B+树是索引树,有n棵子树的节点中含有n个关键字; 每个关键字是他的子树中的最大(最小)值; 

2)叶子节点层包含了所有的节点,并以一个链表的方式存储; 所以可以方便的顺序遍历所以的节点; 

3) 非叶子节点主要的作用是索引的作用; 非叶子节点中并不包含节点的详细指针信息; 所以遍历B+树的时候必须一直遍历到叶子节点; 不像B树一样找到既可以返回; 

4)B+树除了根节点指针通常还维护一个指向最小元素的指针;