在讲B树和B+树之前我们解释一下为什么会想到创建B树等数据结构？
答：对于查找，我们可以通过以下的方式进行查找

1. 全部遍历==》时间复杂度是O(n)==〉hash表
2. hash遍历，优点在于能够快速找到我们的目标值，但其缺点是对于查找某一个范围之间的的数据仍然需要依次遍历==》二叉树
3. 查找的时间复杂度是O（log2n），大大提高了效率，其查找的时间复杂度取决于树的深度，但是如果出现递增式的增长的情况，树不平衡的情况，深度最大的情况，效率为O(n)，效率很低==》平衡二叉树
4. 平衡二叉树（AVL）保证了树的平衡，控制树的高度，但是数据量越大，树的高度越高，时间复杂度越高（譬如每一个结点中的数据信息保存在磁盘中，深度越高，磁盘的IO次数越多，效率越低）==》B树
5. B树的话保证了树的平衡，控制树的高度，减少磁盘的IO，每个节点可以存放多个数据信息以及指向多个子树，按照B树查找方式可以快速找到目标值（若存在的话），缺点在于每个磁盘容量有限，如果是索引和数据存放在一块的话，一个磁盘页存放关键词不多，当数据量很大的话，内存需要加载磁盘也的次数变多，查找效率也很低==》B+树
   
6. B+树：
   非叶子结点都是存放的索引，知识起索引的作用，存放的关键词变多，能更快的找到目标值，磁盘的IO次数减少，提高了查找效率==》这也是为什么Mysql用B+树查找的原因！
   

B-树（经常在文件系统中使用）

• 定义
  又称多路平衡查找树，b树中所有结点的孩子节点数的最大值称为B树的阶
  一颗m阶B树或为空树或为满足如下特性的m叉树

1. 树的每个结点至多有m棵子树（即至多有m-1个关键词）
2. 如果根节点不是叶子结点的话，则至少有两棵子树
3. 除根节点以外的所有非叶子结点至少有m/2向上取整棵子树（即至少有m/2向上取整-1个关键词）
4. 非叶子结点的结构为
   
   n：表示关键词的个数
   p：表示指针
   k：表示关键词
5. 所有的叶子结点都出现在同一层次上，不带有任何信息，实际上这些结点并不存在，指向这些结点的指针都是空指针
   

• B-树查找分析
  主要分为两步骤：
  第一步：找到结点
  第二步：在结点中找关键词
  前者是在磁盘中进行，找到对应的结点以后会将结点中的信息读入内存，然后再利用顺序查找/折半查找法查找目标关键词====》由于磁盘进行查找的效率远比内存低，所以B-树的效率很大部分取决于磁盘中的查找====〉B-树的深度
  假设有一个m阶的B-树，总共有n个关键词，深度为h（这里的h不包含叶子层）
  
  深度最小的情况是满二叉树的情况，根据B-树的定义可知，最多有 （1+m+m2+......+m^(n-1)）(m-1)
  深度最多的情况是每一层都是最少的子树，即如下图所示，叶子结点那一层结点个数最多的时候是n+1个
  
  所以最终变换而得，h的范围！

• 插入
  分为以下几种情况：

1. 插入关键词以后，仍然满足B-树的性质，即满足该节点的关键词个数在[m/2向上取整-1，m-1]之间，如下图
   
2. 插入关键词以后，不满足B-树的性质，即满足该节点的关键词个数不在[m/2向上取整-1，m-1]之间，超出了m-1个数，则需要进行如下的操作：
   
   举例说明：
   未插入19之前的状态
   
   插入19关键词以后的B-树状态如下图所示：
   

• 删除
  

对于终端结点的删除操作

1. 直接删除
   删除以后仍然满足B-树性质，即关键词数在[m/2向上取整-1，m-1]之间，则直接删除

2. 兄弟够借
   删除以后不满足B-树性质，即关键词数不在[m/2向上取整-1，m-1]之间，但是相邻的兄弟结点中关键词数>=m/2向上取整，借走一个也满足B-树的要求，所以可以借给要删除的结点，以满足B-树的性质，步骤如下：需要调整该节点，双亲结点，兄弟结点的关键词！
   
   如下图所示
   未删除24之前
   
   删除24之后（从左兄弟结点借）
   
   删除24之后（从右兄弟结点借）
   

3. 兄弟不够借
   删除以后不满足B-树性质，即关键词数不在[m/2向上取整-1，m-1]之间，相邻的兄弟结点中关键词树==m/2向上取整-1，借走一个不满足B-树的要求，需要进行如下的步骤才能满足B-树的性质，如下图所示，
   第一步：删除关键词
   第二步：与不够借的兄弟结点和双亲结点中这两兄弟子树中间的关键词进行合并，合并后的关键词们放入原兄弟结点中
   第三步：合并之后，双亲结点因删除一个关键词如果不满足B-树性质的话，继续执行步骤2向上合并操作，直到符合B-树定义为止
   
   举例说明：
   未删除30之前：
   

   对于非终端结点的删除操作（需要删除关键词k）

4. 如果小于k的子树中的关键词个数m/2向上取整，则找到k的前驱值，并交换二者的位置，之后递归删除k，直到k位于终端结点位置，然后使用删除终端的结点的关键词的方法删除目标关键词
   举例：
   未删除33之前
   
   删除33之后
   

5. 如果大于k的子树中的关键词个数至少为m/2向上取整，则找到k的后继值，并交换二者的位置，之后递归删除k，直到k位于终端结点位置，然后使用删除终端的结点的关键词的方法删除目标关键词
   举例：
   未删除33之前
   
   删除33之后
   

6. 如果前后两个子树的关键词树都是m/2向上取整-1个，不能进行替换删除（否则会不满足B-树的性质），直接将两个子节点合并，然后删除k即可
   举例：
   未删除23之前
   
   删除23之后
   

B+树（B-树的变型树）

应用：常用于数据库和操作系统的文件系统中的查找
与B-树之间的区别在于：
1、所有非叶子结点都只存放索引数据，起索引作用，非叶子结点的索引项只含有对应子树的最大关键词和指向孩子树的指针，所有叶子结点包含所有的索引值，并指向数据（如存在磁盘上的数据等）
2、B+树中每个节点有多少个子树，对应该节点就有多少个关键词，其范围在[m/2向上取整,m]
3、B+树的叶子结点链接起来形成一个单链表
注意：每个节点存放的索引都是从小到大排列的！
B树于B+树最大的区别在于叶子结点是否存放数据！
如下图所示：
这样设计的好处有：
1、每个节点存放的是索引，所以一个节点存放的数据更多，降低树的高度，大大提高查找效率
2、叶子结点部分是相连的，完全可以看成是一个排好序的链表，所以链表的操作优点都具有！！