玩转Mysql系列 - 第21篇：什么是索引？
这是Mysql系列第21篇。
本文开始连续3篇详解mysql索引：
-
第1篇来说说什么是索引？
-
第2篇详解Mysql中索引的原理
-
第3篇结合索引详解关键字explain
本文为索引第一篇：我们来了解一下什么是索引？
路人在搞计算机之前，是负责小区建设规划的，上级领导安排路人负责一个万人小区建设规划，并提了一个要求：可以快速通过户主姓名找到户主的房子；让路人出个好的解决方案。
方案1
刚开始路人没什么经验，实在想不到什么好办法。
路人告诉领导：你可以去敲每户的门，然后开门之后再去询问房主姓名，是否和需要找的人姓名一致。
领导一听郁闷了：我敲你的头，1万户，我一个个找，找到什么时候了？你明天不用来上班了。
这里面涉及到的时间有：走到每户的门口耗时、敲门等待开门耗时、询问户主获取户主姓名耗时、将户主姓名和需要查找的姓名对比是否一致耗时。
加入要找的人刚好在最后一户，领导岂不是要疯掉了，需要重复1万次上面的操作。
上面是最原始，最耗时的做法，可能要找的人根本不在这个小区，白费力的找了1万次，岂不是要疯掉。
方案2
路人灵机一动，想到了一个方案：
-
给所有的户主制定一个编号，从1-10000，户主将户号贴在自家的门口
-
路人自己制作了一个户主和户号对应的表格，我们叫做：
户主目录表，共1万条记录，如下：
| 户主姓名 | 房屋编号 |
|---|---|
| 刘德华 | 00001 |
| 张学友 | 00002 |
| 路人 | 00888 |
| 路人甲java | 10000 |
此时领导要查找路人甲Java时，过程如下：
-
按照姓名在
户主目录表查找路人甲Java，找到对应的编号：10000 -
然后从第一户房子开始找，查看其门口户号是否是10000，直到找到为止
路人告诉领导，这个方案比方案1有以下好处：
-
如果要找的人不在这个小区，通过
户主目录表就确定，不需要第二步了 -
步骤2中不需要再去敲每户的门以及询问户主的姓名了，只需对比一下门口的户号就可以了，比方案1省了不少时间。
领导笑着说，不错不错，有进步，不过我找路人甲Java还是需要挨家挨户看门牌号1万次啊！。。。。。你再去想想吧，看看是否还有更好的办法来加快查找速度。
路人下去了苦思冥想，想出了方案3。
方案3
方案2中第2步最坏的情况还是需要找1万次。
路人去上海走了一圈，看了那边小区搞的不错，很多小区都是搞成一栋一栋的，每栋楼里面有100户，路人也决定这么搞。
路人告诉领导：
-
将1万户划分为100栋楼，每栋楼有25层，每层有4户人家，总共1万户
-
给每栋楼一个编号，范围是[001,100]，将栋号贴在每栋楼最显眼的位置
-
给每栋楼中的每层一个编号，编号范围是[01,25]，将层号贴在每层楼最显眼的位置
-
户号变为：栋号-楼层-层中编号，如
路人甲Java户号是：100-20-04，贴在每户门口
户主目录表还是有1万条记录，如下：
| 户主姓名 | 房屋编号 |
|---|---|
| 刘德华 | 001-08-04 |
| 张学友 | 022-18-01 |
| 路人 | 088-25-04 |
| 路人甲java | 100-25-04 |
此时领导要查找路人甲Java时，过程如下：
-
按照姓名在
户主目录表查找路人甲Java，找到对应的编号是100-25-04，将编号分解，得到：栋号（100）、楼层（25）、楼号（04） -
从第一栋开始找，看其栋号是否是100，直到找到编号为100为止，这个过程需要找100次，然后到了第100栋楼下
-
从100栋的第一层开始向上走，走到每层看其编号是否为25，直到走到第25层，这个过程需要匹配25次
-
在第25层依次看看户号是否为
100-25-04，匹配了4次，找到了路人甲Java
此方案分析：
-
查找
户主目录表1万次，不过这个是在表格中，不用动身走路去找，只需要动动眼睛对比一下数字，速度还是比较快的 -
将方案2中的第2步优化为上面的
2/3/4步骤，上面最坏需要匹配129次（栋100+层25+楼号4次），相对于方案2的1万次好多了
领导拍拍路人的肩膀：小伙子，去过上海的人确实不一样啊，这次方案不错，不过第一步还是需要很多次，能否有更好的方案呢？
路人下去了又想了好几天，突然想到了我们常用的字典，可以按照字典的方式对方案3中第一步做优化，然后提出了方案4。
方案4
对户主表进行改造，按照姓的首字母(a-z)制作26个表格，叫做：姓氏户主表，每个表格中保存对应姓氏首字母及所有户主和户号。如下：
| 姓首字母：A | |
|---|---|
| 姓名 | 户号 |
| 阿三 | 010-16-01 |
| 阿郎 | 017-11-04 |
| 啊啊 | 008-08-02 |
| 姓首字母：L | |
|---|---|
| 姓名 | 户号 |
| 刘德华 | 011-16-01 |
| 路人 | 057-11-04 |
| 路人甲Java | 048-08-02 |
现在查找户号步骤如下：
-
通过姓名获取姓对应的首字母
-
在26个表格中找到对应姓的表格，如
路人甲Java，对应L表 -
在L表中循环遍历，找到
路人甲Java的户号 -
根据户号按照方案3中的(2/3/4)步骤找对应的户主
理想情况：
1万户主的姓氏分配比较均衡，那么每个姓氏下面分配385户（10000/26） ，那么找到某个户主，最多需要:26次+385次 = 410次，相对于1万次少了很多。
最坏的情况：
1万个户主的姓氏都是一样的，导致这1万个户主信息都位于同一个姓氏户主表，此时查询又变为了1万多次。不过出现姓氏一样的情况比较低。
如果担心姓氏不足以均衡划分户主信息，那么也可以通过户主姓名的笔画数来划分，或者其他方法，主要是将用户信息划分为不同的区，可以快速过滤一些不相关的户主。
上面几个方案为了快速检索到户主，用到了一些数据结构，通过这些数据结构对户主的信息进行组织，从而可以快速过滤掉一些不相关的户主，减少查找次数，快速定位到户主的房子。
索引是什么？
通过上面的示例，我们可以概况一下索引的定义：索引是依靠某些数据结构和算法来组织数据，最终引导用户快速检索出所需要的数据。
索引有2个特点：
-
通过数据结构和算法来对原始的数据进行一些有效的组织
-
通过这些有效的组织，可以引导使用者对原始数据进行快速检索
mysql为了快速检索数据，也用到了一些好的数据结构和算法，来组织表中的数据，加快检索效率。