B树简单笔记

B tree

B树比较简单，以前写过的最小堆、最大堆之类的，就是在堆内实现的B树，每个节点的左分叉为小于该节点值，右分叉为大于该节点值，这样就实现了快速查找。

B-Tree

首先给下定义，假设节点最多有M（M>2）个子节点，则称为M阶B-Tree，那么满足以下条件的树就是B-Tree。

1.所有节点最多有M个子节点
2.假设不是空树，根节点最少有2个子节点
3.非根节点的节点，最少有(M+1)/2个子节点，假设M=4，则最少有2个子节点
4.假设某个节点有N个节点，则该节点则有N-1个关键字
5.由（3）和（4）可知，某个节点的关键字数=节点的子节点数-1，假设该节点的关键字分别为k(1)、k(2)、k(N-1)，则必须满足k(1)>k(2)>…>k(N-1)；假设该子节点分别为c(1)、c(2)、c(N)，则假设搜索某个关键词k，该关键词满足条件k<k(1)，则子节点c(1)满足条件，假设k(1)<k<k(2)，则满足子节点c(2)，假设k满足k>k(N-1)，则满足子节点c(N)

B+Tree

B+Tree的定义和B-Tree差不多，主要有以下几点差异：

1.节点数和关键词数相同
2.比较范围不同，假设k满足条件k(1)<=k<k(2)，则k满足子节点c(1)，在c(1)中必然第一个元素是k(1) ，所以在叶子节点中，包含了全部的关键词信息
3.由于(2)，所以B-在任意的节点均可以查找完成，而B+必须得搜索到叶子节点才能完成，所以某个值假如正好是父节点的k(1)，则k(1)会不断往下传递