B树和B+树

B树和B+树的出现是为了查询数据时减少磁盘的IO次数，我们知道平衡二叉查找树是一种查询速度很快的数据结构。它的时间复杂度为（logN），但是它由于是一个二叉树，所以树的高度相对于多叉树来讲是比较高的，所以为了平衡磁盘IO与时间复杂度直接的关系，我们引入了B树和B+树

一、 何为B树？

首先我们要知道B树是一种多路平衡查找树，从这里我们可以知道，B树是一个多叉树，同时它又是一个平衡树，它的作用就是用来进行查询的。
首先我们从一个具体的B树来探究一下B树的定义：

从图可以看出，B树的高度与二叉树相比减少了

定义

根据Knuth的定义，一个m阶的B树是一个有以下属性的树：

1. 每一个节点最多有m个子节点
2. 每一个非叶子节点(除根节点)最少有[m/2]个子节点
3. 如果根节点不是叶子节点，那么它至少有两个子节点
4. 有k个子节点的非叶子节点有K-1个键
5. 所有的叶子节点都在同一层
   关于B树的插入和删除操作，我们只需记着一个原则，在进行插入或删除操作后，一定要查看树是否满足约束条件，若不满足，则进行调整。

二、何为B+树？

B+树是由B树演变而来，通常用于数据库和操作系统的文件系统中，有着比B树更高的查询性能

1. 有m个子树的节点包含有m个元素
2. 根节点和分支节点不保存数据，只用于索引，所有数据都保存在叶子节点中

3. 叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小从小到大顺序链接。