欢迎关注MySQL专栏MySQL历险记
强烈建议收藏本导航文【MySQL历险记】MySQL的核心特性汇总

前语

MySQL的索引是一个十分重要的知识点，也基本上是面试必考的一个技能点，所以十分重要。那你了解MySQL索引的数据结构是怎样样的吗？为什么要采用这样的数据结构？

现在化身为MySQL的架构师，一步步迭代规划出MySQL的索引结构，确保你再也忘记不了索引的结构了，轻松经过面试。

索引介绍

MySQL表中存储的数据量十分大，或许有上亿条记载，假如一条条去匹配，便是所谓的全表扫描，会十分的慢。那么有什么办法呢？

想想咱们生活中的比如，比如新华字典，咱们有一个目录，目录依据拼音排序，内容包括了汉字坐落字典中具体的的页码。聪明的你肯定也想到了，咱们也能够学习这种思想，树立一个MySQL的目录，叫做“索引”。

所以你对“索引”做了笼统和界说：索引（Index）是协助MySQL高效获取数据的数据结构。

索引是在存储引擎中实现的，因而每种存储引擎的索引不一定完全相同，MySQL有InnoDB、MyISAM、Memory等存储引擎，你想了下，就拿最常用的InnoDB作为存储引擎规划索引。

索引规划方针

你现在拼命转动大脑，开端去考虑怎样规划出这样的一个索引结构。你就在脑子里想，索引规划中需求处理哪些问题，以及要达成什么样的方针。

  1. 我要怎样样才干在索引目录（数据结构）中快速找到具体的某条数据记载呢？那么这个数据结构需求有顺序规则，我依照这个规则就能够定位到具体的某条数据。
  2. MySQL中的数据中的记载怎样能够快速找到呢？是不是能够将记载进行排序，然后依据 二分法 快速找到对应的数据记载。
  3. MySQL中架构老迈一开端界说数据是依照数据页寄存的，每个数据页默许是16kb, 每次满了，就会重新有新的一页。我的索引目录数据应该也是放到页中，而且索引的数据尽量少些，这样每页能够放更多的目录信息。
  4. 我怎样样才干查询效率最高呢？其实每次慢都是慢在磁盘IO上，我再后边规划中一定要削减磁盘IO的拜访，越少拜访磁盘IO越好。
  5. 磁盘中的空间仍是不接连的啊，那我还得有个指针去连接下一条记载的方位。

带着这些问题和考虑，你开端规划啦。

索引规划迭代

你想着我就拿一个比如具象化的考虑规划索引。

下面是一个新建的表：

CREATE TABLE demo(
	c1 INT,
	c2 INT,
	c3 CHAR(1),
	PRIMARY KEY(c1)
) ROW_FORMAT = Compact;

行记载的格局简化如下：

一步步带你设计MySQL索引数据结构

咱们只在示意图里展示记载的这几个部分：

  • record_type：记载头信息的一项特点，表明记载的类型， 0 表明一般记载、 2 表明最小记载、 3 表明最大记载、 1 暂时还没用过，下面讲。
  • next_record：记载头信息的一项特点，表明下一条地址相对于本条记载的地址偏移量，咱们用箭头来表明下一条记载是谁。
  • 各个列的值：这儿只记载在 index_demo 表中的三个列，别离是 c1 、 c2 和 c3 。
  • 其他信息：除了上述3种信息以外的一切信息，包括其他躲藏列的值以及记载的额外信息。

把一些记载放到页里的示意图便是：

一步步带你设计MySQL索引数据结构

注意：一页能够寄存16kb的数据，并不是图上的3条数据，这儿只是一个示例。

迭代一

咱们为什么要遍历一切的数据页或者记载？由于各个页中的记载并没有规则，不知道这条数据出现在哪个数据页中。那么怎样快速定位要查找的数据在哪个数据页中呢？咱们需求树立一定的规则，如下：

  1. 下一个数据页中用户记载的主键值必须大于上一个页中用户记载的主键值。

一步步带你设计MySQL索引数据结构

  • 页中的数据依据主键按顺序排序
  • 不同页中的数据，下一页数据大于上一页数据
  • 新分配的数据页编号或许并不是接连的。它们只是经过保护者上一个页和下一个页的编号而树立了 链表 联系
  1. 给一切的页树立一个目录项

一步步带你设计MySQL索引数据结构

  • key表明目录中最小的主键值。
  • page_on表明对应的页码。

查找主键值为 20 的记载，具体查找进程分两步：

  1. 先从目录项中依据二分法快速确认出主键值为 20 的记载在 目录项3 中（由于 12 < 20 < 209 ），它对应的页是页9。

  2. 再依据前边说的在页中查找记载的方式去页9中定位具体的记载。

迭代二

迭代一中的目录项是怎样存储的呢？咱们是不是也能够用行记载格局存储到数据页中呢。答案是肯定的，咱们经过行记载格局中的record_type等于1表明是目录记载，如下图所示：

一步步带你设计MySQL索引数据结构

  • 目录项记载的 record_type 值是1，而 一般用户记载的 record_type 值是0。
  • 目录项记载只要主键值和页的编号两个列，而一般的用户记载的列是用户自己界说的，或许包括许多列 ，另外还有InnoDB自己添加的躲藏列。

现在以查找主键为 20 的记载为例，依据某个主键值去查找记载的进程就能够大致拆分红下边两步：

  1. 先到存储目录项记载的页，也便是页30中经过二分法快速定位到对应目录项，由于 12 < 20 < 209 ，所以定位到对应的记载所在的页便是页9。

  2. 再到存储用户记载的页9中依据二分法快速定位到主键值为20的用户记载。

迭代三

跟着数据量变多，必然一个目录项寄存不下，由于一页只要16kb巨细，就会割裂出多页，如下图所示：

一步步带你设计MySQL索引数据结构

那么现在查找主键值为 20 的记载，流程如下：

  1. 咱们现在的存储目录项记载的页有两个，即页30和页32 ，又由于页30表明的目录项的主键值的 规模是 [1, 320) ，页32表明的目录项的主键值不小于 320 ，所以主键值为 20 的记载对应的目录项记载在页30中。

  2. 经过目录项记载页确认用户记载实在所在的页。

  3. 在实在存储用户记载的页中定位到具体的记载。

迭代四

假如咱们表中的数据十分多则会发生许多存储目录项记载的页，假如直接这么查，也是很慢，咱们是不是能够针对目录项记载的页再生成一个更高档的目录，就像是一个多级目录一样，如下图所示：

一步步带你设计MySQL索引数据结构

那么现在查找主键值为 20 的记载，流程如下：

  1. 生成了一个存储更高档目录项的页33，这个页中的两条记载别离代表页30和页32, 主键20的记载在 [1, 320) 之间，则到页30中查找更具体的目录项记载。

  2. 在页30中经过二分法查找主键为20记载的用户记载页码。

  3. 在实在存储用户记载的页中定位到具体的记载。

迭代小结

以上这个数据结构便是咱们索引终究的数据结构，B+树， 图形描述如下：

一步步带你设计MySQL索引数据结构

  • 一切的叶子节点寄存全量的用户记载信息，包括一切的字段。
  • 一切的目录节点只寄存索引字段、主键以及对应的页码信息，要求信息越少越好，由于一页最多16kb，只要目录信息越少，每页寄存的信息越多，树的层级就越小，树的层级越小，那么和磁盘的IO就越少，查询就会越快。一般来说，B+树4层，就能够寄存上亿数据了。

索引结构总结

聚簇索引

咱们依照前面的迭代推演出了依据主键的索引结构，是一颗B+树，咱们把这种索引叫做聚簇索引。

一步步带你设计MySQL索引数据结构

特点：

  • 聚簇索引中的叶子节点寄存了用户记载的全部数据，它便是innoDB中数据寄存的格局，即数据即聚簇索引，聚簇索引即数据，这也是聚簇索引名字的由来吧，数据和索引集合在一起。
  • InnoDB要求表必须有主键。假如没有显式指定，则MySQL系统会自动挑选一个能够非空且仅有标识数据记载的列作为主键。假如不存在这种列，则MySQL自动为InnoDB表生成一个隐 含字段作为主键，这个字段长度为6个字节，类型为长整型，这样始终就会有一个聚簇索引。

非聚簇索引

既然有了聚簇索引，那么肯定有非聚簇索引，非聚簇索引也叫二级索引或者辅助索引。

它是在什么场景出现的呢？比如咱们想以别的列作为搜索条件，总不能是自始至终沿着链表依次遍历记载一遍，肯定要慢死了。这时候就需求树立非聚簇索引，那它的索引结构和聚簇索引有什么区别呢？

一步步带你设计MySQL索引数据结构

  • 索引目录的内容由3部分组成，索引列的值+主键值+页码，经过索引列的值+主键值仅有确认新刺进的列是在哪个页中，也能够仅有确认从那个页中查询。
  • 索引的叶子节点寄存内容为索引列的值+主键值。

那或许你有疑问了，只要主键值，我要查记载的其他信息怎样办呢？

咱们依据这个以c2列巨细排序的B+树只能确认咱们要查找记载的主键值，所以假如咱们想根 据c2列的值查找到完好的用户记载的话，依然需求到 聚簇索引 中再查一遍，这个进程称为 回表 。也就 是依据c2列的值查询一条完好的用户记载需求运用到 2 棵B+树！

回表的进程会耗时，为什么不直接寄存一切的数据记载呢？

假如把完好的用户记载放到叶子结点是能够不用回表。但是太占地方了，相当于每树立一课B+树都需求把一切的用户记载再都复制一遍，这就有点太浪费存储空间了。

联合索引

联合索引是一种特殊的非聚簇索引，那么它的数据结构又是怎样样的呢？

比方说咱们想让B+树依照c2和c3列的巨细进行排序，为c2和c3树立的索引的示意图如下：

一步步带你设计MySQL索引数据结构

  • 每条目录项都有c2、c3、主键、页号这4个部分组成，各条记载先依照c2列的值进行排序，假如记载的c2列相同，则依照c3列的值进行排序
  • B+树叶子节点处的用户记载由c2、c3和主键c1列组成。

索引长处和缺陷

咱们在了解了索引的数据结构今后，就更加了解索引的优缺陷了。

长处

  1. 进步数据查询的效率，下降数据库的IO本钱。
  2. 经过创立仅有索引，能够确保数据库表中每一行数据的仅有性。
  3. 在运用分组和排序子句进行数据查询时，能够明显削减查询中分组和排序的时刻，下降了CPU的消耗。

缺陷

  1. 创立索引和保护索引要消耗时刻，而且跟着数据量的添加，所消耗的时刻也会添加。
  2. 索引需求占磁盘空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间
  3. 下降更新表的速度。当对表中的数据进行添加、删除和修改的时候，索引也要动态地保护，这样就下降了数据的保护速度。
  4. 索引中的数据都是有序的，比如刺进一条主键较小的数据，必然导致其他数据进行移动，页码发生调整，这种现象也叫做页割裂，这也是为什么推荐主键要求自增。

总结

本为让你亲身作为一个MySQL架构师的身份，一步步带你了解MySQL中索引的数据结构，现在是不是了解的很透彻了，假如对你有协助的话，请留下一个赞吧。

本文正在参加「技能专题19期 漫谈数据库技能」活动