一、什么是索引
在mysql中,索引是一种特殊的数据库结构,由数据表中的一列或多列组合而成,可以用来快速查询数据表中有某一特定值的记录。通过索引,查询数据时不用读完记录的所有信息,而只是查询索引列即可，索引是帮助Mysql高效获取数据且以排好序的数据结构，直观的说，索引就类似书的目录页，没有目录（即索引）我们就要一页一页的找，有了目录（索引）我们就可以按照目录中标记的页数去相应的页数去查找。
二、为什么要用索引
例如，我们通过查询语句查询一条记录：select * from table where Col2 = 85,如果没有索引的话，那么它将从第一行[1,35]开始找，一行一行的找，直到找到[6,85]这条数据，并且数据存放的位置也不规则，拿取一行记录就需要与磁盘进行一次交互，即IO读取，如果数据多，这种效率将会很低下，只要把这种交互次数控制在一定范围之内，那他的效率将会比一行行查找要高很多，如给col2加索引，来执行select * from table where Col2 = 85，通过二叉树接口，第一次我们查到的是35，85比35大，所以查找右子节点，查到85，与条件种的85为一条数据，所以，这里就只需要两次交互就可以查到。所以索引就诞生了。
三、索引的数据结构
1、二叉树
1.1、二叉树的特点：
1、每个节点最多有两个子树，所以二叉树不存在度大于2的节点（结点的度：结点拥有的 子树的数目。），可以没有子树或者一个子树。
2.左子树和右子树有顺序，次序不能任意颠倒。
3、二叉树支持动态的插⼊和查找，保证操作在O(height)时间，这就是完成了哈希表不便完成的⼯作，动态性。但是⼆叉树有可能出现worst-case，如果 输⼊序列已经排序，则时间复杂度为O(N)。为什么不用二叉树来作为索引，就是因为二叉树的worst-case，如果输入序列是排好序的，那么二叉树的结构就会变成如下图所示的特殊状态：
所以二叉书并不适合去做索引，遇到这种极端情况，就会导致有索引和无索引效果一样。
2、平衡二叉树
AVL树是严格的平衡二叉树，所有节点的左右子树高度差不能超过1；AVL树查找、插入和删除在平均和最坏情况下都是O(lgn)。AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要1次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(lgn)。由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。
3、红黑树
与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡：只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。从实现来看，红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一，且节点颜色的划分需要满足特定的规则。在java8中的HashMap就是使用链表+红黑树。红黑树的缺点就是太高了，如下图所示：
当数据量特别大的时候，树的高度很高，假设你要查找的节点为当前树的叶子节点，那么要查找这个节点，至少要循环h(这棵树的高度)次，所以说，红黑树在这种情况下也并不适用。
4、B-Tree
Tree就是我们常说的B树，它是一种多路搜索树而非二叉树，使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度
在B树中，每个节点包含：
1、本结点所含关键字的个数；
2、指向父节点的指针
3、关键字
4、指向子节点的指针
对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结点为叶子节点，相应的，根结点中关键字的个数为1~m-1;非根结点至少有[m/2]([]，向上取整)个子结点，相应的，关键字个数为[m/2]-1~m-1。
B-tree有以下特性:
1、关键字集合分布在整棵树中;
2、任何一个关键字出现且只出现在一个结点中; 所有索引元素不重复
3、搜索有可能在非叶子结点结束;
4、其搜索性能等价于在关键字全集内做一次二分查找;
5、自动层次控制;
6、所有叶节点都在同一层，每个节点最多有m-1个key，并且以升序排列
叶节点具有相同的深度，叶节点的指针为空
由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最低搜索性能为:
其中，M为设定的非叶子结点最多子树个数，N为关键字总数;
所以B-树的性能总是等价于二分查找(与M值无关)，也就没有B树平衡的问题;
由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点;删除结点时，需将两个不足M/2的兄弟结点合并。
B树的查询：
B树是二叉排序树的扩展，二叉排序树是二路查找，B-树是多路查找。因为B-树节点内的关键字是有序的，在节点内查找的时候除了顺序查找之外，还可以用折半查找提高效率，B-树的具体查找步骤可以参照折半查找方法。
以查找42为例：
首先获取关键点的关键字进行比较，当前根节点关键字为30，42>30，所以找右子节点，拿到关键字39，45，39 |
