[大数据]MySQL 索引的原理

索引的原理

1、数据页

假设有一张数据库表：

对于 InnoDB 存储引擎来说，最小的存储单位就是：页。那么存放原始数据的页就称为数据页。

一个数据页默认的大小是：16KB。如果我们假设一条记录所占空间的字节数是 1KB，那么这个数据页大致能够存储 16 条记录。那么如果这个数据库表总共有 100 万条记录，那么肯定是需要很多数据页来存放这些数据。

2、数据页内部

①主键排序

数据页内部对主键进行了排序，所以当我们在一个数据页内部根据主键查找记录时，会根据二分法进行查找。找到主键就能够很快找到这条记录。

②数据页编号

为了在众多数据页中，定位每一个数据页，数据页需要有编号。

3、数据页如何便于查找

①排序

根据主键值对所有数据页进行排序。

②双向链表

把所有数据页组成环状双向链表。

好处是：假设搜索主键值大于 30 的记录，那么找到主键值为 30 的记录之后，后面所有的记录就都可以快速找到和返回了。

③扫描全表

就目前的数据存储方式来说，如果要找到某一个主键值所在的数据页，需要一页一页的查找，这无疑是非常缓慢的。所以肯定需要做进一步优化。

4、数据页设定目录

①第一层目录

[1]设置

• 选取每一个数据页中最小的主键值
• 最小主键值 + 当前数据页的页码 = 目录页中的一条记录
• 主键值 + 页码 组成的记录放在一起组成了目录页
• 不管是数据页还是目录页都是页，默认大小都是 16KB
• 估算目录页能够存储多少条记录？
  • 主键值占 8 字节
  • 页码占 8 字节
  • 16 KB / 16 B = 1024 条

[2]搜索

现在我们在 4 号目录页中有如下三个区间：

• 区间 1：[1,11)
• 区间 2：[11,21)
• 区间 3：[21, …)

情景一：搜索主键值为 11 的记录

select emp_id,emp_name,emp_age from t_emp where emp_id=11

• 11 落在了区间 2：[11,21)
• 根据目录页中的 11->2 这条记录，得知想要的数据在页码为 2 的数据页
• 进入页码为 2 的数据页
• 在数据页内部根据主键做二分法查找

情景二：搜索主键值为 15 的记录

select emp_id,emp_name,emp_age from t_emp where emp_id=15

• 15 落在了区间 2：[11,21)
• 根据目录页中的 11->2 这条记录，得知想要的数据在页码为 2 的数据页
• 进入页码为 2 的数据页
• 在数据页内部根据主键做二分法查找

②第二层目录

[1]设置

为了更进一步方便查找，命中我们要找的目录页，我们可以进一步给目录再设置目录。

[2]搜索

用户搜索的主键值是：60。现在 13 号目录页中包含的区间：

• [1,51)
• [51,150)
• [150,…)

所以 60 会落在 [51,150) 区间，所以继续查找页码为 8 的目录页：

• [51,81)
• [81,100)
• [100,…)

所以 60 会落在 [51,81) 区间，所以继续查找页码为 5 的数据页，根据主键执行二分法查找。

[3]扩展

如果有需要，就可以给目录的目录再设置目录……直到向上汇总到一个唯一的根节点。

③最终形成一个树形结构

[1]示意图

[2]对接概念

B+Tree：其实这就是 B+Tree。在我们这里例子中，数据的主键就是 B+Tree 里面的索引，页码值就是指向数据存储位置的指针。只不过指针有可能指向数据页，也有可能指向目录页。

B+Tree 节点：目录页或数据页都算是 B+Tree 中的节点。

• 页：是 InnoDB 存储引擎管理数据的最小单元。
• 节点：是从树形结构角度来说的。

聚簇索引：索引和原始数据存放在一起的存储形式。聚簇索引都是由主键作为索引值，所以一个表中只有一个聚簇索引。

这里我们可以说：主键索引其实就是聚簇索引，这两个名字是从不同的角度来说的。

——> 主键索引：是指这个索引是根据主键字段来创建的

——> 聚簇索引：是指这个索引的树形结构中是否同时包含了『原始数据』和『索引目录』

不仅『主键索引』和『聚簇索引』这个两个概念是等同的，而且它们其实也就是数据表本身。也就是说其实我们并没有在原始数据库表之外再另外创建索引表，而是应该说：数据库表本身就是按照 B+Tree 的结构组织起来的，底层就是这么存储的。

非聚簇索引：索引和原始数据没有存放在一起的存储形式。非聚簇索引都算由非主键字段创建的，所以可以有多个。

索引值：在当前例子中，我们是拿主键字段的值作为索引。

[3]估算 B+Tree 能够存储的记录数量

结论：根据下面的推算使用 B+Tree 的形式来组织数据库表中数据的存储方式，只需要 2~4 层就足够了。

• 一层：只有一个根节点
  • 这个根节点只能是数据页节点
  • 一个数据页默认大小是：16KB
  • 假设一条记录占空间：1K
  • 能够存储的是数据数量：16 条
• 两层：
  • 根节点：目录页
    • 主键：8 B
    • 页码：8 B
    • 目录页的每一条记录：16 B
    • 目录页能够存储的记录数量：16 KB / 16 B = 1024
    • 对目录页来说：内部存储了多少条记录，就会指向多少个子节点
  • 叶子节点：数据页
    • 能够存储的是数据数量：16 条
  • 总和：目录页容量 × 数据页容量 = 1024 × 16 = 16384 条记录
• 三层：
  • 根节点：1 个目录页
  • 第二层：1024 个目录页
  • 第三层：目录页的个数 × 目录页的容量 = 1024 × 1024 = 1048576 个数据页
  • 总和：数据页的个数 × 数据页的容量= 1048576 × 16 = 16,777,216 条记录
• 四层：
  • 根节点：1 个目录页
  • 第二层：1024 个目录页
  • 第三层：目录页的个数 × 目录页的容量 = 1024 × 1024 = 1048576 个目录页
  • 第四层：目录页的个数 × 目录页的容量 = 1048576 × 1024 = 1,073,741,824 个数据页
  • 总和：数据页的个数 × 数据页的容量= 1,073,741,824 × 16 = 17,179,869,184 条记录

[4]B+Tree 层次对性能的影响

• 根节点常驻内存。
• 访问下一层的节点会导致一次 I/O。
• 所以层数越少，I/O 的次数就越少，性能就越好。

[5]BTree 为什么高瘦？

• BTree 的体型：

  高瘦

  • BTree 每个节点都存原始数据。
  • 每个节点的默认大小 16 KB，存了数据，能够用来存『主键 + 页码』的空间就不够了
  • 每个节点容纳子节点的数量就很少，导致深度增加
  • 对于查询来说：深度增加 1 层，I/O 次数增加一次
  • 所以性能方面 BTree 不如 B+Tree

• B+Tree 的体现：扁平、矮胖

[6]BTree 为什么每个节点都存原始数据？

BTree 将所有主键排序，对于父节点来说：

• 节点内部：主键是排序的
• 左边子节点：存放比父节点中最小主键还要小的主键
• 右边子节点：存放比父节点中最大主键还要大的主键
• 中间子节点：存放在父节点中主键区间范围的主键

所以在 BTree 中，在父节点出现过的主键不会在子节点中出现。反过来说：每一个主键只在一个节点中出现。所以主键关联的数据只能在主键所在的节点中保存。

[7]BTree 和 B+Tree 的区别总结

• BTree 中的节点（页），没有目录页、数据页之分。
• BTree 的节点中既存储原始数据，又存储子节点的页码值。
• 在 BTree 中，每个主键值只能在一个节点中出现，所以每个节点都需要保存原始数据
• BTree 因为每个节点都保存原始数据，所以用来保存节点页码的空间变小
• BTree 每个节点能够容纳的子节点比 B+Tree 要少
• BTree 整体层数比 B+Tree 要多
• MySQL 每读取一层节点，就要做一次 I/O 操作
• I/O 操作越多，性能越差
• B+树中所有叶子节点都是通过指针连接在一起，而B树不是。所以B+树范围查询效率很高

BTree：高瘦
层数多 —> I/O 次数多 —> 性能低
[1]为什么层数多？
因为父节点中，能够容纳的子节点的指针少。
[2]为什么能够容纳的子节点的指针少？
数据页的存储空间是固定的，默认是 16KB。
在这个固定的空间内，要拿出一部分存储原始数据。
所以能够用来存储索引记录的空间就变少了。
所以能够存储的索引记录的数量就变少了。
索引记录=索引值+子节点指针
[3]BTree里为什么每个节点都存数据？
因为对BTree的父节点来说，内部的主键值也是经过排序的。
比父节点中最小的主键值还小的主键值存放在父节点左边的子节点中。
比父节点中最大的主键值还大的主键值存放在父节点右边的子节点中。
最终导致：每一个主键都只在一个节点中出现过一次，所以原始数据就必须和主键保存在同一个节点中。
B+Tree：矮胖
层数少 —> I/O 次数少 —> 性能高

[8]有数据表和索引表之分吗？

这要看索引表具体指的是哪种类型的索引。

• 聚簇索引：那就没有额外的数据表，数据本身就是按照 B+Tree 的形式组成了聚簇索引——以主键作为索引值。
• 非聚簇索引：非聚簇索引相对于聚簇索引来说可以称之为是另外一张表。

但其实我们应该更进一步，更精确的来说：数据库底层维护表中的数据其实并没有『表』这个概念，而全部都是以索引的形式保存的。所以说数据库底层存储数据并不是我们从逻辑上看到的『行』和『列』的形式，而是树形结构。

结论：

• 数据的逻辑结构：表、行、列
• 数据的物理结构：B+Tree

5、非主键字段创建索引

TIP

前面我们所论述的，都是从主键出发建立索引，方便 SQL 语句中根据主键查询数据。

而用户在 SQL 语句中很多时候不是根据主键查询的。所以非主键字段也应该在适合的情况下创建索引，提升查询效率。

①不同数据类型的搜索方式

• 数值类型：就拿这个数值字段本身作为索引值

select emp_id,emp_name,emp_age from t_emp where emp_age=20;

• 字符串类型：

  • 较短字符串：就拿这个字符串字段本身作为索引值

  select emp_id,emp_name,emp_age from t_emp where emp_name='tom';
  

  • 较长字符串：通常就拿这个字符串字段开头（最左边）的一部分本身作为索引值

  select emp_id,emp_name,emp_age from t_emp where emp_decs like "I come from UK%";
  

TIP

对于目录页来说，它的结构固定就是下图所示：

那么我们用什么值做索引呢？

• 聚簇索引：主键值作为索引值
• 非聚簇索引：主键之外其它形式数据作为索引值

②单列索引

[1]概念

假设还是使用前面的数据库表：

现在我们为 emp_age 字段建立索引。此时因为我们只用到了这一个字段，所以叫单列索引。

[2]存储结构

和前面聚簇索引对比，也就是数据页存储的结构不同：

下面咱们拿实际数据举个例子：

[3]字符串类型能排序吗？

B+Tree 要求作为索引值的数据必须经过排序，这样方便执行二分法查找。而字符串可以根据它底层的 Unicode 码进行排序。因为 Unicode 码是二进制数据，二进制数据（或十六进制数据）也是整数，所以当然可以比较大小，可以排序。

③多列索引

也叫：组合索引、联合索引。顾名思义，这种索引就是在数据页包含了多个字段的值。

④回表

我们根据这个以非聚簇索引的索引列大小排序的 B+ 树只能确定我们要查找记录的主键值，所以如果我们想根据非聚簇索引的索引列的值查找到完整的用户记录的话，仍然需要回到聚簇索引中再查一遍，这个过程称为回表。也就是根据非聚簇索引的索引列的值查询一条完整的用户记录需要使用到两棵B+树！

问题：为什么我们还需要一次回表操作呢？直接把完整的用户记录放到叶子节点不OK吗？

回答： 如果把完整的用户记录放到叶子节点是可以不用回表。但是太占地方了，相当于每建立一棵B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了。

因为这种按照非主键列建立的B+树需要一次回表操作才可以定位到完整的用户记录，所以这种B+树也被称为二级索引（英文名secondary index），或者辅助索引。如果我们使用的是 emp_age 列的大小作为 B+ 树的排序规则，那么我们也可以把这个B+树叫做：为 emp_age 列建立的索引。

非聚簇索引的存在不影响数据在聚簇索引中的组织，所以一张表可以有多个非聚簇索引。

⑤不回表的情况

如果最终需要使用的数据，在非聚簇索引中直接就能够拿到，那就不需要回表再查询聚簇索引。

create index idx_emp_name on t_emp(emp_name);

select emp_id,emp_name from t_emp where emp_name like 'tom%';

⑥小结

聚簇索引与非聚簇索引的原理不同，在使用上也有一些区别：

1. 聚簇索引的叶子节点存储的就是我们的数据记录，非聚簇索引的叶子节点存储的是数据位置——主键。非聚簇索引不会影响数据表的物理存储顺序。
2. 一个表只能有一个聚簇索引，因为原始数据只能有一种排序存储的方式，但可以有多个非聚簇索引，也就是多个索引目录提供数据检索。

6、索引的分类

MySQL的索引包括普通索引、唯一性索引、全文索引、单列索引、多列索引和空间索引等。

• 从功能逻辑上说，索引主要有 4 种，分别是普通索引、唯一索引、主键索引和全文索引。
• 按照物理实现方式，索引可以分为 2 种：聚簇索引和非聚簇索引。
• 按照字段个数进行划分，分成单列索引和联合索引。

①普通索引

在创建普通索引时，不附加任何限制条件，主要用于提高查询效率。这类索引可以创建在任何数据类型中，其值是否唯一和非空，要由字段本身的完整性约束条件决定。建立索引以后，可以通过索引进行查询。例如，在表t_student的字段stuid上建立一个普通索引，查询记录时就可以根据该索引进行查询。

②唯一性索引

使用UNIQUE参数可以设置索引为唯一性索引，在创建唯一性索引时，限制该索引的值必须是唯一的，但允许有空值。在一张数据表里可以有多个唯一索引。

例如，在表t_student的字段name中创建唯一性索引，那么字段name的值就必须是唯一的。通过唯一性索引，可以更快速地确定某条记录。

③主键索引

主键索引就是一种特殊的唯一性索引，在唯一索引的基础上增加了不为空的约束，也就是 NOT NULL+UNIQUE，一张表里最多只有一个主键索引。

Why？ 这是由主键索引的物理实现方式决定的，因为数据存储在文件中只能按照一种顺序进行存储。

④单列索引

在表中的单个字段上创建索引。单列索引只根据该字段进行索引。单列索引可以是普通索引，也可以是唯一性索引，还可以是全文索引。只要保证该索引只对应一个字段即可。一个表可以有多个单列索引。

⑤多列(组合、联合)索引

多列索引是在表的多个字段组合上创建一个索引。该索引指向创建时对应的多个字段，可以通过这几个字段进行查询，但是只有查询条件中使用了这些字段中的第一个字段时才会被使用。例如，在表中的字段id、name和gender上建立一个多列索引idx_id_name_gender，只有在查询条件中使用了字段id时该索引才会被使用。使用组合索引时遵循最左前缀集合。

⑥全文索引

全文索引（也称全文检索）是目前搜索引擎使用的一种关键技术。它能够利用【分词技术】等多种算法智能分析出文本文字中关键词的频率和重要性，然后按照一定的算法规则智能地筛选出我们想要的搜索结果。

使用参数FULLTEXT可以设置索引为全文索引。在定义索引的列上支持值的全文查找，允许在这些索引列中插入重复值和空值。全文索引只能创建在CHAR、VARCHAR或TEXT类型及其系列类型的字段上，**查询数据量较大的字符串类型的字段时，使用全文索引可以提高查询速度。**例如，表t_student的字段information是TEXT类型，该字段包含了很多文字信息。在字段information上建立全文索引后，可以提高查询字段information的速度。

[1]自然语言的全文索引

默认情况下，或者使用 in natural language mode 修饰符时，match() 函数对文本集合执行自然语言搜索。

自然语言搜索引擎将计算每一个文档对象和查询的相关度。这里，相关度是基于匹配的关键词的个数，以及关键词在文档中出现的次数。**在整个索引中出现次数越少的词语，匹配时的相关度就越高。**相反，非常常见的单词将不会被搜索，如果一个词语的在超过 50% 的记录中都出现了，那么自然语言的搜索将不会搜索这类词语。

这个机制也比较好理解，比如说，一个数据表存储的是一篇篇的文章，文章中的常见词、语气词等等，出现的肯定比较多，搜索这些词语就没什么意义了，需要搜索的是那些文章中有特殊意义的词，这样才能把文章区分开。

[2]布尔全文索引

在布尔搜索中，我们可以在查询中自定义某个被搜索的词语的相关性，当编写一个布尔搜索查询时，可以通过一些前缀修饰符来定制搜索。

MySQL 内置的修饰符，上面查询最小搜索长度时，搜索结果 ft_boolean_syntax 变量的值就是内置的修饰符，下面简单解释几个，更多修饰符的作用可以查手册。

限制： MySQL数据库从3.23.23版开始支持全文索引，但MySQL5.6.4以前只有Myisam支持，5.6.4版本以后innodb才支持，但是官方版本不支持中文分词，需要第三方分词插件。在5.7.6版本，MySQL内置了ngram全文解析器，用来支持亚洲语种的分词。测试或使用全文索引时，要先看一下自己的 MySQL 版本、存储引擎和数据类型是否支持全文索引。

随着大数据时代的到来，关系型数据库应对全文索引的需求已力不从心，逐渐被 solr、elasticSearch等专门的搜索引擎所替代。

⑦补充：空间索引

使用参数SPATIAL可以设置索引为空间索引。空间索引只能建立在空间数据类型上，这样可以提高系统获取空间数据的效率。MySQL中的空间数据类型包括GEOMETRY、POINT、LINESTRING和POLYGON等。目前只有MyISAM存储引擎支持空间检索，而且索引的字段不能为空值。对于初学者来说，这类索引很少会用到。

**小结：不同的存储引擎支持的索引类型也不一样 **

• InnoDB ：支持 B-tree、Full-text 等索引，不支持 Hash 索引；
• MyISAM ： 支持 B-tree、Full-text 等索引，不支持 Hash 索引；
• **Memory ：**支持 B-tree、Hash 等索引，不支持 Full-text 索引；
• **NDB ：**支持 Hash 索引，不支持 B-tree、Full-text 等索引；
• **Archive ：**不支持 B-tree、Hash、Full-text 等索引；