本篇文章还有几部分没有写

  1. 全文索引的原理
  2. 索引的相关问题
  3. 隐式类型转换，可能导致索引失效
  4. 索引优化
  5. 分布式索引

介绍索引

技术是为了解决问题而生的，通过索引我们可以解决全表扫描查询慢的问题。
索引是什么：索引是帮助数据库管理系统高效获取数据 / 快速定位的数据结构。
索引的目标：用一种数据结构来提高查询效率。

索引的优劣局限

InnoDB 存储引擎的索引方案使用 B+树。
InnoDB 存储引擎的索引方案的优点（作用、目标）是：

  • 提高查询效率：使用 B+树来存储数据，减少查询所需要的磁盘 I/O 次数，从而提高查询效率（影响增删改效率）
  • 唯一性约束：使用唯一索引，可以保证行记录的唯一性
  • 用全文索引可以实现查询文本中出现的关键字

InnoDB 存储引擎的索引方案的缺点是：（维护索引所需的代价）

  • 维护索引消耗空间：每个索引对应一个文件，如果索引数量过多，将会占用过多空间。
  • 维护索引消耗时间：当进行增删改操作时，索引文件也要更新，如果索引数量过多，将会影响增删改的性能。
  • 查询优化器选择索引消耗时间：如果索引数量过多，还会增加索引选择的时间。

    MySQL 中创建和删除索引

    创建表的时候，同时创建主键索引：
    1. create table `table_name` (
    2. 各种列的信息 ··· ,
    3. primary key(`column1`, `column2`, ...)
    4. )

添加索引

  1. # 添加普通索引 (key 和 index 是同义词，任选其一)
  2. alter table `table_name` add [key | index] index_name(`column`);
  4. # 添加唯一索引
  5. alter table `table_name` add unique(`column`);
  7. # 添加主键索引
  8. alter table `table_name` add primary key(`column`);
  10. # 添加全文索引
  11. alter table `table_name` add fulltext(`column`);

删除索引

  1. # 既可以普通索引，也可以删除唯一索引、全文索引
  2. alter table `table_name` drop [key | index] index_name;

索引的分类

按照功能逻辑分类

按照功能逻辑，索引可分为：普通索引、唯一索引、主键索引、全文索引

  • 普通索引是基础的索引，没有任何约束，用以提高查询效率。
  • 唯一索引在普通索引的基础上，增加了数据唯一性的约束，也就是 unique。
  • 主键索引在唯一索引的基础上，增加了不为空的约束，也就是 not null + unique，并且索引的列为主键。
  • 全文索引用来查询文本中出现的关键字。

    一张表里，可以有多个普通索引，多个唯一索引，只能有一个主键索引。

按照字段个数分类

按照字段个数，索引可分为：单一索引、联合索引

  • 单一索引：索引列为一列

  • 联合索引：索引列为多个列

    按照物理实现方式分类

    按照物理实现方式，索引可分为：聚簇索引、非聚簇索引

  • 聚簇索引的叶子节点存储的就是数据记录（也就是所谓的索引即数据，数据即索引）

  • 非聚簇索引的叶子节点存储的是数据位置（索引和数据分开存储）

    非聚集索引也被称为二级索引、辅助索引。 一张表里，只能有一个聚簇索引。

索引的常见模型

24丨索引的原理：我们为什么用B+树来做索引？
04 | 深入浅出索引（上）
实现索引的方式有很多种，所以就引入了索引模型的概念。
不同存储引擎的索引使用的数据结构不同。
并且不同存储引擎的索引使用的数据结构相同，但具体实现原理也可能不同。

比如：InnoDB 和 MyISAM 存储引擎，他俩都是使用 B+树，但是 B+树的叶子节点存储的内容却不同。

B+树

B 树的英文是 Balance Tree，也就是平衡的多路搜索树。
B+ 树基于 B 树做出了改进，B+ 树和 B 树的差异在于以下几点

  1. B+ 树中，有 k 个子节点的节点就有 k 个关键字；而 B 树中，子节点数量 = 关键字数 + 1。
  2. B+ 树中，非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中；而 B 树中，非叶子节点既保存索引，也保存数据记录。
  3. B+ 树中，非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）；而 B 树中，非叶子节点的关键字可能不存在子节点中。
  4. B+ 树中，所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。

B 树
B+ 树

哈希表

哈希表是键值对的集合，通过键（key）即可快速取出对应的值（value），可以用来提高等值查询的效率。
一个哈希表，其实就是一个数组，数组的每个元素被称为一个哈希桶，每个哈希桶中保存了键值对数据。
键 key 通过 Hash 函数映射到哈希桶。那么无法避免的会产生 Hash 冲突，也就是说多个不同的 key 映射到相同的哈希桶。常用的解决 Hash 冲突的办法是：链地址法。链地址法的核心思想是：如果出现了 Hash 冲突，产生 Hash 冲突的键值对，形成一个链表。
索引 - 图3

对于等值查询来说，通常 Hash 索引的效率很高，不过也存在一种情况，就是索引列的重复值如果很多，效率就会降低。这是因为遇到 Hash 冲突时，需要遍历桶中的行指针来进行比较，找到查询的关键字，非常耗时。所以，Hash 索引通常不会用到重复值多的列上，比如列为性别、年龄的情况等。
MySQL 的 Memory 存储引擎支持 Hash 存储。
MySQL 的 InnoDB 存储引擎有一个“自适应 Hash 索引”的功能，就是当某个索引值使用非常频繁的时候，它会在 B+ 树索引的基础上再创建一个 Hash 索引，这样让 B+ 树也具备了 Hash 索引的优点。

Hash 索引与 B+ 树索引的区别

25丨Hash索引的底层原理是什么？
Hash 索引结构和 B+ 树索引结构不同，因此在使用上也会有差别。

  1. Hash 索引不能进行范围查询，而 B+ 树可以。这是因为 Hash 索引指向的数据是无序的，而 B+ 树的叶子节点是个有序的链表。
  2. Hash 索引不支持联合索引的最左侧原则（即联合索引的部分索引无法使用），而 B+ 树可以。对于联合索引来说，Hash 索引在计算 Hash 值的时候是将索引键合并后再一起计算 Hash 值，所以不会针对每个索引单独计算 Hash 值。因此如果用到联合索引的一个或者几个索引时，联合索引无法被利用。
  3. Hash 索引不支持 ORDER BY 排序。因为 Hash 索引指向的数据是无序的，因此无法起到排序优化的作用，而 B+ 树索引数据是有序的，可以起到对该字段 ORDER BY 排序优化的作用。
  4. 同理，Hash 索引无法进行模糊查询。而 B+ 树使用 LIKE 进行模糊查询的时候，LIKE 后面前模糊查询（比如 % 开头）的话就可以起到优化作用。

总结一下，Hash 索引与 B+ 树索引的本质区别就是：Hash 索引指向的数据是无序的，B+ 树的叶子节点是一个有序的链表。
Hash 索引适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。

有序数组

有序数组就是，里面的元素按照一定的顺序排序。
如果你要查某个元素，用二分法就可以快速得到，这个时间复杂度是 O(log(N))。
有序数组在等值查询和范围查询场景中的性能就都非常优秀。
索引 - 图4

如果仅仅看查询效率的话，有序数组就是最好的数据结构了。但是，在需要更新数据的时候比较麻烦，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。
所以，有序数组索引只适用于静态存储引擎，比如你要保存的是 2017 年某个城市的所有人口信息，这类不会再修改的数据。

InnoDB 和 MyISAM 的索引方案

B+ 树索引
InnDB 和 MyISAM 存储引擎使用的索引结构都为 B+树。一个索引对应一棵 B+ 树。
但是两者的具体实现原理不同。
使用 InnDB 存储引擎的表：

  • 聚簇索引的叶子节点存储的是完整的用户记录。所谓完整的用户记录是指：这个记录中存储了所有列的值，包括隐藏列（行 id(row_id)、事务 id(transaction_id)、回滚指针(roll_pointer)、自定义的列）
  • 非聚簇索引的叶子节点存储的并不是完整的用户记录，只是索引列 + 主键列的值，不包括隐藏列。如果索引上的信息不满足查询请求，需要回到主键索引上根据主键值取数据，再返回

    在没有自定义主键以及 Unique 键的情况下才会添加行 id（row_id）隐藏列。 回滚指针(roll_pointer) 用于记录形成版本链，和事务回滚以及 MVCC 相关。

MyISAM 的索引方案虽然也使用 B+树，但是它却将索引和数据分开存储。
将表中的记录按照记录的插入顺序单独存储在一个 .myd 文件中，称为数据文件。这个数据文件可以通过行号快速访问到一条记录。
使用 MyISAM 的表会把索引信息单独存储在一个 .myi 文件中，称为索引文件。
MyISAM 会单独为表的主键创建一个索引，索引的叶子节点中存储的不是完整的用户记录，而是主键值 + 行号的组合。也就是先通过索引找到对应的行号，再通过行号去找对应的记录。
如果有需要的话，也可以对其它的列建立索引，索引的叶子节点中存储的是相应的列 + 行号，
MyISAM 存储引擎的索引都是非聚簇索引（二级索引、辅助索引）。

索引 - 图5

全文索引的原理

索引的相关概念

05 | 深入浅出索引（下）

索引的最左前缀原则

最左前缀原则的意思是：索引项是按照索引定义里面出现的字段顺序依次排序的。我们按照什么顺序创建索引，就只能按照这个顺序使用索引中的字段，从索引的最左前列开始并且不跳过索引中的列，不只是索引的全部索引项，只要满足最左前缀，就可以利用索引来提高查询效率。

这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

比如，我们创建联合索引（a, b, c），那么，
where 等值查询，可以用上该联合索引的情况如下：

  • where 等值查询 a
  • where 等值查询 a b
  • where 等值查询 a b c

where 等值查询，不能用上该联合索引的情况如下：

  • where 等值查询 b
  • where 等值查询 c
  • where 等值查询 a c

    覆盖索引

    覆盖索引是指：非聚簇索引上的信息足够满足查询请求，不需要再回到聚簇索引上去取数据。
    对于直接使用聚簇索引的查询，也属于覆盖索引。
    在执行计划 Explain 中，如果在 Extra 字段里面显示 Using index，表示这个语句将会使用覆盖索引。

我们以 person(id, name, age, gender) 表为例。
我们在 name，age 列上建立联合索引 index1。
如果我们只需要查询 age = 18 的 name，也就是 select name from person where age = 18; 由于联合索引 index1 中的数据包含 name、age、主键 id，那么此时只需要访问一次该联合索引，不需要再根据主键值去主键索引上查找数据，避免了回表操作。

索引条件下推

索引条件下推是 MySQL 5.6 版本引入的一项索引优化功能。
技术是为了解决问题而生的，索引条件下推要解决的问题是：不是覆盖索引的查询需要回表，影响查询效率。
索引条件下推的目标是：减少回表次数，进一步提高查询效率。
在从非聚簇索引中查出数据后，先对索引中包含的字段判断是否满足 where 查询条件，过滤掉不符合 where 查询条件的记录，再回表根据主键值取数据，再判断其他条件。

我们以 person(id, name, age, gender) 表为例。
我们在 name，age 列上建立联合索引 index1。
如果我们要查询 name = “xm” 并且 age > 18 的列，也就是 select * from person where name = “xm” and age > 18;这条 SQL 语句首先会从联合索引 index1 中查出 name = “xm” 的记录，如果有多条 name = “xm” 的记录的话，这时会先判断这些记录的 age 是否大于 18，只根据那些 age > 18 的记录的主键值回表查询其他列数据。

前缀索引

11 | 怎么给字符串字段加索引？
前缀索引的意思是，对某个字段的前 N 个字符建立索引，而不是整个字段。
如果你创建索引的语句不指定前缀长度，那么索引就会包含真个字段。
技术是为了解决问题而生的，前缀索引要解决的问题是：如果某索引列的值后半部分是相同的，那么存储相同的部分将毫无意义，并且占用空间。
前缀索引的目标：减少占用的空间（节省空间）。

前缀索引的优劣局限

前缀索引节省了空间，这同时也带来了损失：可能会增加额外的记录扫描、回表次数，增加查询成本。
因此前缀索引用不上覆盖索引，因为仅凭字符串前缀，无法判断字符串是否完全相等。

我们以 person(id, name, age, gender) 表为例。
我们对 name 列的前 3 个字符建立单值索引 index1，SQL 语句如下：

  1. alter table `person` add index index_name(name(3))

这样，这个索引对应的 B+树的 name 字段就只取前 3 个字符，所以占用的空间会更小，这就是使用前缀索引的优势。

下面我们说一下上面提到的带来的损失：可能会增加额外的记录扫描、回表次数，增加查询成本。
如果表中有 name 列为 abc、abcd、abce、abcf、abcg ……，那么我们执行下面的 SQL：

  1. select * from `person` where name = 'abc';

此时，单值索引 index1 中有多个前 3 个字符为 abc 的记录，那么会回表多次，去判断 name 是否等于 abc
如果我们是对 name 列的全部字符建立索引，那么只会查找到 1 条记录字符为 abc 的记录，只需要回表 1 次。

如何选择多长的前缀

使用前缀索引，定义好长度，就可以做到既节省空间，又不用额外增加太多的查询成本。
那么当要给字段创建前缀索引时，有什么方法能够确定我应该使用多长的前缀呢？
实际上，我们在建立索引时关注的是区分度，区分度越高越好。因为区分度越高，意味着重复的键值越少。
因此，我们可以通过统计索引上有多少个不同的值来判断要使用多长的前缀。

首先，你可以使用下面这个语句，算出这个列上有多少个不同的值：

  1. select count(distinct `name`) as L from person;

然后，依次选取不同长度的前缀来看这个值，比如我们要看一下 4~7 个字节的前缀索引，可以用这个语句：

  1. select 
  2.   count(distinct left(`name`,4)) as L4,
  3.   count(distinct left(`name`,5)) as L5,
  4.   count(distinct left(`name`,6)) as L6,
  5.   count(distinct left(`name`,7)) as L7
  6. from person;

使用前缀索引很可能会损失区分度，所以你需要预先设定一个可以接受的损失比例，比如 5%。
然后，在返回的 L4~L7 中，找出不小于 L * 95% 的值，假设这里 L6、L7 都满足，你就可以选择前缀长度为 6。

索引的使用原则

26丨索引的使用原则：如何通过索引让SQL查询效率最大化？

创建索引的规律

  1. 如果字段的数值有唯一性的限制，比如用户名，可以使用唯一索引进行唯一性约束
  2. 频繁作为 where 查询（包括删改）条件的字段，要考虑在该字段上创建索引
  3. 需要经常 group by 和 order by 的字段，要考虑在该字段上创建索引

  4. 需要经常 distinct 的字段，要考虑在该字段上创建索引

    什么时候不需要创建索引

  5. 表中的数据行数比较少的情况下，不需要创建索引。当表中的数据行数变多，查询性能不满足要求时，考虑用索引优化

  6. 当该字段的数据重复度大（区分度小）时，不需要对这个字段创建索引（需要根据实际情况来做判断）
  7. where 条件（包括 group by、order by）里用不到的字段不需要创建索引
  8. 频繁更新的字段不一定要创建索引

索引的价值是帮我们从海量数据中快速查找，如果数据量少，那么是否使用索引对结果的影响并不大。因此，在表中的数据行数比较少的情况下，是不需要创建索引的。
当表中的数据行数达到什么数据级时，就需要创建索引了呢，这个要根据 SQL 语句的查询时间来定。

假设团队要求 SQL 语句的查询时间不能超过 0.5 s，那么当 SQL 语句的查询时间超过 0.5 s 时，就要考虑用索引来优化查询时间。

当该字段的数据重复度大（区分度小）时，不需要对这个字段创建索引。
我们不仅要看字段中的数值个数，还要根据数值的分布情况来考虑是否需要创建索引。
比如性别，但是如果表中的数据男性 10 人，女性 10 万人，如果要查出所有男性的数据行的话，还是使用索引比较快。

频繁更新的字段不一定要创建索引。
因为更新数据的时候，也需要更新索引，如果索引太多，在更新索引的时候也会造成负担，从而影响效率。

索引失效的情况

  1. 如果 where 查询条件的索引列进行了表达式计算，那么索引会失效
  2. 如果 where 查询条件的索引列使用了函数，那么索引会失效
  3. 在 where 子句中，如果在 or 前的条件列进行了索引，而在 or 后的条件列没有进行索引，那么索引会失效
  4. 索引列与 NULL 或者 NOT NULL 进行判断的时候，索引会失效
  5. 隐式类型转换，可能导致索引失效

1、2：使用函数的情况和进行表达式计算的情况类似，这是因为我们需要把索引字段的取值都取出来，然后依次进行表达式的计算 / 函数的计算来进行条件判断，因此采用的就是全表扫描的方式。
4：索引列与 NULL 或者 NOT NULL 进行判断的时候，索引会失效。这是因为索引并不存储空值，所以最好在设计数据表的时候就将字段设置为 NOT NULL 约束。比如你可以将 INT 类型的字段，默认值设置为 0，将字符类型的默认值设置为空字符串 (‘ ‘)。

索引的相关问题

为什么索引的结构选择 B+ 树，而不是 B 树、红黑树、跳表呢？

24丨索引的原理：我们为什么用B+树来做索引？
B 树、B+树、红黑树、跳表都是支持快速查找的动态数据结构，为什么 MySQL 采用了 B+树呢？

B 树 和 B+树
B+ 树和 B 树的查询过程差不多，但是 B+ 树和 B 树的差异之一在于，B+ 树的非叶子节点并不直接存储数据。这样的好处都有什么呢？

  • 首先，B+ 树查询效率更稳定。因为 B+ 树每次只有访问到叶子节点才能找到对应的数据，而在 B 树中，非叶子节点也会存储数据，这样就会造成查询效率不稳定的情况，有时候访问到了非叶子节点就可以找到关键字，而有时需要访问到叶子节点才能找到关键字。
  • 其次，B+ 树的查询效率更高，这是因为 B树的非叶子节点既保存索引，也保存数据记录，同样的磁盘页大小，B+ 树可以存储更多的节点关键字，因此在同等数据量的情况下，B+ 树比 B 树更矮胖（阶数更大，深度更低），查询所需要的磁盘 I/O 也会更少。
  • 再次，B+ 树的范围查询效率更高。因为在 B+ 树中，所有关键字都出现在叶子节点中，并且所有叶子节点形成双向链表，范围查询时只需要找到起始节点，然后基于双向链表结构往下去读取并判断是否满足 范围查询条件；而在 B 树中则需要通过树的遍历才能完成范围查询。

红黑树 和 B+树

跳表 和 B+树

为什么不用 MySQL 的全文索引，而是用全文搜索引擎

为什么不使用 MySQL 的全文索引，而是选择使用专门的全文搜索引擎，比如 ElasticSearch、Solr。

索引优化

分布式索引

参考资料

04 | 深入浅出索引（上）
05 | 深入浅出索引（下）
11 | 怎么给字符串字段加索引？
24丨索引的原理：我们为什么用B+树来做索引？
25丨Hash索引的底层原理是什么？
26丨索引的使用原则：如何通过索引让SQL查询效率最大化？
B+ 树索引

以下的文章也是和索引相关的文章，但是上面的文章内容未参考这部分。

23丨索引的概览：用还是不用索引，这是一个问题
27丨从数据页的角度理解B+树查询
29丨为什么没有理想的索引？
34丨答疑篇：关于索引以及缓冲池的一些解惑
B+ 树索引的使用
讲 B+ 树：MySQL 数据库索引是如何实现的
09 | 普通索引和唯一索引，应该怎么选择？
10 | MySQL为什么有时候会选错索引？