我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:王中王 > 顶级结点 >

MySQL 索引原理及设计

归档日期:05-06       文本归类:顶级结点      文章编辑:爱尚语录

  索引一直是数据库中非常重要的概念,所以了解索引相关的知识是转入后端开发中必不可少的一环。这篇文章是我从开始做后端开发之后至今学习关于索引知识的一个总结,从原先很多概念的模糊和不理解到现在大致有一个比较清楚的认知,尽量会把关于索引的一些点以及为什么需要这么做给解释明白,包括使用 InnoDB 引擎的 MySQL 索引的相关概念,以及如何针对 InnoDB 进行索引的设计和使用,以及三星索引的概念,会从我所了解到的知识去解释为什么需要这样,如果有错误的地方还请指出。

  在 InnoDB 中,索引使用的数据结构是B+ Tree,这里的B是Balance的意思。B 类树的一个很鲜明的特点就是树的层数比较少,而每层的节点都非常多,树的每个叶子节点到根节点的距离都是相同的(这也是为什么叫Balance Tree的原因)。

  另外,树的每一个节点都是一个数据页,这样每个节点只需要一次 IO 就可以全部读取。这样的结构保证了查询数据时能尽量少地进行磁盘 IO,同时保证 IO 的稳定性。

  B+ Tree和B Tree不同,B+ Tree中,只能将数据存储在叶子结点中,内部节点将只包含指针,而B Tree可以将数据存储在内部的叶节点中。

  因此B+ Tree的关键优势是中间节点不包含数据,因此B+ Tree的大小远小于B Tree,并且可以将更多数据存储到存储器中。另外,B+ Tree的每一个叶子节点包含了到相邻的节点的链接,这样可以快速地进行范围遍历。

  在 InnoDB 存储引擎中,每一个索引都对应一棵B+ Tree,InnoDB 的索引主要分为主索引和辅助索引:

  就是主索引,也就是主键,也被称为聚簇索引。因为无法同时把数据行存放在两个不同的地方,所以一个表只能有一个聚集索引。在 InnoDB 中,主索引的叶子节点存的是整行数据,这也意味着 InnoDB 中的表一定要有一个主索引;

  就是辅助索引。InnoDB 中的辅助索引在叶子节点中并不存储实际的数据,只会包含主索引的值 。这就意味着如果使用辅助索引进行数据的查找,只能查到主索引,然后根据这个主索引再次扫描以下主索引的树,进行一次回表操作;

  上面讲到,InnoDB 的表中要求必须有一个主键,那么可能有人会将身份证号这种唯一性的标识作为主索引,这样就大错特错了。刚刚说到主键也被称为聚簇索引,它是要按照顺序进行排序的,要求有聚簇性。如果将身份证号作为主键,不能保证每次插入的数据都是按照身份证号的顺序进行排列的,这就使得每次主键的插入都变得完全随机,可能导致每次插入一条数据都会引起页分裂的问题(这个话题在后面会讲到)。

  所以在表结构定义的时候,应该使用一个具有聚集性的key作为主键,如果真的没有的话,可以使用一个AUTO INCREMENT代理键作为主索引,这样可以保证数据行是顺序写入的。如果你真的完全没有定义主键,InnoDB 会选择一个唯一的非空索引代替,但是如果没有这样的索引,InnoDB 会隐式定义一个主键来作为聚集索引。

  以上几点也基本上代表常听到的“最左前缀”,我们通过几个例子来解释一下这个问题,可能有的情况举的例子不太恰当,但希望能说明白想说出的问题。假设我们有一个 employees 表,表结构如下:

  这个表中我们有 (name, age, gender) 这个联合索引,这个索引的结构大概如下图所示:

  在上面的叶子节点下,假设有多个名为 BX 和 iCell 的员工,他们的年龄都不太一样,是先按照 name 排序,再按照 age 进行排序。

  上述这种查询,根据 (name, age, gender) 这个索引树来查找,找到 id 为 2 的索引数据符合条件,然后通过相邻的节点链接继续查找,发现下一个数据不符合条件,最终命中索引的就是 id 为 2 的这一条数据,因为是要查找行的所有数据,所以再根据 id 为 2 去主键索引树中继续回表查找,得到结果数据。

  根据 (name, age, gender) 这个索引树来查找,找到 id 为 3 的索引数据符合条件,然后通过相邻的节点链接继续查找,发现下一个数据也符合条件,继续根据节点链接查找,直到发现数据已经不符合条件了,于是命中索引的就是 id 为 3,4,5 的几条数据,然后继续根据这几个 id 值进行回表操作,得到结果数据。

  根据“最左前缀”原则,并不存在 age 为前缀的索引,所以这个查询无法使用 (name, age, gender) 这个索引树进行数据查找,得去主索引中进行全表扫描,这无非是非常慢的。所以如果想让这个查询命中索引,得单独为 age 添加索引或者添加 age 为前缀的联合索引。或者,这类情况还有一种方法,就是给跳过的索引列使用 IN 的查询方式让其发生“最左前缀”匹配,但是在这里 name 这个字段不适合用 IN 这种查询方法。

  由于 B+ Tree 的限制,当查询中出现有某个列的范围查询,则这个范围查询后面的列都无法使用索引。上面的查询中,like B%和 age 18都是范围查询,所以后面的查询不能通过索引树来直接查找。

  对于此种情况,MySQL 5.6 版本增加了Index Condition Pushdown技术,如果查询中 where 语句可以使用索引中已有的字段(比如这里就是 name,age, gender),在遍历索引时对这些字段先做判断直接过滤掉不满足条件的值,减少引擎层访问表的次数和 MySQL Server 层访问存储引擎的次数。但是这种技术跟“最左前缀”并无冲突,只是做了数据过滤的优化。

  注意看之前的数据表定义,employee_id 是 varchar 类型,但这个查询语句中将其与数字类型做比较,这时候会触发 MySQL 的隐式类型转换,将字符串转换成数字进行比较,也就是说上述的语句相当于:

  也就是说,在这个查询中对索引字段做了函数操作,而这样的话会破坏索引值的有序性,于是不会命中索引,转而进行全表扫描。

  这种情况类似于查询 2 中所举的例子,但是这个查询的结果要求只返回 age 和 gender,而 age 和 gender 的值是包含在索引中的,这样就可以直接返回而不用再进行回表查询了。如果一个索引包含所有需要查询的字段的值,则为覆盖索引,使用覆盖索引不需要进行回表操作,能增加数据查询效率

  要说 ORDER BY 如何利用索引进行排序,得先弄清楚 ORDER BY 本身是如何进行排序的。在 MySQL 中,会给每个线程分配一块内存空间buffer用于排序,还有一个参数叫做 max_length_for_sort_data,这个参数作用是用来规定排序返回行的字段长度,默认值是 1024,最小值为 4,如果排序返回行的字段长度没有超过这个参数的值,就会使用一次访问排序,否则使用二次访问排序。

  现在我们还是通过上面这张 employees 表来说明问题,有以下语句:

  现在我要查的排序的返回字段只包括 name, age 和 employee_id,在默认情况下肯定不会超过 1024,所以会使用一次访问排序,流程如下:

  那么假设我现在的 max_length_for_sort_data 的值很小,要查询的返回子段长度超过了这个值,那就会使用二次访问排序,流程如下:

  以上两种排序,无非是 MySQL 认为内存够不够用,够用的话就多利用内存而避免过多的回表操作从而增加磁盘访问。那如果排序申请的内存空间不过用了怎么办?参数 sort_buffer_size 就是控制排序内存空间大小的,如果内存不够用,就会使用磁盘临时文件做外部归并排序。

  知道了以上排序操作,再结合之前覆盖索引以及B+ Tree索引的逻辑,是不能就有办法去优化 ORDER BY 的流程了。首先,不管是一次访问排序还是二次访问排序,都要在buffer对数据做排序操作,而B+ Tree本身的叶子结点就是有序排列的,所以只要能做到排序行也能按照最左匹配原则匹配到索引,就可以避免内存排序的步骤了。另外,上述的排序步骤中还需要进行回表操作,那么只要查询的语句能命中覆盖索引,是不是就能够避免回表操作了。进一步,如何可以使用同一个索引既满足排序又用于查找行那就相当不错了。

  但是三星索引往往是理想中的情况,现实状况下往往会同时有范围查询和排序的需求出现,这样就很难同时满足第一颗星和第二颗星,比如下列语句:

  前面说到,InnoDB 中数据是存储在数据页中的,而数据是按照索引的顺序插入到数据页中的,所以数据是紧凑排序的,但如果随机对数据进行插入,就有可能导致数据页分裂的问题。

  假设一个数据页只能存储 3 条数据,且已经有 3 条数据(100, 200, 300)了,这时候想插入一条 150 的数据,就会再申请一个新的数据页,100,150 两条数据存放在原来的数据页中,200 和 300 存放在新的数据页中,这样可能会存在数据页利用率不高的问题。

  不仅仅是插入数据会导致上述问题,删除数据也会。这里要注意,如果删除掉了一个数据页中的某条数据,这条数据所留下的位置并不会缩小而是等待复用,如果是一整个页的数据被删除了,那这个页也是出于被复用状态。如果相邻的两个数据页的利用率很小,系统会把这两个页的数据合到其中一个页上,另一个页就处于可被复用的状态。所以通过 delete 删除数据并不会回收表空间。

  为了解决频繁删除数据导致的没有回收表空间的问题,可以通过重建表来解决,比如以下命令:

  所以我们使用AUTO INCREMENT主键的插入数据模式,正符合了递增插入的场景。每次插入一条新记录,都是追加操作,都不涉及到挪动其他记录,也不会触发叶子节点的分裂。

  以上便是我对所学索引相关知识的一些总结,可能有些疏漏或者错误的地方。但是索引一直学过来感觉是一个涉及面非常广的知识点,这篇文章也只能算是一个学习笔记,在之后的实践过程中遇到什么值得记录的还会继续进行补充。返回搜狐,查看更多

本文链接:http://brazil-run.com/dingjijiedian/279.html