索引03之索引原理

解密索引原理

一：MySQL索引为何使用B+树结构

核心回答思路

1：一条普通SQL的全表扫描

假设有一张用户(user)表，存在如下的信息

假设表中不存在任何索引，此时来执行下述这条SQL

select * from user where name = '钱七'

因为表中不具备索引，所以这里会走全表扫描的形式检索数据，但不管是走全表亦或索引

本质上由于数据都存储在磁盘中，因此首先都会触发磁盘IO，所以先来说说磁盘寻道的过程：

如果磁盘不是SSD类型，大致长上面这个样子，里面有一个个的盘面和磁针，当发生磁盘IO时，首先会根据给出的磁盘地址，在盘面上寻道。

这个寻道过程是怎么回事呢？

就跟小时候VCD、DVD放光碟类似，盘面会开始转圈圈，在盘面上有一个磁道的概念

当转到了对应的地址时，磁道和磁针会相互吸引，然后以一上一下的方式读取0、1二进制数据，最终从磁盘中将目标地址中的数据读取出来。

当走全表扫描时，会发生磁盘IO，但是磁盘寻道是需要有一个地址的，这个地址最开始就是本地表数据文件中的起始地址，也就是从表中的第一行数据开始读，读到数据后会载入内存，然后MySQL-Server会根据SQL条件对读到的数据做判断，如果不符合条件则继续发生磁盘IO读取其他数据（如果表比较大，这里不会以顺序IO的形式走全表检索，而是会触发随机的磁盘IO）。

上面的用户表中，「钱七」这条数据位于表的第五行，那这里会发生五次磁盘IO吗？

答案是不是，为什么呢？因为OS、MySQL中都有一个优化措施，叫做局部性读取原理。

1.1：局部性原理

局部性原理的思想比较简单，比如目前有三块内存页x、y、z是相连的

CPU此刻在操作x页中的数据，那按照计算机的特性，一般同一个数据都会放入到物理相连的内存地址上存储

也就是当前在操作x页的数据，那么对于y，z这两页内存的数据也很有可能在接下来的时间内被操作

因此对于y，z这两页数据则会提前将其载入到高速缓冲区（L1/L2/L3），这个过程叫做利用局部性原理“预读”数据

上面说的是操作系统高速缓冲区的知识，在CPU中利用局部性原理

提前将数据从内存先放入L1/L2/L3三级缓冲区中，主要是为了减小CPU寄存器与内存之间的性能差异。

对于MySQL而言，亦是同理，存储数据的磁盘和内存之间的性能差异也是巨大的，因为MySQL也会利用局部性原理，提前“预读”数据。

MySQL一次磁盘IO不仅仅只会读取一条表数据，而是会读取多条数据，在InnoDB引擎中，一次默认会读取16KB数据到内存。

1.2：全表扫描过程

由于MySQL中会使用局部性原理的思想，所以对于给出的用户表数据而言，可能只需发生一次磁盘IO就能将前五条数据全部读到内存

然后会在内存中对本次读取的数据逐条判断，看一下每条数据的姓名字段是否为「钱七」：

• 如果发现不符合SQL条件的行数据，则会将当前这条数据放弃，同时在本次SQL执行过程中会排除掉这条数据，不会对其进行二次读取。
• 如果发现当前的数据符合SQL条件要求，则会将当前数据写入到结果集中，然后继续判断其他数据。

当本次磁盘IO读取到的所有数据全部筛选完成后，紧接着会看一下表中是否还有其他数据

• 如果还有则继续触发磁盘IO检索数据
• 如果没有则将内存中的结果集返回。

为什么这里已经读到了符合条件的数据，还需要继续发生磁盘IO呢？

因为表中的字段没有建立唯一索引或唯一约束，因此MySQL不确定是否还有其他同名的数据，所以需要将整个表全部扫描一遍，才能得到最终结论。

1.3：全表扫描弊端

数据一多就会出问题…

假设表中一条数据大小为512Byte，一次磁盘IO也只能读32条，表中有320w条数据，一次全表就有可能会触发10W次磁盘IO

每次都需要在硬件上让那个盘面转啊转，其过程的开销可想而知…

因此建立索引的原因就在于此处，为了避免查询时走全表扫描，因此全表扫描的开销会随着数据量增长而越来越大。

2：为何选择B+树

各种数据结构可以看这个演示：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

2.1：为啥淘汰二叉树和红黑树？

普通二叉树问题

• 如果索引的字段值是按顺序增长的，二叉树会转变为链表结构。
• 由于结构转变成了链表结构，因此检索的过程和全表扫描无异。
• 由于树结构在磁盘中，各节点的数据并不连续，因此无法利用局部性原理。

红黑树问题

• 虽然对比二叉树来说，树高有所降低，但数据量一大时，依旧会有很大的高度。
• 每个节点中只存储一个数据，节点之间还是不连续的，依旧无法利用局部性原理。

2.2：为啥淘汰B树？

数据和键值放在同一级，导致一个磁盘块可以保存的数据量会因为data的存在而大大降低，三层树，可能也就几千几万个数据

虽然对比之前的红黑树更矮，检索数据更快，也能够充分利用局部性原理减少IO次数，但对于大范围查询的需求，依旧需要通过多次磁盘IO来检索数据。

2.3：为啥选择B+树

除了叶子节点之外，其他节点只存储指针和键值

B+树有一个最大的变化就是：最下面的一排节点之间，都存在一个单向指针，指向下一个节点所在的位置，这也是B+树对B树的最大改造点

2.4：千万级别的表B+Tree会有多高

对于索引单个节点的容量是多少呢？

在MySQL中默认使用引擎的一页大小作为单节点的容量，假设此时表的存储引擎为InnoDB，就可以通过下述这条命令查询：

从上述查询结果来看，InnoDB引擎的一页大小为16384 Bytes，也就是16KB，此时也就代表着B+Tree的每个节点容量为16KB。

指针是多大呢？ - 6Bytes

一般来说，操作系统的指针为了方便寻址，一般都与当前的操作系统位数对应，例如32位的系统，指针就是32bit/4Bytes，64位的操作系统指针则为64bit/8Bytes

由于64bit的指针寻址范围太大，目前的计算机根本用不上这么大的寻址范围，因此在MySQL-InnoDB引擎的源码中，单个指针被缩小到6Bytes大小。

千万级树高计算？

从上述三条可得知：单个索引节点容量为16KB，主键字段值为4B，指针大小为6B，一个完整的索引信息是由主键字段值+指针组成的，也就是4+6=10B

那此时先来计算一下单个节点中可存储多少个索引信息呢 -> 16KB / 10B ≈ 1638个。

来算算树高为3的B+树可以存多少呢？因为最下面一排才是叶子节点，此时树高为3，也就代表着中间一排是叶节点，只存储指针并不存储数据，而每个节点可容纳1638个索引键+指针信息，因此计算过程是：1638 * 1638 * 16 = 42928704条。

树高为3的B+Tree，竟然可以存储四千多万条数据，也就代表着千万级别的表，走索引查询的情况下，大致只需要发生三次磁盘IO即可获取数据。

2.5：MySQL索引底层的真正结构

虽然B+Tree已经特别特别优秀了，但B+Tree的叶子节点之间是单向指针组成的链表结构，这对于倒排序查询时，显然并不友好

因为只有单向指针，那么只能先正序获取数据后再倒排一次，因此MySQL真正的索引结构还对B+Tree做了变种设计！

MySQL变种的内容就是所有叶子节点变种成为一个双向链表结构。

上面给出的b+树的图的那种形状

这样做的好处在于：即可以快速按正序进行范围查询，而可以快速按倒序进行范围操作，在某些业务场景下又能进一步提升整体性能！

2.6：前缀索引为何能提升索引性能

为前缀索引可以选用一个字段的前N个字符来创建索引，相较于使用完整字段值做为索引键，前缀索引的索引键，显然占用的空间更少

一个索引键越小，代表一个B+Tree节点中可以存储更多的索引键，等价于树高会越小，也就代表磁盘IO更少，检索数据时自然效率更高。

3：索引建立时的内部操作

通过SQL命令创建索引时，MySQL首先会判断一下当前表的存储引擎

索引机制本身是由存储引擎层提供实现的，不同的引擎实现的索引也不同，因此创建索引时第一步就会先判断存储引擎，然后根据不同的存储引擎创建索引

1：常用存储引擎的数据结构

-- 创建一张使用MyISAM引擎的表：zz_myisam_index
CREATE TABLE zz_myisam_index  (
  z_m_id int(8) NOT NULL,
  z_m_name varchar(255) NULL DEFAULT ''
) 
ENGINE = MyISAM 
CHARACTER SET = utf8 
COLLATE = utf8_general_ci 
ROW_FORMAT = Compact;

-- 创建一张使用InnoDB引擎的表：zz_innodb_index
CREATE TABLE zz_innodb_index  (
  z_i_id int(8) NOT NULL,
  z_i_name varchar(255) NULL DEFAULT ''
) 
ENGINE = InnoDB 
CHARACTER SET = utf8 
COLLATE = utf8_general_ci 
ROW_FORMAT = Compact;

上述过程中创建了两张表：zz_myisam_index、zz_innodb_index，分别使用了不同的引擎

MySQL中对于所有的数据都会放入到磁盘中存储，因此先来找一下这两张表的本地位置

myisam的三个文件分别是：(8.0版本)

• zz_myisam_index.MYD：该文件中存储表的行数据。
• zz_myisam_index.MYI：该文件中存储表的索引数据。
• zz_myisam_index_570.sdi：MySQL8将frm文件的信息以及更多信息移动到叫做序列化字典信息(SDI)中

innodb的文件是：(8.0版本)

• zz_innodb_index.ibd：数据库信息、表结构、表数据以及表索引均存储在ibd文件中。

2：手动创建索引发生的事情

当手动创建索引后，MySQL会先看一下当前表的存储引擎是谁，接着会判断一下表中是否存在数据：

• 如果表中没有数据，则直接构建一些索引的信息，例如索引字段是谁、索引键占多少个字节、创建的是啥类型索引、索引的名字、索引归属哪张表、索引的数据结构…，然后直接写入对应的磁盘文件中，比如MyISAM的表则写入到.MYI文件中，InnoDB引擎的表则写入到.ibd文件中。
• 当表中有数据时，首先MySQL-Server会先看一下目前要创建什么类型的索引，然后基于索引的类型对索引字段的值，进行相应的处理，比如：
  • 唯一索引：判断索引字段的每个值是否存在重复值，如果有则抛出错误码和信息。
  • 主键索引：判断主键字段的每个值是否重复、是否有空值，有则抛出错误信息。
  • 全文索引：判断索引字段的数据类型是否为文本，对索引字段的值进行分词处理。
  • 前缀索引：对于索引字段的值进行截取工作，选用指定范围的值作为索引键。
  • 联合索引：对于组成联合索引的多个列进行值拼接，组成多列索引键。
  • …
• 做了相应处理后，紧接着会再看一下当前索引的数据结构是什么？是B+Tree、Hash亦或是其他结构，然后根据数据结构对索引字段的值进行再次处理
  • B+Tree：对索引字段的值进行排序，按照顺序组成B+树结构。
  • Hash：对索引字段的值进行哈希计算，处理相应的哈希冲突，方便后续查找。
  • …
• 已经根据索引结构，对索引字段的值处理好了，但是如果此时为InnoDB引擎，那在写入前还会判断当前的索引是否为主键/聚簇索引：
  • 如果当前创建索引的字段是主键字段，则在写入时重构.ibd文件中的数据，将索引键和行数据调整到一块区域中存储

3：索引键的大小会随着值长度变化吗

比如现在基于一个int类型的字段建立了一个索引，但目前的字段值是1，按理来说这个值只占1bits对不对？

那在索引键中，或数据库中占多少呢？答案是4Bytes/32bits

这是因为一个int类型在操作系统中就会占用32bit空间，不会根据实际值而减少占用空间。

但数据库中还有不少文本类型，例如varchar类型，它是固定的长度吗？

并不是，它是一个变长类型，而非一个定长类型，也就是一个varchar字段值，占用的空间会随着实际所存储的数据而变化。

所以对于一个索引键的大小是否会发生变化，要取决于是基于什么字段类型建立的索引，如果是定长类型就不会变化，但如果是变长类型就会随之发生改变。