MySQL索引

索引基础回顾

索引是什么

• MYSQL 官方对索引的定义为：索引（Index）是帮助 MySQL 高效获取数据的数据结构，所以说索引的本质是：数据结构
• 索引的目的在于提高查询效率，可以类比字典、 火车站的车次表、图书的目录等 。
• 可以简单的理解为“排好序的快速查找数据结构”，数据本身之外，数据库还维护着一个满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
• 索引本身也很大，不可能全部存储在内存中，一般以索引文件的形式存储在磁盘上

索引的优势

• 索引大大减少了服务器需要扫描的数据量（提高数据检索效率）
• 索引可以帮助服务器避免排序和临时表（降低数据排序的成本，降低 CPU 的消耗）
• 索引可以将随机 I/O 变为顺序 I/O（降低数据库 IO 成本）

索引的劣势

• 索引也是一张表，保存了主键和索引字段，并指向实体表的记录，所以也需要占用内存
• 虽然索引大大提高了查询速度，同时却会降低更新表的速度，如对表进行 INSERT、UPDATE 和 DELETE。 因为更新表时，MySQL 不仅要保存数据，还要保存一下索引文件每次更新添加了索引列的字段，都会调整因为更新所带来的键值变化后的索引信息

索引分类

逻辑角度

• 主键索引：主键索引是一种特殊的唯一索引，不允许有空值
• 普通索引或者单列索引：每个索引只包含单个列，一个表可以有多个单列索引
• 多列索引（复合索引、联合索引）：复合索引指多个字段上创建的索引，只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。
• 唯一索引或者非唯一索引
• Full-Text 全文索引：它查找的是文本中的关键词，而不是直接比较索引中的值
• 空间索引：空间索引是对空间数据类型的字段建立的索引

数据结构角度

• Hash 索引：主要就是通过 Hash 算法，将数据库字段数据转换成定长的 Hash 值，与这条数据的行指针一并存入 Hash 表的对应位置；如果发生 Hash 碰撞，则在对应 Hash 键下以链表形式存储。查询时，就再次对待查关键字再次执行相同的 Hash 算法，得到 Hash 值，到对应 Hash 表对应位置取出数据即可，Memory 引擎是支持非唯一哈希索引的，如果发生 Hash 碰撞，会以链表的方式存放多个记录在同一哈希条目中。使用 Hash 索引的数据库并不多， 目前有 Memory 引擎和 NDB 引擎支持 Hash 索引。
• 缺点是，只支持等值比较查询，像 = 、 in() 这种，不支持范围查找，比如 where id > 10 这种，也不能排序。
• B+ 树索引

物理存储角度

• 聚集索引（clustered index）
• 非聚集索引（non-clustered index），也叫辅助索引（secondary index）
  聚集索引和非聚集索引都是 B+ 树结构

MySQL 索引结构

索引可以有很多种结构类型，这样可以为不同的场景提供更好的性能。

首先要明白索引（index）是在存储引擎（storage engine）层面实现的，而不是 server 层面。不是所有的存储引擎都支持所有的索引类型。即使多个存储引擎支持某一索引类型，它们的实现和行为也可能有所差别。
MySQL 为什么不用 Hash 结构做索引?
我会直接来一句，不好意思，MySQL 也会用 Hash 做索引，Memory 存储引擎就支持 Hash 索引。只是场景用的少，Hash 结构更适用于只有等值查询的场景
为什么不用二叉搜索树呢？ 这就很简单了，二叉树的叉叉上只有两个数，数据量太多的话，那得多少层呀。

B树和B+树

介绍
在 B 树中，内部（非叶子）节点可以拥有可变数量的子节点（数量范围预先定义好）。当数据被插入或从一个节点中移除，它的子节点数量发生变化。为了维持在预先设定的数量范围内，内部节点可能会被合并或者分离。因为子节点数量有一定的允许范围，所以B 树不需要像其他自平衡查找树那样频繁地重新保持平衡，但是由于节点没有被完全填充，可能浪费了一些空间。子节点数量的上界和下界依特定的实现而设置。例如，在一个 2-3 B树（通常简称2-3树 (opens new window)），每一个内部节点只能有 2 或 3 个子节点。
**B 树中每一个内部节点会包含一定数量的键，键将节点的子树分开。**例如，如果一个内部节点有 3 个子节点（子树），那么它就必须有两个键： a1 和 a2 。左边子树的所有值都必须小于 a1 ，中间子树的所有值都必须在 a1 和 a2 之间，右边子树的所有值都必须大于 a2 。
在存取节点数据所耗时间远超过处理节点数据所耗时间的情况下，Ｂ树在可选的实现中拥有很多优势，因为存取节点的开销被分摊到里层节点的多次操作上。这通常出现在当节点存储在二级存储器如硬盘存储器上。通过最大化内部里层节点的子节点的数量，树的高度减小，存取节点的开销被缩减。另外，重新平衡树的动作也更少出现。子节点的最大数量取决于，每个子节点必需存储的信息量，和完整磁盘块的大小或者二次存储器中类似的容量。虽然 2-3 树更易于解释，实际运用中，Ｂ树使用二级存储器 (opens new window)，需要大量数目的子节点来提升效率。
而 B+ 树 又是 B 树的变种，B+ 树结构，所有的数据都存放在叶子节点上，且把叶子节点通过指针连接到一起，形成了一条数据链表，以加快相邻数据的检索效率。
数据结构可视化网站

区别

为什么要用 B+ 树

B+Tree 是在 B-Tree 基础上的一种优化，使其更适合实现外存储索引结构。

用 B+ 树不用 B 树考虑的是 IO 对性能的影响，B 树的每个节点都存储数据，而 B+ 树只有叶子节点才存储数据，所以查找相同数据量的情况下，B 树的高度更高，IO 更频繁。数据库索引是存储在磁盘上的，当数据量大时，就不能把整个索引全部加载到内存了，只能逐一加载每一个磁盘页（对应索引树的节点）。其中在 MySQL 底层对 B+ 树进行进一步优化：在叶子节点中是双向链表，且在链表的头结点和尾节点也是循环指向的。

B-Tree 结构图每个节点中不仅要包含数据的 key 值，还有 data 值。而每一个页的存储空间是有限的，如果 data 数据较大时将会导致每个节点（即一个页）能存储的 key 的数量很小，当存储的数据量很大时同样会导致 B-Tree 的深度较大，增大查询时的磁盘 I/O 次数，进而影响查询效率。在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。

IO 次数取决于 B+ 数的高度 h，假设当前数据表的数据为 N，每个磁盘块的数据项的数量是 m，则有 h=㏒(m+1)N，当数据量 N 一定的情况下，m 越大，h 越小；而 m = 磁盘块的大小 / 数据项的大小，磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小，比如 int 占 4 字节，要比 bigint 8 字节少一半。这也是为什么 B+ 树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于 1 时将会退化成线性表。

MyISAM 和 InnoDB 索引原理

MyISAM 主键索引与辅助索引的结构

MyISAM 引擎的索引文件和数据文件是分离的。MyISAM 引擎索引结构的叶子节点的数据域，存放的并不是实际的数据记录，而是数据记录的地址。****索引文件与数据文件分离，这样的索引称为"非聚簇索引"。MyISAM 的主索引与辅助索引区别并不大，主键索引就是一个名为 PRIMARY 的唯一非空索引。

在 MyISAM 中，索引（含叶子节点）存放在单独的 .myi 文件中，叶子节点存放的是数据的物理地址偏移量（通过偏移量访问就是随机访问，速度很快）。

主索引是指主键索引，键值不可能重复；辅助索引则是普通索引，键值可能重复。

通过索引查找数据的流程：先从索引文件中查找到索引节点，从中拿到数据的文件指针，再到数据文件中通过文件指针定位了具体的数据。

辅助索引类似。

InnoDB 主键索引与辅助索引的结构

InnoDB 引擎索引结构的叶子节点的数据域，存放的就是实际的数据记录（对于主索引，此处会存放表中所有的数据记录；对于辅助索引此处会引用主键，检索的时候通过主键到主键索引中找到对应数据行），或者说，InnoDB 的数据文件本身就是主键索引文件，这样的索引被称为**"“聚簇索引”**，一个表只能有一个聚簇索引。
主键索引
我们知道 InnoDB 索引是聚集索引，它的索引和数据是存入同一个 .idb 文件中的，因此它的索引结构是在同一个树节点中同时存放索引和数据，如下图中最底层的叶子节点有三行数据，对应于数据表中的 id、name、score 数据项。

辅助（非主键）索引：
这次我们以示例中学生表中的 name 列建立辅助索引，它的索引结构跟主键索引的结构有很大差别，在最底层的叶子结点有两行数据，第一行的字符串是辅助索引，按照 ASCII 码进行排序，第二行的整数是主键的值。

这就意味着，对 name 列进行条件搜索，需要两个步骤：

在辅助索引上检索 name，到达其叶子节点获取对应的主键；
使用主键在主索引上再进行对应的检索操作
这也就是所谓的**“回表查询”**

InnoDB 索引结构需要注意的点

• 数据文件本身就是索引文件
• 表数据文件本身就是按 B+Tree 组织的一个索引结构文件
• 聚集索引中叶节点包含了完整的数据记录
• InnoDB 表必须要有主键，并且推荐使用整型自增主键
  正如我们上面介绍 InnoDB 存储结构，索引与数据是共同存储的，不管是主键索引还是辅助索引，在查找时都是通过先查找到索引节点才能拿到相对应的数据，如果我们在设计表结构时没有显式指定索引列的话，MySQL 会从表中选择数据不重复的列建立索引，如果没有符合的列，则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键，并且这个字段长度为 6 个字节，类型为整型。

索引策略

哪些情况需要创建索引

• 主键自动建立唯一索引
• 频繁作为查询条件的字段
• 查询中与其他表关联的字段，外键关系建立索引
• 单键/组合索引的选择问题，who? 高并发下倾向创建组合索引
• 查询中排序的字段，排序字段通过索引访问大幅提高排序速度
• 查询中统计或分组字段
  哪些情况不要创建索引
• 表记录太少
• 经常增删改的表
• 数据重复且分布均匀的表字段，只应该为最经常查询和最经常排序的数据列建立索引（如果某个数据类包含太多的重复数据，建立索引没有太大意义）
• 频繁更新的字段不适合创建索引（会加重IO负担）
• where 条件里用不到的字段不创建索引

高效索引

独立的列
如果查询中的列不是独立的，MySQL 就不会使用索引。“独立的列”是指索引不能是表达式的一部分，也不能是函数的参数。

EXPLAIN SELECT * FROM mydb.sys_user where user_id = 2;

EXPLAIN SELECT * FROM mydb.sys_user where user_id + 1 = 2;

前缀索引
前缀索引其实就是对文本的前几个字符（具体是几个字符在建立索引时指定）建立索引，这样建立起来的索引占用空间更小，所以查询更快。
对于内容很长的列，比如 blob, text 或者很长的 varchar 列，必须使用前缀索引，MySQL 不允许索引这些列的完整长度。
所以问题就在于要选择合适长度的前缀，即 prefix_length。前缀太短，选择性太低，前缀太长，索引占用空间太大。

select id,name,email from user where emai='zhangsan@qq.com' 

执行效果会有很大的差别，普通索引 idx_email 找到满足条件的记录后，再返回主键索引取出数据即可，而前缀索引会多次查到 zhangs，然后返回主键索引取出数据进行对比，会扫描多次数据行。

如果前缀索引取前 7 个字节构建的话 idx_pre_email(7)，就只需要扫描一行。

所以使用前缀索引，定义好长度，就可以做到既节省空间，又不用额外增加太多的查询成本。

为了决定前缀的合适长度，需要找到最常见的值的列表，然后和最常见的前缀列进行比较。
前缀索引是一种能使索引更小、更快的有效办法，但另一方面也有缺点：MySQL 无法使用前缀索引做 ORDER BY 和 GROUP BY，也无法使用前缀索引做『覆盖索引』。
覆盖索引
覆盖索引（Covering Index），或者叫索引覆盖， 也就是平时所说的不需要回表操作

• 就是 select 的数据列只用从索引中就能够取得，不必读取数据行，MySQL 可以利用索引返回 select 列表中的字段，而不必根据索引再次读取数据文件，换句话说查询列要被所建的索引覆盖。
• 索引是高效找到行的一个方法，但是一般数据库也能使用索引找到一个列的数据，因此它不必读取整个行。毕竟索引叶子节点存储了它们索引的数据，当能通过读取索引就可以得到想要的数据，那就不需要读取行了。一个索引包含（覆盖）满足查询结果的数据就叫做覆盖索引。
• 判断标准 使用 explain，可以通过输出的 extra 列来判断，对于一个索引覆盖查询，显示为 using index，MySQL 查询优化器在执行查询前会决定是否有索引覆盖查询
  多列索引（复合索引、联合索引）
  组合索引(concatenated index)：由多个列构成的索引，如 create index idx_emp on emp(col1, col2, col3, ……)，则我们称 idx_emp 索引为组合索引。在多个列上建立独立的单列索引大部分情况下并不能提高 MySQL 的查询性能。
  MySQL 5.0 和后续版本引入了一种叫做“索引合并”的策略，查询能够同时使用这两个单列索引进行扫描，并将结果合并。这种算法有三个变种：OR 条件的联合（union），AND 条件的相交（intersection），组合前两种情况的联合及相交。索引合并策略有时候是一种优化的结果，但实际上更多时候说明了表上的索引建得很糟糕
• 当出现服务器对多个索引做相交操作时（多个AND条件），通常意味着需要一个包含所有相关列的多列索引，而不是多个独立的单列索引。
• 当出现服务器对多个索引做联合操作时（多个OR条件），通常需要耗费大量的 CPU 和内存资源在算法的缓存、排序和合并操作上。特别是当其中有些索引的选择性不高，需要合并扫描返回的大量数据的时候。
• 如果在 explain 中看到有索引合并，应该好好检查一下查询和表的结构，看是不是已经是最优的。