MySQL与B-Tree和B+Tree
MySQL支持多种存储引擎，如InnoDB，MyISAM，Memory等等。其中InnoDB支持事物安全(ACID)，支持行锁定和外键，因而成为了MySQL默认的存储引擎。(MyISAM是在MySQL 5.5.5 之前的默认引擎)
- InnoDB是支持事物安全的存储引擎，支持行锁定和外键，支持 B-Tree/Hash/FullText 索引类型。因为行锁，所以相比较MyISAM更能支持高并发的读写，但是存储空间也比MyISAM高。
- MyISAM不支持事物，也不支持外键，锁级别是表锁，这个引擎适合查询为主的业务。支持 B-Tree/FullText/R-tree 索引类型，强调快速读取。
- Memory是内存级别的存储引擎，所以存储的数据量较小，对数据的一致性支持较差。锁级别为表锁，不支持事务。但访问速度非常快，并且默认使用 hash 索引。
其中，索引(index)是为了提高MySQL检索数据效率的一种数据结构。索引中的B-Tree索引使用的数据结构是多叉平衡树。其实InnoDB中使用的是B+Tree，是B-Tree的变种，至于为什么网上以及MySQL中查询所使用的索引得到的是B-Tree，可以参考：https://dba.stackexchange.com/questions/204561/does-mysql-use-b-tree-btree-or-both 。
相较而言，B-Tree和B+Tree是有区别的，但是总的来说，在作为存储引擎的索引方面，还是B+Tree更合适。
- B+Tree排序更快(非叶子结点不存储数据，底层链表)。
- B-Tree在中间结点(非叶子结点)上的插入速度更快。
二叉树和平衡二叉树
关于二叉树以及其遍历，在我之前的博客有讲到过，可以参考：https://russxia.github.io/2018/03/08/%E4%BA%8C%E5%8F%89%E6%A0%91%E5%8F%8A%E5%85%B6%E9%81%8D%E5%8E%86/。那么平衡二叉树又是什么呢，和普通的二叉树相比，区别又是什么呢。
概念
我们知道，二叉查找树的查询效率并不是严格的O(logN)的，当二叉树退化成链表的情况下，其最差的查找效率是O(N)，等同于顺序查找。所以为了提升查询效率，如果我们保证了每棵树都是一颗完全二叉树(除最后一层外，其余层都是满的)，那么查询的效率就可以保证更接近于O(longN)，因此引出了平衡二叉树的概念。
关于平衡二叉树的设计思路，可以参考百度百科的平衡二叉树：
对一棵查找树（search tree）进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree（平衡树）。
所以为了满足平衡二叉树的特点，在插入/删除新元素的时候，如果新插入/删除的元素使得当前的二叉树不再是一颗平衡二叉树，我们需要对树结点进行”旋转”，使其重新满足平衡二叉树，这就是树的左旋和右旋。
总结
更多关于二叉平衡树常见的定义和实现，可以参考wiki的平衡二叉搜索树。
平衡二叉搜索树(Balanced Binary Tree)是一种结构平衡的二叉搜索树，是一种每个节点的左右两子树高度差都不超过一的二叉树。能在O(logN)内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树。
常见的平衡二叉搜索树有：
B-Tree
B-Tree是一颗多路平衡查找树，在百度百科的平衡二叉树中有说到：对一棵查找树（search tree）进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。 树的深度过大，意味着频繁的磁盘I/O读写，低下的查询效率。那么如何减少树的深度呢，一个基本的思路就是：采用多叉树的结构。
一棵m阶的B-树 (m叉树)的特性如下
树中每个结点最多含有m个孩子（m>=2）
除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子(最多有m个孩子)(其中ceil(x)是一个向正无穷取整的函数)
若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）
所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)
每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，……，Kn，Pn)。其中：
a) Ki (i=1…n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
b) Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。
c) 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。
一颗4阶的B-Tree的插入和删除
假设我们先插入了100、200、300三个元素，因为我们是一颗4阶树，所以根节点可以存放3个元素(key)。当插入第四个元素400时，200成为根节点，100成为左结点，300、400成为右结点。(特性3)
当连续插入元素500、600时，由于右子节点的key>3了，所以其中间结点400被移动到根节点，|500|600|构成新的右子节点。300 是和 100 、|500|600|同一级别的新节点(特性5)
删除元素的过程中，有可能会破坏了B-Tree的特性，所以需要考虑的情况会比插入的情况要复杂的多。
关于删除的过程，可以参考wiki：
其主要思路是先删除元素，删除的元素又需要去区分叶子结点和非叶子结点这种情况。删除元素后重新平衡，重新平衡从叶子结点开始向根节点进发，直到重新平衡为止。
B+Tree
B+Tree是B-Tree的变形，是一种更适应数据存储和索引的数据结构。它和B-Tree的主要不同在于：
- 所有关键字存储在叶子节点，非叶子节点不存储真正的data
- 所有的非叶子结点，都可以看成是索引。
- 所有的叶子结点依顺序增加了顺序指针，形成了一个链表。
为什么这样的改动，就能使B+Tree比B-Tree更适合数据存储和索引呢？原因主要有以下几点：
- B+Tree的磁盘读写代价更低
参考内容: