索引提高查询效率，就像我们看的书，想要直接翻到某一章，是不是不用一页一页的翻，只需要看下目录，根据目录找到其所在的页数即可。
在计算机中我们需要一种数据结构来存储这个目录，常见数据结构有哈希表，二叉查找树，二叉平衡树(AVL)，红黑树，那为什么Innodb和MyISAM选择b+树呢。
1. 哈希表
哈希表就是一个数组+链表，用下标0，1，2，3..... 表示其数据所在的位置。如果想要在哈希表中存放数据，首先用对这个数据进行散列算法（基本的就是取模运算），假如数组长度是13 ，进行模13之后是0-12，正好对应的数据的下标，如果计算出的下标一样的，就会在下标位置跟上链表。
不能直接说mysql不使用哈希表，而是要根据存储引擎来确定的，Memory存储引擎使用的就是哈希表
2. 二叉查找树
同样是只有两个分支，数据量大的时候深度依然会很深
以上三种二叉树，随着数据的增多，最终都会出现节点过多的情况，而且他们有且仅有2个分支，那么IO的次数一样很多.
怎么解决仅有2个分支而且深度过深，这就有了B树，增加分支
5. B-Tree
如上图：（图中只是画出来一部分，实际上没有限制的，不止p1,p2,p3）
每个节点占用一个磁盘块，一个节点上有两个升序排列的关键字和三个指向子树根节点的指针，指针存储的是子节点所在的磁盘块地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为16和34，p1指针指向的子树的数据范围小于16，p2指针指向的子树的数据范围为16-34，p3指针指向的子树的数据范围大于34。
查找关键字28的过程：
6. B+树
B+树是在B树的基础上做的一种优化，变化如下：
如上图： 在B+树上有两个头指针，一个指向根节点，另一个指向关键字的最小叶子节点，而且所有叶子节点(及数据节点)之间是一种链式环结构，因此可以对B+树进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始的随机查找。
InnoDB和MyISAM中索引上的差异
1. InnoDB-主键索引
叶子节点存储的是具体的行数据