PHP数据结构（十九） ——B+树
PHP数据结构（十九）——B+树
（原创内容，转载请注明来源，谢谢）
一、概述
B+树是B树的变种，在数据库系统、文件系统等方面，B+树的运用非常广泛。
1、B+树的要求
1）有n棵子树的结点中含有n个关键字。（B树是n-1个关键字。）
2）所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。这点意味着，叶子节点存在指向相邻叶子节点的指针。这个是在树形的数据结构中非常特殊的地方，使得B+树的数据结构看起来有点像图的数据结构了。(B树的叶子节点没有保存父节点的信息，因此并没有包括全部需要查找的信息。)
3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。(B 树的非终节点也包含需要查找的有效信息，但是不包含和子节点相同的关键字。)
2、B+树如下图所示（图片来自网络）
3、B+树的特性
1）所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的。
2）B+树比较稳定，查询过程不可能在非叶子节点命中。
3）非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层。
4、增删改查
1）查找
B+树的查找和B树几乎一样。主要区别：
a.前面一直提到的，查找结束一定是在叶子节点，无论是否查找。但是有一个例外，当B+树的父节点的关键字数组都是存储子节点中关键字最小的值时，如果待查的关键字小于根节点的最小的值，则停止查找。因为此值已经表示整个树最小的值。因此，可以过滤掉很多无用的查找。
b.当要进行范围查找时，只需要查找最小以及最大的节点所在的位置，然后比较在此之间的各关键字即可。这是因为B+树的叶子节点之间有指针相连。
2）插入
B+树的插入，和B树不太一样，步骤如下（假设B+树的父节点是存储子节点中最小的关键字）：
a.在B+树中查找，如果关键字存在，插入失败。否则，插入在最后查找的那个叶子节点中，并且保证插入后节点的关键字仍是有序的。
下列a、b、c只会发生一种，且前提是B+树的父节点是存储子节点中最小的关键字，如果存储的是最大的关键字，则相似，不再进行赘述。
b.如果插入后，叶子节点关键字的个数满足小于m（m是父节点子树的个数），且元素大于父节点指向该元素的关键字，则插入完毕。
c.如果插入后，叶子节点关键字的个数满足小于m，且元素小于父节点指向该元素的关键字，则更新父节点的关键字为刚刚插入的这个关键字，插入完毕。
d.如果插入后，叶子节点关键字的个数满足大于m，则需要分裂叶子节点，将叶子节点按关键字的大小顺序，分裂成两个叶子节点，每个叶子节点含有的关键字数量相同。并根据分裂后的叶子节点，更新父节点指向该叶子节点的关键字。
如果父节点也超出要求，则继续分裂。如果父节点是根节点，则B+树插入后多一层。
3）删除
B+树的删除，也和B树不太一样，步骤如下（假设B+树的父节点是存储子节点中最小的关键字）：
a.在B+树中查找，如果关键字不存在，删除失败。否则，在叶子节点中删除该关键字。
下列b、c、d、e只会发生一种，且前提是B+树的父节点是存储子节点中最小的关键字，如果存储的是最大的关键字，则相似，不再进行赘述。
b.如果删除后，叶子节点关键字的个数满足大于m/2-1（m/2的结果取进一法，m是父节点子树的个数），且被删除的元素不在父节点中，则删除完毕。
c.如果删除后，叶子节点关键字的个数满足大于m/2-1，且被删除的元素在父节点中，则需要重新取被删除关键字的节点中最小的关键字，替换父节点中指向该节点的关键字。
d.如果删除后，叶子节点关键字的个数小于m/2-1，且左右相邻兄弟节点至少有一个兄弟节点满足元素个数大于m/2，则把相邻的兄弟中最小（或最大，左兄弟取最大，右兄弟取最小）的关键字移到刚刚被删除关键字的节点中，并且相应的修改父节点中的关键字的值。如果左右兄弟都满足迁移条件，则取关键字较多的那个兄弟进行迁移。
e.如果删除后，叶子节点关键字的个数小于m/2-1，且左右相邻兄弟节点都不满足元素个数大于m/2，则需要合并被删除的元素与左右兄弟节点中元素较少的节点。合并后，相应的要删除父节点的一个关键字。
如果父节点的关键字被删除后，不满足要求，则需要与相邻的父节点中的关键字较少的那一个节点合并。最终有可能出现B+树少一层的情况。
二、文件和数据库的索引采用B+树的理由
1）文件与数据库都是需要较大的存储，且需要永久性存储，不能断电就消失，因此不可能存储在内存中，故要存储到磁盘上。因此就需要考虑磁盘I/O的问题。
2）考虑到I/O问题，则需要用B树或B树的相应变种来实现。
3）B+树的内部结点并没有指向关键字具体信息的指针，因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存中的需要查找的关键字也就越多。因此，相对于B树来说，B+树的IO读写次数也就降低了。
4）B+树比较稳定。由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
5）于B+树的叶子节点之间是有指针的，因此B+树只要遍历叶子节点就可以实现整棵树的遍历（B树需要采用中序遍历的方式才能获取整棵树）。特别是在数据库中基于范围的查询是非常频繁的情况下，可以通过定位一个节点的关键字，就可以利用叶子节点关键字之间的指针把剩余的符合要求的关键字全部取出。
三、B+树在Mysql数据库的应用
Mysql数据库的引擎，最常见的两个是InnoDB 与 MyISAM，其主要区别在于InnoDB支持行级锁、事务处理与外键，MyISAM支持表级锁且不支持事务与外键。MyISAM类型的表强调的是性能，执行速度比InnoDB快，读性能强，但是不支持高级操作，写性能不如InnoDB。具体这两个引擎的区别以后数据库的专题文章讲述，由于这两个引擎都是采用B+树的结构存储索引，因此这里主要讲这两个引擎对B+树应用的区别。
1、MyISAM
MyISAM引擎叶节点的关键字指定的值域存放的是数据记录的地址，不保存实际的数据。主索引和辅助索引都是这样，区别在于主索引要求每个字段唯一，辅助索引没有这个要求。
因此，MyISAM中索引检索的算法为首先按照B+树搜索算法搜索索引，如果指定的关键字存在，则取出其关键字指定的值，然后以关键字指定的值为地址，读取相应数据记录。
2、InnoDB
InnoDB表数据文件本身就是按B+树组织的一个索引结构，这棵树的叶节点关键字指定的值域保存了完整的数据记录。这个索引的关键字是数据表的主键，因此InnoDB表数据文件本身就是主索引。这种索引叫做聚集索引。
InnoDB的辅助索引是聚簇索引，也会包含主键列，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
3、区别
综上所述，区别在于以下几点：
1）主索引区别在于InnoDB的数据文件本身就是索引文件，MyISAM的索引和数据是分开的。
2）辅助索引区别在于InnoDB的辅助索引关键值指定的值域存储相应记录主键的值而不是地址， MyISAM的辅助索引和主索引几乎一样。
四、好的文章
http://blog.csdn.net/v_JULY_v/article/details/6530142/
http://www.cnblogs.com/xyxxs/p/4440187.html
——written by linhxx 2017.07.17
相关阅读：