PHP数据结构（十六） ——B树
PHP数据结构（十六）——B树
（原创内容，转载请注明来源，谢谢）
一、概述
B树在很多地方被称为“B-树”，因为B树的原英文名称为B-tree，很多人把其译作B-树，但是它的正确读法是B树，因此下面都用B树来表示B-tree。B树是一种多路平衡查找树，其对于加快查找速度具有重要意义。
1、定义
一棵m阶的B树（不是指m叉树，m是这棵树的度，下同），或者是空树，或者是满足下列特性的m叉树：
1）树中每个节点至多m个子树，m-1个关键字。
2）根节点若不是叶子节点，至少要有2棵子树，最多m棵子树。
3）除根节点和叶子节点以外，其余节点至少要有m/2棵子树，最多m棵子树。
4）所有叶子节点在同一层。
5）所有非叶子节点，包含信息（n,a0,k1,a1,k2..kn,an），ki(i=1..n)为关键字，且ki<k(i+1)。ai(i=0..n)为指向子树根节点的指针，a(i-1)所指子树节点关键字小于ki，an所指子树的所有节点大于kn，n表示本节点关键字的个数。即每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
6）每个节点有多个值时，按从小到大（或从大到小）的顺序排列。
7）决定查找速度的关键因素，在于节点在B树的层次数。
8）阶的含义：一棵树的最小度树即这个数的阶。
2、图
B树如下图所示：(图来自网络)
上图中，黄色和灰色方块的P表示指针，蓝色方块的数字表示值。可以看出，这种树比较特殊，每个节点不一定只有一值，而指针更不止一个。拿第一行的根节点为例，P1表示指向的子树以及子树的所有子树的数字均小于17，P2表示在17-35之间（不含），P3表示大于35。
3、特性
1）关键字分布在整个树中，如果在非叶子节点查找到结果，则搜索在非叶子节点结束（与B+树的很大的一个区别）。
2）任何一个关键字只出现在一个节点中，即对B树插入关键字时，如果关键字存在，则插入失败。
3）搜索性能等同于二分法查找。
4）B树是一种特殊的平衡二叉树，因此B树在进行插入和删除操作时，也会自动调整，保证插入或者删除后的树仍满足B树的全部规定。
二、查找
B树的查找类似二分法，查找方法如下：
1）先在根节点进行比较，如果有对应的则返回结果。
2）如果没有，则根据比较的结果，当小于第一个数，则去第一个指针指向的子树进行查找；大于最后一个树，则去最后一个指针指向的树进行查找；否则，当大于i-1位置的关键字、小于第i位置的关键字，则在第i个指针所指的子树进行查找。
3）重复1、2两步，直到找到关键字，或子树为null。
编程实现B树的查找，主要需要以下内容：
1）输入B树的根节点以及需要查找的关键字。
2）在根节点中查找是否有满足条件的关键字，有则返回关键字对应的内容，否则根据查找结果，去相应的指针所指的子节点进行比对。
3）需要注意的是，在任意一个节点进行关键字的比较时，比较出现key1<key<key2（其中key是待查找的关键字，key1和key2是节点存储的关键字），则无需继续往后比较，而是去相应的子节点进行查找。
性能分析：
B树对于加快查找速度而言，非常有意义。但是，IO操作是影响整个B树查找效率的决定因素。B树中每个结点的规模一般是一个磁盘页，而结点中所包含的关键字及其孩子的数目取决于磁盘页的大小，通常每个结点拥有的孩子数目(即结点的度数)m为50至2000不等。
下图是一个1001阶的B树（图片来自网络）：
可以看到，1001阶的B树，在第三层，已经可以容纳超过10亿的关键字。因此可以这么理解，在10亿多的关键字中查找内容，当关键字是用B树进行存储时，最多只需要进行3000次的查找，就可以确定关键字是否存在。
虽然，如果用二叉查找树来表示，只需要30次左右的查找（2的30次方约等于10亿），而由于树的每一个节点存放在磁盘的一个磁盘块中，则这30个次的查找需要影响到磁盘的30个磁盘块，而B树只会影响到3个磁盘块，每次对磁盘块的移动，时间耗费是很大的，甚至可能接近0.1s。而3000次的查找与30次的查找，对于内存而言区别极小，差距在微秒级别，和磁盘移动的次数比起来忽略不计。
但是，也不能无限增大B树的度，主要有两个原因：
1）磁盘块的空间有限，无法容纳太多的内容。
2）当节点的值太多时，会变成顺序查找，反而更降低效率。
三、插入
B树的插入主要是如下步骤：
1）插入一个元素时，首先检查该关键字在B树中是否存在，如果存在，则插入失败。
2）如果上述查找结果不存在，即在叶子结点处结束查找，然后在叶子结点中插入该新的元素。
3）如果叶子结点空间足够，这里需要向右移动该叶子结点中大于新插入关键字的元素，即保证插入后叶子节点仍是大小有序的。
4）如果节点的空间满了，以致没有足够的空间去添加新的元素，则需要将该结点进行“分裂”，将中间关键字元素上移到父结点中，上移后仍需保证父节点是大小有序的。父节点因为接收的上移的节点，则会多出一个指针，指向节点比中间关键字大的一半数量的关键字所元素分裂到新的其相邻右结点中。
5）如果父节点空间也满了，则需要分裂父节点。如果父节点是根节点，即根节点满了，则只能分裂根节点，这样会产生新的根节点，而且树的层数加一，导致树的高度增加一层。
四、删除
B树的删除主要是如下步骤：
1）首先查找B树中需删除的元素，如果不存在，删除失败。
2）如果元素存在B树，则将该元素在其结点中进行删除。
3）删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某个和被删除的元素最相近的元素到父节点中。如果没有子节点，直接删除该节点即可。
4）删除之后，如果该节点的关键字小于(m/2)-1，其中m/2的结果是进一法的结果，那还需进行节点移动操作。下列5、6两个操作只会发生其中一种，6的情况比较复杂，当发生6的情况，需要继续检查B树节点的关键字个数是否满足要求。
5）如果相邻右边的兄弟节点的关键字个数大于(m/2)-1，则将右兄弟节点最小的关键字上移到父节点，把父节点中小于此关键字的最大的那个关键字下移到刚刚删除元素的节点的最右边，以保证每个兄弟节点都满足要求。
相邻左边的节点方式类似，不再描述。需要注意的是，左右两边的兄弟节点如果都满足条件，则选关键字数目更多的那个兄弟节点，以保证相对来说的平衡。
6）如果相邻左右的兄弟节点的关键字个数都小于或等于(m/2)-1，则需要进行节点的合并。合并采用的方法是，将父节点中最接近于被删除的元素下移到被删除元素的节点中，再将节点与相应的兄弟节点进行合并。这里的相应，是由于父节点的下移，会导致相应的指针丢失，因此需要根据父节点下移的情况决定。可以理解为下移的是父节点小于被删除的元素的元素，则节点和左边兄弟合并，反之和右边合并。
7）上述6的合并情况结束后，由于父节点少了一个元素，则需要检查父节点是否满足要求，不满足的话，需要父节点和父节点的兄弟节点进行5或6的操作。如果父节点是根节点，则合并后，B树少了一层。
五、好的文章
B树的概念在数据结构中相对复杂，而又很重要，我也是查看大量资料学习来的。主要有数据结构的书，以及网络上的博客，在此分享两篇觉得写的很好的博客。
http://blog.csdn.net/v_JULY_v/article/details/6530142/
http://blog.csdn.net/acs713/article/details/6880375
——written by linhxx 2017.07.16