Innodb索引底层数据结构式B+树。所以介绍索引实现原理之前，我们来看一下什么是B+树。看B+树之前我们，要了解一下二叉查找树和平衡二叉树。
什么是二叉查找树？
二叉查找树，又叫做二叉排序树，也叫做二叉搜索树。
二叉查找树或者使用一颗空树；或者是具有下列性质的二叉树
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若他的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左右子树也分别为二叉搜索树。
可以看出来，二叉查找树中序遍历可以得到一个关键字的有序序列。二叉查找树既拥有类似折半查找的特性，又采用了链表做存储结构，因此是动态查找表的一种适宜表示。
在二叉查找树上查找其关键字等于给定值结点的过程，恰是走了一条从根结点到该结点的路径的过程。所以，含有n个结点的二叉查找树夫人平均查找长度和树的形态有关。
当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树。
所以，需要对二叉查找树 进行 平衡化处理，成为二叉平衡树。
平衡二叉树
平衡二叉树（Balanced Binary Tree）又称AVL树。它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
如果二叉查找树是AVL树，则它的深度和logn是同数量级的。因此，它的平均查找长度也和logn同数量级。
B-Tree平衡多路查找树
B-Tree是一种平衡的多路查找树。一颗m阶的的B-树，或为满足下列特性的m叉树：
- 树中每个结点最多有m棵子树；
- 若根结点不是叶子结点，则至少有两棵子树；
- 除根之外的所有非终端结点至少有【m/2】棵子树；
- 所有非终端结点中包含信息数据；
- 所有叶子结点都出现在同一层次上，并且不带信息。
由B-树定义可知，在B-树上进行查找的过程和二叉查找树的查找类似。B-树查找包含两种基本操作：
- 在B-树中找结点；
- 在结点中找关键字。
B+树
B+树是应文件系统所需而出的一种B-树的变形树。一棵m阶的B+树和m阶的B-树的差异在于：
- 有n棵子树的结点中含有n个关键字。
- 所有叶子结点中包含了全部关键字的信息，以及指向这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
- 所有非终端结点可以看成是索引部分，结点中仅含有其子树中的最大（或最小）关键字。
B+树上的查找类似B-树。只是在查找时，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。
