[toc]
前言
MySQL作为互联网中非常热门的数据库，其底层的存储引擎和数据检索的设计非常重要，尤其是MySQL数据的存储形式以及索引的设计，决定了MySQL整体的数据检索性能。
我们知道，索引的作用是做数据快速的检索，而快速检索的实现的本质是数据结构，通过不同的数据结构的选择，实现各种数据快速检索，在数据库中，高效的查找算法非常重要的，因为数据库中存储了大量的数据，一个高效的索引能够节省巨大的时间，比如下面数据表，如果MySQ没有实现索引算法，那么查找id=7这个数据，那么只能采取暴力顺序遍历查找，找到id=7这个数据需要比较7次，如果这个表存储的是1000W个数据，查找id=1000W这个数据就要比较1000W次，这种速度是不能接收的。
MySQL索引底层数据结构选型
hash表(hash)
哈希表是做数据快速检索的有效利器。
哈希算法：也叫散列算法，就是把任意值(key)通过哈希函数变换为固定长度的key地址，通过这个地址进行具体数据的数据结构。
考虑这个数据表user，表中一共有7个数据，我们需要检索id=7的数据SQL的语法是select * from user where id=7;
哈希算法首先计算存储id=7的数据物理地址addr=hash(7)=4231，而4231映射的物理地址是0x77，0x77就是id=7存储的数据的物理地址，通过独立地址可以找到对应user_name='g'这个数据，这就是哈希算法快速检索数据的计算过程。
但是哈希算法有个数据碰撞的问题，也就是哈希函数可能对不同的key会计算出同一个结果，比如hash(7)可能跟hash(199)计算出来的结果一样，也就是不同的key映射到同一个结果了这就是碰撞问题，解决碰撞的问题的一个常见处理方式就是链地址法，即用链表把碰撞的数据连接起来，计算哈希值之后，还需要检查该哈希值是否存在碰撞数据链表，有则一直遍历到链表尾部，直到找到真正的key对应的数据为止。
从算法时间复杂度分析来看，哈希算法时间复杂度为O(1)，检索速度非常快，比如查找id=7的数据，哈希索引只需要计算一次就可以获取到对应的数据，检索速度非常快，但是mysql并没有采取哈希作为其底层算法，这是为什么呢？因为考虑到数据检索有一个常用的手段就是范围查找，比如这个sql，
select * from user where id>3。 针对这个语句，我们希望找出id>3的数据，这就是典型的范围查找，如果使用哈希算法实现索引，范围查找怎么做？一个简单思路就是一次把所有数据找出来加载到内存，然后在内存来筛选目标范围内的数据，但是这个范围查找方法太笨重了，没有一点效率而言。
所以使用哈希算法实现的索引虽然可以做到快速检索数据，但是没办法做数据高效的范围查找，因此哈希索引不适合mysql的底层索引数据结构。
二叉查找树
二叉查找树是一种支持数据快速查找的数据结构，如下图所示：
二叉查找树的时间复杂度是O(logn)，比如针对上面这个二叉树结构，我们需要计算比较3次就可以检索到id=7的数据，相对于直接遍历查询省了一半的时间，从检索效率看能做到高速减速，此外二叉树的结构能不能解决hash索引不能解决的范围查找功能呢？
答案是可以的，通过上图可以看出，二叉树的叶子节点都是按顺序排列的，从左到右一次升序排列，如果我们需要找到id>5的数据，我们取节点为6的节点以及其右子树就可以了，范围查找也算是比较容易实现的。
但是普通的二叉查找树有一个致命缺点：极端情况下会退化成链表，二分查找也会退化为遍历查找，时间复杂度退化为O(N)，检索性能急剧下降，比如下面这种情况就是退化成链表了：
在数据库中，数据自增是一个很常见的形式，比如一个表的主键ID，而主键一般默认是自增的，如果采取二叉搜索树作为索引，那上面的介绍的不平衡状态导致线性查找的问题必然出现，因此简单的二叉搜索树存在不平衡导致检索性能下降，是不能直接用于实现MySQL的底层索引的。
AVL树和红黑树
二叉查找树存在不平衡问题，因此学者提出通过树节点的自动旋转和调整，让二叉树始终保持基本的平衡状态，就能保持二叉查找树的最佳性能了，基于这种思路的自我调整平衡状态的二叉树有AVL树和红黑树。
首先简单介绍红黑树，这是通过自动调整树形态的树结构，比如当二叉树处于一个不平衡状态时，红黑树就会自动左旋右旋节点以及节点变色，调整树的形态，使其保持基本的平衡状态(时间复杂度O(logn))，也保证了查找效率不会明显下降，比如从1到7升序插入数据节点，如果是普通二叉查找树则会退化成链表，但是红黑树则会不断的调整树的形态，使其保持基本平衡状态，如下图所示，下面这个红黑树查找id=7的所要比较的节点数为4，依然保持二叉树不错的查找效率。
红黑树拥有不错的平均查找效率，也不出不存在极端的O(n)情况，那红黑树作为MySQL顶层索引实现是否可以呢，其实红黑树也存在一些问题，观察稀土。
红黑树顺序插入1~7个节点，查找id=7，是需要计算节点数为4
红黑树顺序插入1~16个节点，查找id=16需要比较节点数为6次，观察一下这个树的形态，是不是当数据是顺序插入时，树的形态一直处于“右倾”的趋势？从根上看，红黑树并没有完全解决二叉查找树虽然这个右倾趋势没有那么严重，但是数据库中基本主键自增操作，主键一般都是数百万树千万，如果红黑树存在这种问题，对于查找性能而言也是巨大的消耗，我们数据库不可能忍受这种无意义的等待。
现在考虑另一种更为严格的自平衡二叉树AVL树，因为AVL树是一个绝对平衡的二叉树，因此他在调整二叉树的形态上消耗的性能比较多。
AVL树顺序插入1~7个节点，查找id=7时所需要比较节点次数为3：
AVL树顺序插入1~16个节点，查找id=16，需要比较节点数为4，从查找效率而言，AVL数查找的速度要高于红黑树的查找效率，从树形态来看，AVL树解决了红黑树右倾的问题，也就是说，大量的顺序插入不会导致查询性能的降低，这从根本上解决了红黑树的问题。
总结一下AVL树的优点：
- 不错的查找性能(O(logn))，不存在极端的低效的查找情况。
- 可以实现范围查找、数据排序
看起来AVL树作为数据查找的数据结构确实不错，但是AVL树并不适合做MySQL数据库索引数据结构，因为考虑下面问题：
- 数据库查询数据的瓶颈在于磁盘IO，如果使用AVL树，我们每一个树节点只存储一个数据，我们一次磁盘IO只能取出一个节点上的数据加载到内存里，那比如查询id=7这个数据我们就要进行磁盘IO三次，这是多么消耗时间的，所以设计数据库索引时需要考虑怎么尽可能减少磁盘IO次数。
磁盘IO有个特点，就是从磁盘读取1B数据和1KB数据所消耗的时间基本一样的，我们就根据这个思路，可以在一个树节点上尽可能多的存储数据，一次磁盘IO对价在点数据到内存，这就是B树，B+树的设计原理。
B树
下面这个B树，每个节点限制最多存储两个key，一个节点如果超过两个key就会自动分裂，比如下面这个存储7个数据的B树，只需要查询这两个节点就可以知道id=7这数据的具体位置，也就是两次磁盘IO就可以查询到指定数据，优于AVL树。
下面是一个存储16个数据的B树，同样每个节点最多存储2个key，查询id=16这个数据需要查询4个节点，也就是4次磁盘IO，看起来查询性能与AVL树一样。
但是考虑到磁盘IO读一个数据和读100个数据消耗的时间基本一致，那我们的优化思路可以改为：尽可能在一次磁盘IO中多读一些数据到内存，这个直接反映到树的结构就是，每个节点能存储的key可以适当增加。
当我们把单个节点限制的key个数设置为6之后，一个存储了7个数据的B树，查询id=7这个数据需要进行的磁盘IO为2次。
一次存储16个数据的B树，查询id=7这个数据所需要进行磁盘IO两次，相对于AVL树而言磁盘IO次数降低为一半。
所以数据索引数据结构的选型而言，B树是一个很不错的选择，总结来说，B树用作数据库索引有以下优点：
- 优秀的检索速度，时间复杂度：B树的查找性能等于O(h*logn)，其中h为树高，n为每个节点关键词的个数
- 尽可能减少的磁盘IO，加快了检索速度
- 可以支持范围查找
B+树
B树和B+树的有什么不同
- B树一个节点里存的是数据，而B+树存储的是索引(地址)，所以B树里一个节点存不了很多数据，但是B+树一个节点能够存很多索引，B+树叶子节点存所有数据。
- B+树的叶子节点是数据阶段用了一个链表串联起来，便于范围查找。
通过B树和B+树的对比我们看出，B+树节点存储的是索引，在单个节点存储容量有限的情况下，单节点也能存储大量索引，使得整个B+树高度降低，减少磁盘IO。其次B+树的叶子节点是真正数据存储的地方，叶子节点用了链表连接起来，这个链表本身就是有序的，在数据范围查找时更具备效率，因此MySQL的索引用的就是B+树，B+树在查找效率、范围查找中都有非常不错的性能。
InnoDB引擎和MyIsam引擎的实现
MySQL底层数据引擎以插件形式设计，最常见的是InnoDB引擎和MyIsam引擎，用户可以根据个人需求不同选择不同的引擎作为MySQL数据表的底层引擎，上面分析B+树作为MySQL的索引的数据结构非常适合，但是数据和索引到底怎么组织起来也是需要设计的，设计理念的不同也导致了InnoDB和MyIsam出现，各自呈现不同
性能。
MyIsam虽然数据查找性能极佳，但是不支持事务处理，InnoDB最大的特色就是支持了ACID兼容事务功能，而且支持行级锁，MySQL建立的时候可以指定引擎。
MyIsam引擎把数据和索引分开，一人一个文件，这叫做非聚集索引，InnoDB引擎把数据和索引放在同一个文件里，这叫聚集索引方式，下面从底层角度分析这两个索引怎么依靠B+树这个数据结构来组织引擎实现的。
MyIsam引擎的底层实现(非聚集索引方式)
MyIsam用的是非聚集索引方式，即数据和索引落在不同两个文件上，MyIsam在建表时以主键作为key来建立主索引B+树，树的叶子节点存的是对应数据的物理地址，我们拿到这个物理地址后，就可以到MyIsam数据文件直接定位到具体的数据记录了：
当我们为某个字段添加索引时，我们同样会生成这样的字段的索引树，这字段的索引树的叶子节点同样记录了对应数据的物理地址，然后也是拿着这个物理地址去数据文件里定位到具体数据记录。
InnoDB引擎底层实现(聚集索引方式)
InnoDB是聚集索引方式因此数据和索引都存储在同一个文件里。首先InnoDB会根据主键ID作为key建立索引B+树，如下图所示，而B+树的叶子节点存储的是主键ID对应的数据，比如执行select * from user_info where id=15 这个语句，innoDB就会查询这颗主键ID索引B+树，找到对应的user_name='bob'
这是建表的时候InnoDB就会自动建立好主键ID索引树，这也是为什么MySQL在建表时必须指定主键的原因，当我们为表里某个字段加索引是InnoDB会怎么建立索引树？比如我们要给user_name这个字段加索引，那么InnoDB就会建立user_name索引B+树，节点里存的是user_name的key，叶子节点存储的数据是朱建宁key，注意叶子节点存储的是主键key，拿到主键key后，InnoDB才会去主键索引树根据刚在user_name索引树找到主键key查找对应的数据。
问题来了，为什么InnoDB只在主键索引树的叶子节点存储了具体数据，但是其他索引树却不存在具体数据，而要多此一举找到主键，在主键索引树找到对应的数据呢？
其实很简单，因为InnoDB需要节省存储空间，一个表里面可能有多个索引，InnoDB都会给每个家里索引的字段生成索引树，如果每个字段的索引树都存储了具体数据，那么这个表的索引树文件就变得非常巨大(数据极度冗余)，从节约磁盘空间的角度来说，真的没有必要每个字段索引树都存具体数据，通过这种看似多此一举的步骤，在牺牲较少的查询性能下节省了巨大的磁盘空间，这是非常值得的。
总结
MyISAM查询性能很好，从上面索引数据文件的设计看也能看出：MyISAM直接找到物理地址后就可以直接定位到数据记录，但是InnoDB查询到叶子节点后，还需要在查询一次主键索引树，才可以定位到具体数据，等于MyISAM一步就查询到了数据，但是InnoDB要两步，那当然MyISAM查询性能更高。
什么时候需要给表里字段添加索引：
- 较频繁的作为查询条件的字段应该创建索引
什么时候不适合添加索引：
- 唯一性太差的字段不适合单独创建索引，即使该字段频繁作为查询条件
- 更新非常频繁的字段不适合创建索引
