MySQL索引底层实现原理
MySQL官方对索引的定义为：索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。
我们知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search)，这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找(binary search)、二叉树查找(binary tree search)等。
如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构(例如，理论上不可能同时将两列都按顺序进行组织)，所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用(指向)数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
上图展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在 ( 2) 的复杂度内获取到相应数据。
虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树(red-black tree)实现的，原因会在下文介绍。
二叉排序树
在介绍B树之前，先来看另一棵神奇的树——二叉排序树(Binary Sort Tree)，首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了(下图所示)，而这棵树上的节点是已经排好序的，具体的排序规则如下：
若左子树不空，则左子树上所有节点的值均小于它的根节点的值;
若右子树不空，则右字数上所有节点的值均大于它的根节点的值;
它的左、右子树也分别为二叉排序数(递归定义)。
从图中可以看出，二叉排序树组织数据时，用于查找是比较方便的，因为每次经过一次节点时，最多可以减少一半的可能，不过极端情况会出现所有节点都位于同一侧，直观上看就是一条直线，那么这种查询的效率就比较低了，因此需要对二叉树左右子树的高度进行平衡化处理，于是就有了平衡二叉树(Balenced Binary Tree)。
所谓“平衡”，说的是这棵树的各个分支的高度是均匀的，它的左子树和右子树的高度之差绝对值小于1，这样就不会出现一条支路特别长的情况。于是，在这样的平衡树中进行查找时，总共比较节点的次数不超过树的高度，这就确保了查询的效率(时间复杂度为O(logn))
B树
还是直接看图比较清楚，图中所示，B树事实上是一种平衡的多叉查找树，也就是说最多可以开m个叉(m>=2)，我们称之为m阶b树，为了体现本博客的良心之处，不同于其他地方都能看到2阶B树，这里特意画了一棵5阶B树 。
总的来说，m阶B树满足以下条件：
每个节点至多可以拥有m棵子树。
根节点，只有至少有2个节点(要么极端情况，就是一棵树就一个根节点，单细胞生物，即是根，也是叶，也是树)。
非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整，图中5阶B树，每个节点至少有3个子树，也就是至少有3个叉)。
非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示该节点中保存的关键字个数，K为关键字且Ki
从根到叶子的每一条路径都有相同的长度，也就是说，叶子节在相同的层，并且这些节点不带信息，实际上这些节点就表示找不到指定的值，也就是指向这些节点的指针为空。
B树的查询过程和二叉排序树比较类似，从根节点依次比较每个结点， 因为每个节点中的关键字和左右子树都是有序的 ，所以只要比较节点中的关键字，或者沿着指针就能很快地找到指定的关键字，如果查找失败，则会返回叶子节点，即空指针。
从根节点P开始，K的位置在P之前，进入左侧指针。
左子树中，依次比较C、F、J、M，发现K在J和M之间。
沿着J和M之间的指针，继续访问子树，并依次进行比较，发现第一个关键字K即为指定查找的值。
B树搜索的简单伪算法如下：
BTree_Search(node, key) {
if(node == null) return null;
foreach(node.key)
{
if(node.key[i] == key) return node.data[i];
if(node.key[i] > key) return BTree_Search(point[i]->node);
}
return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);
B树的特点可以总结为如下：
关键字集合分布在整颗树中。
任何一个关键字出现且只出现在一个节点中。
搜索有可能在非叶子节点结束。
其搜索性能等价于在关键字集合内做一次二分查找。
B树在插入删除新的数据记录会破坏B-Tree的性质，因为在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。
Plus版 — B+树
作为B树的加强版，B+树与B树的差异在于:
有n棵子树的节点含有n个关键字(也有认为是n-1个关键字)。
所有的关键字全部存储在叶子节点上，且叶子节点本身根据关键字自小而大顺序连接。
非叶子节点可以看成索引部分，节点中仅含有其子树(根节点)中的最大(或最小)关键字。
B+树的查找过程，与B树类似，只不过查找时，如果在非叶子节点上的关键字等于给定值，并不终止，而是继续沿着指针直到叶子节点位置。因此在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子节点的路径。
B+树的特性如下：
所有关键字都存储在叶子节上，且链表中的关键字恰好是有序的。
不可能非叶子节点命中返回。
非叶子节点相当于叶子节点的索引，叶子节点相当于是存储(关键字)数据的数据层。
更适合文件索引系统。
带有顺序访问指针的B+Tree
一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。
如上图所示，在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。
二叉树与红黑树的比较
从上面我们发现，红黑树相比较于二叉树又进步了一些，但红黑树还是有些问题：那就是数据量大的话，红黑树的深度会很深，也就是说深度不可控，这样一来查找数据还是会很耗时。
从上面看，我们发现BTree又进步了一些，查询速度提高，存储容量也没影响到。当然有人可能会这样想，那我们为什么不把数据全部都存在一个节点，这样深度不就是1了吗?
当然不行了!java拿取数据一般是这样的：java程序-->CPU--->内存---->硬盘，而内存与硬盘的交互是有大小限制的，是一页数据4k左右，所以不能把所有数据都放在一个节点来获取，一般来说节点会尽量预存4K容量。
看到这里，我们知道(4K=节点;节点=小节点*小节点的容量)一个节点是4K，而节点内有几个小节点，那么也就是说，只要我们每个的小节点的data容量越小，那么可以存的节点也就可以更多。
B+Tree通过把data不放在非叶子节点来增加度(小节点)，一般会一百个以上使得深度是3~5，从而减少查询次数。并且，叶子节点之间会有指针，数据又是递增的，这使得我们范围查找可以通过指针连接查找，而不再从上面节点往下一个个找。
结论：B+Tree 既减少查询次数又提供了很好的范围查询。