【C++从0到王者】第五十一站：B+树

一、B+树

1.B+树的概念

B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了以下几点改进优化：

1. 分支节点的子树指针与关键字个数相同

2. 分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间。（相当于取消了最左边的那棵树）

3. 所有叶子节点增加一个链接指针链接在一起

4. 所有关键字及其映射数据都在叶子节点出现 （分支结点跟叶子结点有重复的值，分支结点存的是叶子结点的索引。父亲中存的是孩子结点中的最小值做索引）

2.B+树的特性

B+树的特性：

1. 所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。
2. 不可能在分支节点中命中。
3. 分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层

3.B+树的插入的过程

如下是M=3时候的B+树的插入分裂过程

B+树的插入过程根B树是类似的，细节区别在于，第一次插入两层，一层结点做分支，一层做根

后面一样都是往叶子中去插入的，插入满了以后，分裂一半给兄弟，转换成往父亲插入一个key和一个孩子，孩子就是兄弟，key是兄弟的第一个最小的key。

B+树的分裂：
当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

4.总结

• 简化了B树孩子比关键字多一个的规则，变成了相等
• 所有的值都在叶子上，方便遍历查找所有的值

二、B*树

1. B*树的概念

B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针

2.B*树的分裂

B+树的分裂：
当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

B*树的分裂：
当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。
所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

B*的结点的关键字和和孩子数量是在[2/3*M, M]之间的

三、总结

大致将B树，B+树，B*树总结如下：
B树：有序数组+平衡多叉树；
B+树：有序数组链表+平衡多叉树；
B*树：一棵更丰满的，空间利用率更高的B+树。

四、B树系列和哈希和平衡搜索树作对比

在内存中作内查找时候

单纯论树的高度，搜索效率，B树确实不错

但是B树系列也有一些隐形坏处

1. 空间利用率低，消耗高

2. 插入删除数据时，分裂和合并节点，那么必然挪动数据

3. 虽然高度更低，但是在内存中而言，与哈希和平衡搜索树还是一个量级中。

比如当M为1024的时候，N为10亿的时候

B树的次数为3次，而平衡树的效率为30次

在内存中搜索3次和30次差别不是特别大

但是在磁盘中搜索3次和30次差别巨大

结论：实质上B树系列在内存中体现不出优势

五、B树的一些应用

1.索引

**B-树最常见的应用就是用来做索引。**索引通俗的说就是为了方便用户快速找到所寻之物，比如：书籍目录可以让读者快速找到相关信息，hao123网页导航网站，为了让用户能够快速的找到有价值的分类网站，本质上就是互联网页面中的索引结构

MySQL官方对索引的定义为：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说：索引就是数据结构

当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，该数据结构就是索引。

像我们在使用B+树去索引磁盘数据的时候，分支结点只存储key值，这就可以使得分支结点比较小。分支结点映射的磁盘数据块就可以尽量加载到Cache中，从而提高效率

2.MySQL索引

mysql是目前非常流行的开源关系型数据库，不仅是免费的，可靠性高，速度也比较快，而且拥有灵活的插件式存储引擎

MySQL中索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。

注意：索引是基于表的，而不是基于数据库的

3.MyISAM

MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎，不支持事务，支持全文检索，使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址，其结构如下

上图是以以Col1为主键，MyISAM的示意图，可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果想在Col2上建立一个辅助索引，则此索引的结构如下图所示：

同样也是一棵B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”的。

我们也可以用name来进行索引。

• 一般数据库要求主键是唯一的，比如mysql建表的主键，就是B+s树的key。B+树的value是存储一行数据的磁盘地址

• 分支节点也是需要存盘中的，因为数据量大了，内存是存不下的，分支结点中应该是磁盘地址。

• 但是分支结点理论上应该被尽量缓存到cache

• 

• 一般数据库要求主键值是不重复唯一字段，比如电话、身份证号码适合，但是名字，地址不适合

没有字段能保持唯一，可以考虑自增主键（其实它自己建立一个自增整数做完主键）

一般数据库不要求索引唯一，像mysql建立索引可以考虑使用B+树或者Hash表，数据结构允许冗余

像下面的语句中，插入第二条语句就会报错，因为主键张伟已经存在了。

B+树做主键索引相比B树的优势如下：

1. B+树所有值都在叶子，遍历很方便，方便区间查找
2. 对于没有建立索引的字段，全表扫描的遍历很方便
3. 分支结点值存储key，一个分支结点空间占用更小，可以尽可能加载到缓存

B树不用叶子就能找到值，B+树一定要到叶子，这是B树一个优势，但是B+树高度足够低，所以差别不大

2.InnoDB

InnoDB存储引擎支持事务，其设计目标主要面向在线事务处理的应用，从MySQL数据库5.5.8版本开始，InnoDB存储引擎是默认的存储引擎。InnoDB支持B+树索引、全文索引、哈希索引。但InnoDB使用B+Tree作为索引结构时，具体实现方式却与MyISAM截然不同。

第一个区别是InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而InnoDB索引，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录，这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型

第二个区别是InnoDB的辅助索引data域存储相应记录主键的值而不是地址,所有辅助索引都引用主键作为data域

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。