MySql索引是一种经过排序的数据结构，究竟是什么样的数据结构呢，我们来谈一下常见的几种数据结构的演变历史。
输入一组数据：8，5，9，7，10，4 可以看到这种结构：
二叉查找树-输入无序树高度为3，如果我们输入一组有序的数据呢，4，5，7，8，9，10 会变成什么样子？
二叉查找树-输入有序这个时候变成了一颗斜树，树的高度为 6，很明显问题出现来，树高太高，遍历次数多
平衡二叉树 基于二叉查找树通过左旋、右旋的方式调整树高。 特征： - 任意结点（包括根结点）的左子树上的结点的值都比这个结点得值小； - 任意结点（包括根结点）的右子树上的结点的值都比这个结点得值大； - 左右两个子树的高度差的绝对值不超过1；我们同样输入上面有序的数据
平衡二叉树发现他很好的解决了二叉查找树的斜树树高问题，但随着数据量的暴增，可以想象当数据量达到百万、千万甚至上亿的时候树高的问题又成为了瓶颈，因为每个节点只有两个子节点。
B树 B树是其实就是多路平衡查找树，说白了就是对每个节点做了横向扩展了，每个节点不再单纯的只存一个数据。 每个节点存储了数据行+指向分支节点的多个引用。 根节点和每个分支节点的分支数称为度，度为N，每个分支节点可存储的数据最大个数为N-1假设B树的度为3，则每个节点有3个分支，而每个节点可存储的数据量为2
B-tree B+树 B+tree是在B-tree的基础上，进一步横向扩展 将每个分支节点存储的数据下沉到叶子节点，而根节点和分支节点只存储索引值 每个节点节省出来的存储空间可以用来存储更多的数据项，使树的形状变得矮胖 每个节点存储的内容相比B-tree，仅保存了数据行的索引值+指向分支节点的引用 B+Tree
上面介绍了几种常见的数据结构之后，可以看到二叉查找树和平衡二叉树是有很大的局限性，mysql索引使用的B+Tree，我们来对比下两个的差别。
我们有一张表：a_user（id, name, mobile三个字段），id字段创建了主键索引，name字段创建了普通索引。
如果是B-Tree的结构如果是B+Tree 差异 B-Tree在每个节点存储了数据行的磁盘地址 B+Tree则只存储了索引列的值，占用空间更少，单个节点可存放的数据更多 B+Tree将数据存放在叶子节点，通过索引可直接在数据结构中查到行数据
如图，聚集索引查询效率最高，二级索引会有一次回表的动作，回表就是指根据二级索引查询到数据后会根据主键再扫描一次聚集索引。
