专栏首页路人甲Java玩转Mysql系列 - 第21篇:什么是索引?

玩转Mysql系列 - 第21篇:什么是索引?

这是Mysql系列第21篇。

本文开始连续3篇详解mysql索引:

  1. 第1篇来说说什么是索引?
  2. 第2篇详解Mysql中索引的原理
  3. 第3篇结合索引详解关键字explain

本文为索引第一篇:我们来了解一下什么是索引?

路人在搞计算机之前,是负责小区建设规划的,上级领导安排路人负责一个万人小区建设规划,并提了一个要求:可以快速通过户主姓名找到户主的房子;让路人出个好的解决方案。

方案1

刚开始路人没什么经验,实在想不到什么好办法。

路人告诉领导:你可以去敲每户的门,然后开门之后再去询问房主姓名,是否和需要找的人姓名一致。

领导一听郁闷了:我敲你的头,1万户,我一个个找,找到什么时候了?你明天不用来上班了。

这里面涉及到的时间有:走到每户的门口耗时、敲门等待开门耗时、询问户主获取户主姓名耗时、将户主姓名和需要查找的姓名对比是否一致耗时。 加入要找的人刚好在最后一户,领导岂不是要疯掉了,需要重复1万次上面的操作。

上面是最原始,最耗时的做法,可能要找的人根本不在这个小区,白费力的找了1万次,岂不是要疯掉。

方案2

路人灵机一动,想到了一个方案:

  1. 给所有的户主制定一个编号,从1-10000,户主将户号贴在自家的门口
  2. 路人自己制作了一个户主和户号对应的表格,我们叫做:户主目录表,共1万条记录,如下:

户主姓名

房屋编号

刘德华

00001

张学友

00002

路人

00888

路人甲java

10000

此时领导要查找路人甲Java时,过程如下:

  1. 按照姓名在户主目录表查找路人甲Java,找到对应的编号:10000
  2. 然后从第一户房子开始找,查看其门口户号是否是10000,直到找到为止

路人告诉领导,这个方案比方案1有以下好处:

  1. 如果要找的人不在这个小区,通过户主目录表就确定,不需要第二步了
  2. 步骤2中不需要再去敲每户的门以及询问户主的姓名了,只需对比一下门口的户号就可以了,比方案1省了不少时间。

领导笑着说,不错不错,有进步,不过我找路人甲Java还是需要挨家挨户看门牌号1万次啊!。。。。。你再去想想吧,看看是否还有更好的办法来加快查找速度。

路人下去了苦思冥想,想出了方案3。

方案3

方案2中第2步最坏的情况还是需要找1万次。

路人去上海走了一圈,看了那边小区搞的不错,很多小区都是搞成一栋一栋的,每栋楼里面有100户,路人也决定这么搞。

路人告诉领导:

  1. 将1万户划分为100栋楼,每栋楼有25层,每层有4户人家,总共1万户
  2. 给每栋楼一个编号,范围是[001,100],将栋号贴在每栋楼最显眼的位置
  3. 给每栋楼中的每层一个编号,编号范围是[01,25],将层号贴在每层楼最显眼的位置
  4. 户号变为:栋号-楼层-层中编号,如路人甲Java户号是:100-20-04,贴在每户门口

户主目录表还是有1万条记录,如下:

户主姓名

房屋编号

刘德华

001-08-04

张学友

022-18-01

路人

088-25-04

路人甲java

100-25-04

此时领导要查找路人甲Java时,过程如下:

  1. 按照姓名在户主目录表查找路人甲Java,找到对应的编号是100-25-04,将编号分解,得到:栋号(100)、楼层(25)、楼号(04)
  2. 从第一栋开始找,看其栋号是否是100,直到找到编号为100为止,这个过程需要找100次,然后到了第100栋楼下
  3. 从100栋的第一层开始向上走,走到每层看其编号是否为25,直到走到第25层,这个过程需要匹配25次
  4. 在第25层依次看看户号是否为100-25-04,匹配了4次,找到了路人甲Java

此方案分析:

  1. 查找户主目录表1万次,不过这个是在表格中,不用动身走路去找,只需要动动眼睛对比一下数字,速度还是比较快的
  2. 将方案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

现在查找户号步骤如下:

  1. 通过姓名获取姓对应的首字母
  2. 在26个表格中找到对应姓的表格,如路人甲Java,对应L表
  3. 在L表中循环遍历,找到路人甲Java的户号
  4. 根据户号按照方案3中的(2/3/4)步骤找对应的户主

理想情况:

1万户主的姓氏分配比较均衡,那么每个姓氏下面分配385户(10000/26) ,那么找到某个户主,最多需要:26次+385次 = 410次,相对于1万次少了很多。

最坏的情况:

1万个户主的姓氏都是一样的,导致这1万个户主信息都位于同一个姓氏户主表,此时查询又变为了1万多次。不过出现姓氏一样的情况比较低。

如果担心姓氏不足以均衡划分户主信息,那么也可以通过户主姓名的笔画数来划分,或者其他方法,主要是将用户信息划分为不同的区,可以快速过滤一些不相关的户主。

上面几个方案为了快速检索到户主,用到了一些数据结构,通过这些数据结构对户主的信息进行组织,从而可以快速过滤掉一些不相关的户主,减少查找次数,快速定位到户主的房子。

索引是什么?

通过上面的示例,我们可以概况一下索引的定义:索引是依靠某些数据结构和算法来组织数据,最终引导用户快速检索出所需要的数据。

索引有2个特点:

  1. 通过数据结构和算法来对原始的数据进行一些有效的组织
  2. 通过这些有效的组织,可以引导使用者对原始数据进行快速检索

mysql为了快速检索数据,也用到了一些好的数据结构和算法,来组织表中的数据,加快检索效率。

本文分享自微信公众号 - 路人甲Java(javacode2018)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Word中使用代码高亮插件

    一年前我写了一个word2010的代码高亮插件,但当时那个版本有一个问题:在用word发布博客的时候,高亮的代码在博客中的格式乱了。今天有空改了一下这个插件,虽...

    明年我18
  • 在GAE中使用struts2框架

    在确定了IDE和Server之后,就要选择一个web框架了。我选择的是struts2,因为它的使用率很高,网上也很多资源,遇到问题好查。

    明年我18
  • MyEclipse的安装和汉化

    我不愿意直接用notepad去编辑java代码,因为我要从实际的Project中感受java,不需要一开始就从compile学起,当初学C#的时候不也...

    明年我18
  • 文末送书 | Python的高级特征你知多少?

    开篇先说,IEEE Spectrum 于9月6日发布了2019年最受欢迎的编程语言排名,无疑Python蝉联第一,成绩颇为亮眼。从前年开始,Python 就开始...

    用户1737318
  • 开发一个Word的代码高亮插件

    在用Word写技术文档的时候,免不了要在文档中插入一些源代码。为了使插入进来的源代码更可读,就需要使这些代码的关键字高亮显示。所以在写这些文档的时候,我经常需要...

    明年我18
  • Spring------自动化装配Bean(二) 一、在soundsystem 中新建JavaConfig2

    上一篇是基于 @ComponentScan自动装配Bean的实现,这一篇将通过java手动装配bean来实现。

    用户2417870
  • Ant学习

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    suveng
  • 使Spring.NET的IOC容器支持动态加载的程序集

    当我们发布系统时,有时候希望不用关掉应用程序就能完成发布,但Spring.NET的ApplicationContext是从AppDomain.Curr...

    明年我18
  • Spring------自动化装配Bean(三) 一、打开application.xml

    上一篇是基于java手动装配bean的实现,这一篇将通过xml手动装配bean来实现。

    用户2417870
  • Spring------自动化装配Bean(一) 一、创建 CompactDisc接口和SgetPeppers实现类二、启用spring组件扫描三、编写测试类,并运行 四、补充说明

      CompactDisc接口方法为播放。SgtPeppers实现CompactDisc接口。

    用户2417870

扫码关注云+社区

领取腾讯云代金券