一般说MySQL的索引，都清楚其索引主要以B+树为主，此外还有Hash、RTree、FullText。本文简要说明一下MySQL的B+Tree索引，以及和其相关的二叉树、平衡二叉树、B-Tree，相关的知识网上很多，为了方便自己更快、清楚的了解，文本聚合一些内容以及个人的一些理解。
说明 二叉查找树（BST）
概念
二叉查找树是基于二分查找法来提高数据查找速度的二叉树的数据结构；关于二分查找法的时间复杂度可以看 时间复杂度 O(log n) 意味着什么？。
特点
二叉查找树是采用二分查找法把数据按规则组装成一个树形结构的数据，减少无关数据的检索，提升了数据检索的速度；二叉树的数据结构有以下规则：
（1）非叶子节点只能允许最多两个子节点存在。
（2）每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值；
即二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。 顶端的节点称为根节点，没有子节点的节点我们称之为叶节点。以下图中的圆为二叉查找树的节点，节点中存储了键(key)和数据(data)
查找结点值的方法就是二分查找法：查找次数就是树的高度。二叉查找树可以任意地构造 如果向一方倾斜的二叉树是不平衡的，查询效率就低了，二叉查找树变成了一个链表。如下图：
在上面的2张图中，查找键值为17的数据，第一张图里需要3次IO，第2张图里需要7次IO。原因是二叉查找树变得不平衡了，也就是高度太高了，从而导致查找效率的不稳定。为了解决这个问题，需要保证二叉查找树一直保持平衡，就需要用到平衡二叉树了。
在满足二叉查找树特性的基础上，如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。 类似于：
关于平衡二叉树的可以看 什么是平衡二叉树（AVL）该文章说明，平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。需要注意的是平衡二叉树是每个节点只存储一个键值和数据的。
B树(B-Tree)概念：
B树和平衡二叉树不同，B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引里大量使用者B-Tree和B+Tree的数据结构。
特点：
（1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
（2）子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路，当M=2则是2叉树,M=3则是3叉）；
（3）关键字数：枝节点的关键字数量大于等于ceil(M/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
（4）所有叶子节点均在同一层、叶子节点除了包含了关键字还包含了数据;
最后我们用一个图和一个实际的例子来理解B树（这里为了理解方便我就直接用实际字母的大小来排列C>B>A）
图中可以看到BTree的单个节点可以存储多个键值和数据的平衡树。和平衡二叉树相比：
比如要存储海量的数据，因为（平衡）二叉树的每个节点只存储一个键值和数据的，二叉树的节点将会非常多，高度也会及其高，当查找数据时也会进行很多次磁盘IO，查找的效率将会极低，大致的二叉树结构如下：
为了解决平衡二叉树的这个弊端，需要一种单个节点可以存储多个键值和数据的平衡树（BTree）：
从上图可以看出，B树相对于平衡二叉树，每个节点存储了更多的键值(key)和数据(data)，并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的B树为3阶B树，高度也会很低。 基于这个特性，B树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。