数据库，相信各位开发都不陌生，常见的比如Mysql，Oracle等，随着我们业务量的提升，数据量的不断增加，导致的问题就是普通查询的速度越来越慢，对查询进行优化，就用到了我们今天的主角，索引。
索引是什么？索引是一种数据结构，划重点了，是数据结构!!!，能够帮助我们快速找到数据库中数据，今天咱们介绍两种常见的索引，Hash索引和B+Tree索引，这里得提到一点，索引种类是和存储引擎有关的，但是不同的引擎就算类型一致底层实现也可能不一样，列举几个常见的存储引擎：
首先我们来看下，Hash索引，这个底层的数据结构特别像，JDK1.7及以前的HashMap的底层结构，数组加链表的形式，举个例子吧，假如我们数据库里有如下记录，并且在Memory（默认Hash索引）引擎里使用Hash索引给fname字段加了索引：
当我们存数据的时候，就会触发，通过hash函数把fname这个字段转成hash码，假设我们通过计算返回的hash码如下：
f('Arjen') = 2323
f('Baron') = 7437
f('Peter') = 8784
f('Vadim') = 2458
那么存到索引里就是这个结果：
当发生了，select lname from hashtest where fname = 'Peter';时， 先计算‘Peter’的哈希值，并使用该值寻找对于的记录指针。因为 f('Peter') = 8784 ，所以 MySQL 在索引中查找 8784，可以找到指向第 3 行的指针，最后一步是比较第三行的fname 值是否为‘Peter’，以确保就是要查找的行。
当然了这是最简单的没有发生hash冲突的情况，啥是hash冲突，就是fname都是相同的比如f('Peter') = 8784 ，这时候他们通过hash函数算出来的结果是一样的，都会存在同一个位置，以链表的形式存下来，实际发生了 where fname = 'Peter'时，找到的是一个链表，依次看每个指针对应的行记录上值是不是需要的，需要就返回。看完这个原理，小编第一感觉就是，这和JDK1.7的HashMap的底层实现好类似呀，如果那个原理懂了，这个也很容易理解，包括什么hash函数，hash冲突啥的，小编以前都有说明的。哈希索引适合等值查询，但是无法进行范围查询，哈希索引没办法利用索引完成排序 ，哈希索引不支持多列联合索引的最左匹配规则 ，如果有大量重复键值的情况下，哈希索引的效率会很低，因为存在哈希碰撞问题
B+Tree（这是一种数据结构，自己去了解下吧）索引，这个吧其实和JDK1.8的HashMap的底层红黑树有点类似，B树是一种多路平衡查询树，所以他的节点是天然有序的（左子节点小于父节点、父节点小于右子节点），所以对于范围查询的时候不需要做全表扫描，在不同的存储引擎里实现还不一样，咱们先看下MyISAM引擎里索引的实现：
可以看到整个结构就是个树，第一层15-56,56-77,77以后等，分成了三段，第二层是把15-56之间继续细分，到15-20,20-49,49以后，第三层15-20继续下分到15和18俩元素，15和18其实是我们表里的主键（假设Col1是主键），实际存的是主键对应的行记录的地址（不存整个数据的索引叫非聚集索引）,非主键的辅助索引，除了可以重复外其他和刚才的主键索引并无多大区别。
咱们上面说了，同样是B+Tree索引，引擎不同实现可能不同，InnoDB索引的实现就和MyISAM截然不同，第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引，如图：
可以看到，在15和18下面存的是全部数据，15和18是主键，34和77是Col2列，Bob和Alice是Col3列，整个索引把整个表的数据都存下来了，这是主键索引，这也是为啥说，InnoDB引擎要求必须要有主键的原因，如果你没设置主键，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型，像这种把数据存下来的叫聚集索引。
接着咱们再来对比下，InnoDB引擎的非主键辅助索引和MyISAM的辅助索引的区别，最大的区别是，叶子结点存的不在是行记录的地址，而是存的主键，如图：
可以看到，英文的字段辅助索引默认排序也可以看出来是，按照A-Z的顺序排列的，叶子结点存的都是18，15这样对应的主键，由此可以看出，他实际找的时候是先找到主键，然后根据主键去表里一个一个查对比，找到自己需要的数据。这个情况叫回表，也有不需要回表的操作（覆盖索引），比如一个组合索引Col3,Col2,如果查询 select Col3 from table where Col2='XX',这时候因为Col3,Col2的值都存在组合索引里，不需要再去表里查询Col3的值就可以返回结果。
看了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键了吧，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一棵B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
最后，大家想获取更多知识的，可以继续关注公众号，不定时推送。分享了这么牛逼的知识，还不请小编喝个水吗，哈哈哈，欢迎土豪直接赏赞，谢谢，您的支持就是小编最大的动力。
