MySQL索引数据结构分析
摘要
本文讨论MySQL数据库索引数据结构相关的一些话题，重点在于常用的B+Tree索引以及性能十分高的Hash索引的数据组织方式；还包括B+Tree索引中的聚集索引和非聚集索引，以及B+Tree索引和Hash索引使用的到复合索引数据组织方式。
Hash索引
在MySQL的存储引擎中，由于InnoDB和MyISAM默认都是使用的B+Tree索引，所以通常情况我们都是是用的B+Tree索引。尽管hash索引并不是非常常见，但是我认为hash索引也是需要掌握的，Mermory默认使用的Hash索引。
MySQL中的Hash索引是基于hash table实现的，只有精确匹配索引所有列的查询才会生效。对于表中的每一行数据，MySQL都会为其中的所有索引列计算一个hash code （利用hash算法计算）,使用mysql的select语言进行查询操作时，会根据where后面的条件索引列计算出hash code，利用这个hash code可以直接获取到对应记录的地址。当然，可能存在不同组合索引值计算出了相同的hash code，这就是hash冲突。对于hash冲突，我们通常有两种办法: 1. 开放地址法； 2. 拉链法（关闭地址法）
- 只有使用=，!=, <>时才能使用到hash索引，即只能使用等值查询，不能使用范围查询。
- hash索引无法被用来避免数据的排序操作，什么意思呢？其实就是如果需要进行order by操作，根据hash索引获取到的数据还得进行一次排序，不能像B+Tree一样，根据索引拿到的数据可以直接排好序。
- hash索引必须使用所有索引列进行查询，因为hash code是经过所有索引列计算出来的。所以通过组合索引的前面一个或几个索引键进行查询的时候，hash索引将无法被利用。
- hash索引在任何时候都不能避免表扫描，由于根据hash table存在多个key对应一个hash code，所以一旦hash code相同的情况下，必须根据表中实际数据对比获取想要查找的结果。
- hash索引遇到大量hash值相等的情况后性能并不一定就会比BTree索引高。对于选择性比较低的索引键，如果创建Hash索引，那么会有大量的key对应同一个hash code；根据第4点我们知道，此时是要进行表扫描的，这时定位一条记录，会浪费多次表数据的访问，而造成整体性能低下。
B+Tree索引
在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对B+Tree索引的实现方式有所不同，这里就主要分析MyISAM通过非聚集索引的方式实现的B+Tree索引和InnoDB通过聚集索引的方式实现的B+Tree。
MyISAM引擎实现方式
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。图二是MyISAM索引的原理图：
InnoDB实现方式
虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。最大区别就在于InnoDB的数据文件本身就是索引文件。而MyISAM索引文件和数据文件是分离的，索引文件仅仅保存数据记录的地址。在InnoDb中，数据文件本身就是按B+Tree组织的一个索引结构，这个B+Tree的叶子节点会存储完整的数据记录。这个索引的key是数据表的主键。因此InnoDB表数据文件本身就是primary key。而如果没有显示地为表声明主键，InnoDB则会隐式地创建主键索引树。
复合索引
对于mysql中的复合索引（使用B+Tree索引），不管是基于聚集索引还是非聚集索引，其实与普通索引并没有什么区别，只是每一个节点存储的数据列发生了变化，主要是复合索引的树节点中存储的将会是复合索引的所有列组合，可以参考图五（取自高性能mysql）内容进行分析。
