MySQL学习笔记架构篇

Posted on Edited on In Views:
这是学习MySQL的笔记架构篇，主要是逻辑架构、存储引擎、索引的数据结构

MySQL逻辑架构

MySQL是一个C/S架构，客户端向服务端发送一段SQL语句，服务端处理后，返回给客户端处理结果。

针对MySQL 5版本。图中包含了MySQL 8已经抛弃的查询缓存。

服务端处理客户端请求流程：

image-20221112122337220

具体展开：

Connectors：客户端程序

Management Services & Utilities：基础服务组件

Connection Pool：连接池，提供多个客户端与服务端交互的线程

SQL Interface：SQL接口，接收SQL指令，返回查询结果

Parser：解析器，解析SQL指令，语法解析、语义解析，生成语法树

Optimizer：优化器，对SQL语句进行优化，SQL核心组件

Caches & Buffers：查询缓存，以key-value的方式缓存查询结果（由于数据会变化，实际命中缓存概率低，MySQL 8版本去掉了）

Pluggable Storage Engines：插入式的存储引擎

File system：文件系统，存储引擎与文件系统进行交互

Files & Logs：日志文件

MySQL Server三层架构

连接层

客户端与服务端建立TCP连接，为了解决TCP无限创建与TCP频繁创建、销毁带来的资源耗尽、性能下降问题，MySQL服务器有TCP连接池限制连接数，采用长连接模式复用TCP连接，来解决上述问题。

image-20221112123841729

TCP连接收到请求后，必须要分配一个线程专门与这个客户端交互，所以还会有个线程池，每一个连接从线程池中获取线程，省去了创建和销毁线程的开销。

连接管理的职责是负责认证、管理连接、获取权限信息。

服务层

服务器会解析查询并创建相应的内部解析树，并对其完成相应的优化，如确定查询表的顺序，是否利用索引等，最后生成相应的执行操作。

主要包含SQL Interface，Parser，Optimizer，Caches & Buffers`。

引擎层

插件式的存储引擎架构将查询处理和其他的系统任务以及数据的存储提取相分离，可以根据业务的需求和实际需要选择合适的存储引擎。

插件式存储引擎层，真正的负责了MySQL中数据的存储和提取，对物理服务器级别维护的底层数据执行操作，服务器通过API与存储引擎进行通信。不同的存储引擎具有的功能不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SHOW ENGINES;
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
| Engine             | Support | Comment                                                        | Transactions | XA   | Savepoints |
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
| ndbcluster         | NO      | Clustered, fault-tolerant tables                               | NULL         | NULL | NULL       |
| FEDERATED          | NO      | Federated MySQL storage engine                                 | NULL         | NULL | NULL       |
| MEMORY             | YES     | Hash based, stored in memory, useful for temporary tables      | NO           | NO   | NO         |
| InnoDB             | DEFAULT | Supports transactions, row-level locking, and foreign keys     | YES          | YES  | YES        |
| PERFORMANCE_SCHEMA | YES     | Performance Schema                                             | NO           | NO   | NO         |
| MyISAM             | YES     | MyISAM storage engine                                          | NO           | NO   | NO         |
| ndbinfo            | NO      | MySQL Cluster system information storage engine                | NULL         | NULL | NULL       |
| MRG_MYISAM         | YES     | Collection of identical MyISAM tables                          | NO           | NO   | NO         |
| BLACKHOLE          | YES     | /dev/null storage engine (anything you write to it disappears) | NO           | NO   | NO         |
| CSV                | YES     | CSV storage engine                                             | NO           | NO   | NO         |
| ARCHIVE            | YES     | Archive storage engine                                         | NO           | NO   | NO         |
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
11 rows in set (0.02 sec)

小结

简化后

image-20221112124617740

  1. 连接层：客户端和服务端建立连接，客户端发送SQL至服务器端；
  2. SQL层：对SQL语句进行查询处理；与数据库文件的存储方式无关；
  3. 存储引擎层：与数据库文件打交道，负责数据的存储和读取

SQL执行流程

执行流程

image-20221112124803162

MySQL查询流程：

  1. 查询缓存：如果Server在查询缓存中发现了同样的一条SQL语句，就会直接将结果返回给客户端；如果没有，就进入解析器阶段。因为查询缓存效率不高（1、如果查询字段更新，2、带有一些函数，类似now()，都无法命中。另外，当更新、插入等操作修改数据，让查询缓存失效，此时对于数据库会有性能损耗，因此弊大于利），在MySQL 8.0之后就抛弃了这个功能。

  2. 解析器：对SQL语句做解析。

    SQL语句的解析分为此法分析和语法分析。

    首先做词法分析，识别SQL中的字符串分别是什么，代表什么

    接着做语法分析，根据词法分析的结果，语法分析器（比如Sison）会根据语法规则，判断你输入的这个SQL语句是否满足MySQL语法。

    语法树：

    image-20221112223544373

    SQL词法分析的过程步骤：

    image-20221112223655736

  3. 优化器：确定SQL语句的执行路径，比如是根据全表检索，还是根据索引检索等，优化器最终会生成一个执行计划。

    一条查询可以有很多种执行方式，最后都返回相同的结果。优化器的作用就是找出最好的执行计划。

    查询优化器分为物理查询优化器和逻辑查询优化器。

  4. 执行器：在执行之前需要判断该用户是否具备权限。如果没有就返回权限错误，如果具备权限，就执行优化器生成的执行计划。8.0版本以下，如果设置了查询缓存，则也会将查询语句和结果存储到缓存中。

SQL语句在MySQL中的流程是：

image-20221112224227279

SQL执行原理

针对MySQL 8.0版本。

  1. 查看是否开启计划，开启时，手机SQL执行时所使用的资源情况

    1
    2
    3
    4
    5
    6
    7
    -- 查看记录过程是否开启
    -- 0 代表没有开启，1代表开启
    SELECT @@profiling;
    -- 或者查看会话配置
    SELECT @@session.profiling;
    -- 临时修改，永久修改需要修改配置文件 /etc/my.cnf
    SET @@profiling=1;

    使用

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    -- 使用分析
    SELECT * FROM employee;
    -- 查看所有查询的资源使用情况
    SHOW PROFILES;
    -- 查看最近一次
    SHOW PROFILE;
    SHOW PROFILE FOR QUERY 92;
    +--------------------------------+----------+
    | Status                         | Duration |
    +--------------------------------+----------+
    | starting                       | 0.000090 |
    | Executing hook on transaction  | 0.000005 |
    | starting                       | 0.000010 |
    | checking permissions           | 0.000008 |
    | Opening tables                 | 0.000049 |
    | init                           | 0.000008 |
    | System lock                    | 0.000011 |
    | optimizing                     | 0.000006 |
    | statistics                     | 0.000024 |
    | preparing                      | 0.000128 |
    | executing                      | 0.000086 |
    | end                            | 0.000006 |
    | query end                      | 0.000005 |
    | waiting for handler commit     | 0.000012 |
    | closing tables                 | 0.000010 |
    | freeing items                  | 0.000093 |
    | cleaning up                    | 0.000024 |
    +--------------------------------+----------+
    17 rows in set, 1 warning (0.01 sec)

    还可以增加更多资源，以便查看

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    -- 查看CPU时间，阻塞时间
    SHOW PROFILE cpu,block io FOR QUERY 2;
    +--------------------------------+----------+----------+------------+--------------+---------------+
    | Status                         | Duration | CPU_user | CPU_system | Block_ops_in | Block_ops_out |
    +--------------------------------+----------+----------+------------+--------------+---------------+
    | starting                       | 0.000090 | 0.000046 |   0.000043 |            0 |             0 |
    | Executing hook on transaction  | 0.000005 | 0.000003 |   0.000002 |            0 |             0 |
    | starting                       | 0.000010 | 0.000005 |   0.000004 |            0 |             0 |
    | checking permissions           | 0.000008 | 0.000004 |   0.000004 |            0 |             0 |
    | Opening tables                 | 0.000049 | 0.000025 |   0.000024 |            0 |             0 |
    | init                           | 0.000008 | 0.000004 |   0.000004 |            0 |             0 |
    | System lock                    | 0.000011 | 0.000006 |   0.000005 |            0 |             0 |
    | optimizing                     | 0.000006 | 0.000003 |   0.000003 |            0 |             0 |
    | statistics                     | 0.000024 | 0.000013 |   0.000011 |            0 |             0 |
    | preparing                      | 0.000128 | 0.000128 |   0.000000 |            0 |             0 |
    | executing                      | 0.000086 | 0.000086 |   0.000000 |            0 |             0 |
    | end                            | 0.000006 | 0.000006 |   0.000000 |            0 |             0 |
    | query end                      | 0.000005 | 0.000005 |   0.000000 |            0 |             0 |
    | waiting for handler commit     | 0.000012 | 0.000012 |   0.000000 |            0 |             0 |
    | closing tables                 | 0.000010 | 0.000010 |   0.000000 |            0 |             0 |
    | freeing items                  | 0.000093 | 0.000093 |   0.000000 |            0 |             0 |
    | cleaning up                    | 0.000024 | 0.000025 |   0.000000 |            0 |             0 |
    +--------------------------------+----------+----------+------------+--------------+---------------+
    17 rows in set, 1 warning (0.01 sec)

数据库缓冲池

InnoDB存储引擎是以页为单位来管理存储空间的，为了让数据表或者索引中的数据随时被使用，DBMS会申请占用内存来作为数据缓冲池，在真正访问呢页面之前，需要把磁盘上的页缓存到内存中的Buffer Pool之后才可以访问。减少与磁盘直接进行I/O的时间，提升SQL语句的查询性能。

缓冲池

InnoDB的缓冲池存放信息如下：

image-20221112230501414

缓存原则：

依据位置 * 频次这个原则

  • 位置：决定效率，提供缓冲池就是为了在内存中可以直接访问数据
  • 频次：决定优先级顺序，磁盘中的部分数据才会缓存，会优先对使用频次高的热数据进行加载

缓冲池的预读特性：

缓存一些数据时，会遵循局部性原理，大概率还会使用它周围的一些数据，因此采用预读的机制提前加载，减少未来可能得磁盘I/O操作。

缓冲池读取数据

缓冲池读取诗句的结构图如下：

image-20221112230927518

对数据库中的记录进行修改的时候，首先会修改缓冲池页面里的记录信息，然后数据库会以一定的频率刷新到磁盘上，采用一种叫做checkpoint的机制将数据回写到磁盘上。

比如当缓冲池不够用时，需要释放一些不常用的页，此时就可以强行采用checkpoint的方式，将不常用的脏页回写到磁盘上，然后从缓冲池将这些页释放掉。这里的脏页指的是缓冲池中被修改过的页，与磁盘上的数据页不一致。

查看、设置缓冲池的大小

MyISAM存储引擎，只缓存索引，不缓存数据，对应的键缓存参数为 key_buffer_size

1
2
3
4
5
6
7
SHOW VARIABLES LIKE '%key_buffer_size%';
+-----------------+---------+
| Variable_name   | Value   |
+-----------------+---------+
| key_buffer_size | 8388608 |
+-----------------+---------+
1 row in set (0.01 sec)

InnoDB存储引擎，通过 innodb_buffer_pool_size 变量查看缓冲池的大小

1
2
3
4
5
6
7
8
9
10
-- 查看缓存大小
SHOW VARIABLES LIKE '%innodb_buffer_pool_size%';
+-------------------------+-----------+
| Variable_name           | Value     |
+-------------------------+-----------+
| innodb_buffer_pool_size | 134217728 |   -- 128M
+-------------------------+-----------+
1 row in set (0.01 sec)
-- 修改缓存大小
SET GLOBAL innodb_buffer_pool_size = 134217728;

多个Buffer Pool实例

Buffer Pool缓冲池本质是InnoDB向操作系统申请的一块连续的内存空间，多线程环境下，访问Buffer Pool需要加锁。在多线程高并发时，单一的Buffer Pool会造成性能瓶颈，因此Buffer Pool特别大时，可以把他们拆分成若干个小的Buffer Pool，每个Buffer Pool称为一个实例，有独立的内存空间，独立的管理各种链表。

通过修改配置文件中的innodb_buffer_pool_instances的值修改Buffer Pool个数

1
2
3
4
5
6
7
SHOW VARIABLES LIKE '%innodb_buffer_pool_instances%';
+------------------------------+-------+
| Variable_name                | Value |
+------------------------------+-------+
| innodb_buffer_pool_instances | 1     |
+------------------------------+-------+
1 row in set (0.01 sec)

缓冲池总容量不变，设置之后，每个Buffer Pool带下平摊。

Buffer Pool实例不是越多越好，分别管理各个Buffer Pool也是需要性能开销的。

InnoDB规定：当 innodb_buffer_pooLsize的值小于1G的时候设置多个实例是无效的，InnoDB会默认把innodb_buffer_poolinstances 的值修改为1。而我们鼓励在Buffer Pool大于或等于1G的时候设置多个Buffer Pool实例。

注意

  1. 查询数据时，会先在缓冲池查询，如果缓冲池不存在，则存储引擎会先将数据从磁盘加载到缓冲池中，然后将数据返回给客户端。
  2. 修改数据时，如果数据不在缓冲池，则存储引擎会先将数据从磁盘加载到缓冲池中，修改内存的数据。被修改后的数据会在之后统一输入磁盘

image-20221112232526729

也就是说，如果缓冲池数据修改成功，但是没来得及刷盘，此时如果MySQL宕机，这部分数据将永久丢失。或者在事务操作时，部分事务落盘，部分事务没有落盘，此时MySQL宕机，无法保持事务的ACID。

因此需要通过Redo Log 和 Undo Log解决上述两个问题。

存储引擎

存储引擎的功能是存取数据，按照生成的执行计划调用底层存储引擎提供的API。其实存储引擎就是指表的类型，数据的存储方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
SHOW ENGINES;
-- 引擎                             是否支持		描述																														是否支持事务			是否支持分布式事务  检查点
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
| Engine             | Support | Comment                                                        | Transactions | XA   | Savepoints |
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
| ndbcluster         | NO      | Clustered, fault-tolerant tables                               | NULL         | NULL | NULL       |
| FEDERATED          | NO      | Federated MySQL storage engine                                 | NULL         | NULL | NULL       |
| MEMORY             | YES     | Hash based, stored in memory, useful for temporary tables      | NO           | NO   | NO         |
| InnoDB             | DEFAULT | Supports transactions, row-level locking, and foreign keys     | YES          | YES  | YES        |
| PERFORMANCE_SCHEMA | YES     | Performance Schema                                             | NO           | NO   | NO         |
| MyISAM             | YES     | MyISAM storage engine                                          | NO           | NO   | NO         |
| ndbinfo            | NO      | MySQL Cluster system information storage engine                | NULL         | NULL | NULL       |
| MRG_MYISAM         | YES     | Collection of identical MyISAM tables                          | NO           | NO   | NO         |
| BLACKHOLE          | YES     | /dev/null storage engine (anything you write to it disappears) | NO           | NO   | NO         |
| CSV                | YES     | CSV storage engine                                             | NO           | NO   | NO         |
| ARCHIVE            | YES     | Archive storage engine                                         | NO           | NO   | NO         |
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
11 rows in set (0.02 sec)

查看默认存储引擎。5.5版本默认使用MyISAM，之后默认存储引擎改成InnoDB。创建表时没有指定存储引擎，则使用默认存储引擎。

1
2
3
4
-- 查看默认存储引擎
SHOW VARIABLES LIKE '%storage_engine%';
-- 或者
SELECT @@default_storage_engine;

修改默认存储引擎

1
2
3
-- 临时修改
SET default_storage_engine=MyISAM;
-- 或者永久修改，修改 /etc/my.cnf 配置文件

创建表时指定存储引擎

1
CREATE TABLE test1(id INT) ENGINE=MyISAM;

InnoDB引擎

具备外键支持功能的事务存储引擎

  • MySQL 版本大于5.5之后，默认采用InnoDB引擎

  • InnoDB是MySQL的默认事务型引擎，用来处理大量的短期（short-lived）事务，可以确保事务的完整提交(commit)和回滚(rollback)

  • 相比更新、删除操作，InnoDB更有优势（MyISAM在增加和查询更有优势）

  • 数据文件结构

    表名.frm 存储表结构（MySQL 8.0时，合并到表名.ibd中）

    表名.ibd 存储数据和索引

  • InnoDB是为处理巨大数据量的最大性能设计

在以前的版本中，字典数据以元数据文件、非事务表来存储，现在这些元数据文件被删除了

  • 相比MyISAM，InnoDB写的处理效率差一些，并且会占用更多的磁盘空间以保存数据和索引
  • 相比MyISAM只缓存索引，InnoDB缓存索引和真实数据，对内存要求高，而且内存大小对性能有决定性的影响

MyISAM引擎

主要的非事务处理存储引擎。

  • MyISAM提供了大量的特性，包括全文索引、压缩、空间函数（GIS）等，但MyISAM不支持事务，行级锁，外键，以及没有undo日志和redo日志，可能出现崩溃后无法安全恢复

  • MySQL 5.5之前默认的存储引擎

  • 优势是访问速度快，在select和insert下性能更高

  • 针对数据统计有额外的常数存储，count(*)查询效率很高

  • 数据文件结构

    • 表名.frm 存储表结构
    • 表名.MYD 存储数据 MYData
    • 表名.MYI 存储索引 MYIndex

  • 应用场景：只读应用或者以读为主的业务

Archive 引擎

用于数据存档

  • 仅支持插入和查询（行被插入后不能再修改）
  • 在MySQL 5.5以后支持索引功能
  • 拥有很好的压缩机制，使用zlib压缩库，在记录请求的时候实时进行压缩，经常被用来作为仓库使用
  • 创建Archive表时，存储引擎会创建名称以表名开头的文件，数据文件的扩展名为.ARZ
  • 根据英文的测试结果来看，同样的数据量下，Archive表比MyISAM表小大约75%，比支持事务处理的InnoDB表小大约83%
  • Archive存储引擎采用了行级锁，支持auto_increment列属性，auto_increment列可以具有唯一索引或非唯一索引，尝试在任何其他列上创建索引会导致错误
  • Archive表适合日志和数据采集（档案）类应用；合适存储大量的独立的座位历史记录的数据。拥有很高的插入速度，但是对查询的支持较差。
特征 支持
B树索引 不支持
备份/时间点恢复（在服务器中实现，而不是在存储引擎中） 支持
集群数据库支持 不支持
聚集索引 不支持
压缩数据 支持
数据缓存 不支持
加密数据（加密功能在服务器中实现） 支持
外键支持 不支持
全文检索索引 不支持
地理空间数据类型支持 支持
地理空间索引支持 不支持
哈希索引 不支持
锁粒度 行锁
MVCC 不支持
存储限制 没有任何限制
交易 不支持
更新数据字典的统计信息 支持

Blackhole 引擎

丢弃写操作，读操作会返回空内容。

  • Blackhole 引擎没有实现任何存储机制，会丢弃所有插入的数据，不做任何保存
  • 服务器会记录Blackhole表的日志，可以用于复制数据到备库，或者简单的记录日志，这种应用方式会碰到很多问题，因此并不推荐。

CSV 引擎

存储数据时，以逗号分隔各个数据项。

  • CSV引擎可以将普通的CSV文件作为MySQL的表来处理，但不支持索引
  • CSV引擎可以作为一种数据交换的机制，非常有用
  • CSV存储的数据直接可以在操作系统里，用文本编辑器，或者excel读取
  • 对于数据的快速导入、导出有明显优势

创建CSV表时，服务器会创建一个纯文本数据文件，名称以表名开头并带有.CSV扩展名。当数据存储到表中时，存储引擎将其以逗号分隔值格式保存到数据文件中。

1
2
3
4
5
6
7
-- 创建CSV表 
-- 所有字段都不能为空 
CREATE TABLE csv_demo(id INT NOT NULL,name CHAR(20) NOT NULL) ENGINE=csv;
-- 插入数据 
INSERT INTO csv_demo VALUES(1,'mitaka'),(2,'xiaoyeshiyu');
-- 获取数据
SELECT * FROM csv_demo;

查看文件信息

1
2
3
4
5
6
7
8
-rw-r-----  1 mysql mysql 2.4K Nov 13 05:31 csv_demo_542.sdi
drwxr-x---  2 mysql mysql 4.0K Nov 13 05:31 .
-rw-r-----  1 mysql mysql   27 Nov 13 05:32 csv_demo.CSV
-rw-r-----  1 mysql mysql   35 Nov 13 05:32 csv_demo.CSM

cat csv_demo.CSV
1,"mitaka"
2,"xiaoyeshiyu"

Memory 引擎

置于内存的表。

Memory采用的逻辑介质是内存，响应速度很快，但是当mysqld守护进程崩溃的时候数据会丢失。另外，要求存储的数据时数据长度不变的格式，比如，Blob和text类型的数据不可用（长度不固定）。

主要特征：

  • Memory同时支持哈希（HASH）索引和B+树索引

    • 哈希索引相等的比较快，但是对于范围的比较慢很多
    • 默认使用哈希索引，速度比使用B+树快
    • 如果要使用B+树，可以创建索引时选择使用

  • Memory表至少比MyISAM表要快一个数量级

  • Memory表的大小受到限制，表的大小主要取决于两个参数，分别是max_rows和max_heap_table_size。其中max_rows可以在创建表时指定；max_heap_table_size默认16MB，可以根据需要扩大

  • 数据文件与索引文件分开存储

    • 每个基于Memory存储引擎的表实际对应一个磁盘文件，该文件的文件名与表名相同，类型为**frm类型**，该文件中只存储表的结构，而其数据文件都是存储在内存中的。
    • 有利于数据的快速处理，提供整个表的处理效率

  • 缺点是数据容易丢失，生命周期短。

使用场景：

  • 数据比较小，而且频繁的进行访问，在内存中存放数据，数据量受限于内存。
  • 如果数据是临时的，而且必须立即可用，那么就可以放在内存中
  • 数据丢失影响不大

Federated 引擎

访问远程表，是访问其他MySQL服务器的一个代理，尽管该引擎看起来提供了一种很好的跨服务器的灵活性，但经常带来问题，因此默认禁用。

Merge 引擎

管理多个MyISAM表构成的表集合

NDB 引擎

MySQL集群专用存储引擎，也叫做NDB Cluster存储引擎，主要用于MySQL Cluster 分布式存储环境。

MyISAM和InnoDB对比

对比项 MyISAM InnoDB
外键 不支持 支持
事务 不支持 支持
行表锁 表锁，即使操作一条记录也会锁住整个表，不适合高并发的操作 行锁，操作时只锁某一行，不影响其他行，适合高并发的操作
缓存 只缓存索引，不缓存真实数据 缓存数据和索引，对内存要求高，而且内存大小决定性能
自带系统表使用 Y N
关注点 性能：节省资源、消耗少、简单业务 事务：并发写、事务、更大资源
默认安装 Y Y
默认使用 MySQL 5.5版本之前 MySQL 5.5 版本之后

索引的数据结构

索引时存储引擎用于快速找到数据记录的一种数据结构，就好比书的目录。MySQL进行数据查找时，首先查看查询条件是否命中某条索引，符合则通过索引查找相关数据，如果不符合则需要全表扫描，也就是需要一条一条查找记录，直到找到与条件符合的记录。

相比顺序查找，时间复杂度是o(n)，使用二叉树的数据结构更适合查找，时间复杂度是o(logn)(2为底n的对数)。

image-20221113135351758

使用索引的好处就是减少磁盘I/O的次数，加快查询速率。

索引及其优缺点

索引Index是帮助MySQL高效获取数据的数据结构。

索引的本质：索引是数据结构。为了排好序的快速查找数据结构，满足特定查找算法，这些数据结构以某种方式指向数据，可以在这些数据结构的基础上实现高级查找算法。

索引时在存储引擎中实现的，因此每种存储引擎的索引不一定完全相同，而且每种存储引擎不一定支持所有索引类型。同时，存储引擎可以定义每个表的最大索引数和最大索引长度。所有存储引擎支持每个表上限至少16个索引，总索引长度上限至少为256字节。有些存储引擎支持更多的索引数和更大的索引长度。

有点

  • 提高检索效率，降低I/O成本
  • 通过创建唯一索引，可以保证数据库表中的每一行数据的唯一性
  • 加速表和表之间的连接，有依赖关系的子表和父表联合查询时，可以提高查询速度
  • 使用分组和排序子句进行数据查询时，可以减少查询中分组和排序的时间，降低CPU消耗

缺点

  • 创建和维护索引需要消耗时间，并且随着数据量的增加，耗费的时间也会增加
  • 索引需要占用磁盘空间
  • 降低更新表的速度，对表中数据增加、删除和修改时，索引也要动态维护，降低了数据的维护速度

提示：

索引可以提高查询速度，但是会影响插入速度，这种情况下，最好的办法是先删除表中的索引，插入之后，再创建索引。

InnoDB索引的推演

索引是在存储引擎中创建，这里以InnoDB的索引为例。

数据库中数据的基本存储单位是数据页。查找一条数据是通过某一列的条件进行查找。

在一个页中的查找

如果数据很少，在一页中存储

  • 以主键为搜索条件

    在页目录中使用二分法快速定位到对应的槽，然后遍历该槽对应分组中的记录即可快速找到指定的记录。

  • 以其他列作为搜索条件

    其他列没有在索引中，而且没有顺序，这种情况只能从最小记录开始依次遍历单链表（减少内存占用，而且不需要存储时连续）中的每条记录，然后对比是否符合搜索条件。

在很多页中查找

数据量很多时，需要将数据进行分页存储

  1. 定位到所在页
  2. 在所在页查找

此时只能从第一页沿着双向链表一直往下找，在每一页中根据查找方式去查找指定的记录。因为要遍历所有的数据页，这种方式很耗时，因此需要索引。

简单索引设计方案

1
2
3
4
5
6
7
8
CREATE TABLE index_demo1(
c1 INT,
c2 INT,
c3 VARCHAR(1),
-- 将 c1 列设置为主键
PRIMARY KEY(c1)
-- 设置表存储的行格式，为 Compact 
) ROW_FORMAT = Compact;

Compact行格式存储记录示意图：

image-20221113141912427

  • record_type：记录头信息的一项属性，表示记录的类型，0表示普通记录，2表示最小记录，3表示最大记录，1表示目录项记录
  • next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，例如链表，指向下一个记录
  • 各个列的值：例如index_demo1表中三列，c1列，c2列，c3列
  • 其他信息：除了上述3中信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息

如果横过来看，这些记录在页里的示意图：

image-20221114110046705

如果插入一些记录

1
INSERT INTO index_demo1 VALUES(1,4,'u'),(3,9,'d'),(5,3,'y');

数据排序

这些记录按照主键值的大小串联成一个单向链表：（真实页可能会存放数千条记录，这里假设只存储能3条）

image-20221114110254441

由于设置主键，因此即使操作上没有顺序插入，在存储的时候，还是会按照顺序排列。

在存储3条记录之后，如果还要再存储数据，则需要再分配一个新页

1
INSERT INTO index_demo1 VALUES(4,4,'a');

分配新页之后，数据页编号可能不连续，也需要一个双向链表维护关系。

image-20221114110704707

又因为主键插入4，小于5，所以不符合下一数据页中记录的主键必须大于上一页记录主键的要求，因此，插入4记录的时候，还需要一次记录移动，将数据5从页10移动到页28

image-20221114110833872

对页中的记录进行增删改的操作过程中，必须通过一些诸如记录移动的操作来时钟保证这个状态一直成立：下一页的主键必须大于上一页的主键。将记录移动的操作这个过程称为页分裂。

给所有页建立一个目录项

由于数据页的编号不一定连续，所以向index_demo1表中插入许多记录后，可能出现这样的效果

image-20221114145615952

如果想从这么多页中根据主键值快速定位某些记录所在的页，可以给页加一个目录，每页一个目录项，每个目录项包括：

  • 页的用户记录中最小的主键值，用key表示
  • 页号，用page_no表示

image-20221114150049332

当通过主键c1字段查询时，首先与目录项进行匹配查询，获取到对应的page_no后，再在对应页中查询。这个过程实际上是用两次二分查找法。

针对数据页做的简易目录就是这样，这个目录就是索引。

InnoDB中的索引方案

上述的目录项还可以优化：

  • 无法用连续地址空间存储
  • 数据量大时，内存占用大
  • 插入、删除时改动量大

因此，可以将目录项也做成单向链表，称为目录页。这样的数据，也可以通过Compact行格式存储，record_type为1。

迭代一次：目录项记录的页

image-20221114151023560

通过页30存储目录项记录。目录项记录和普通的用户记录不同点：

  • 目录项记录的record_type值是1，而普通用户记录的record_type值是0
  • 目录项记录只有主键值和页的编号两个列，普通用户记录的列是用户自定义的，可能包含很多列，另外还有InnoDB自己添加的隐藏列。
  • 记录头信息里还有一个叫min_rec_mask的属性，只有在存储目录项记录的页中的主键值最小的目录项记录的min_rec_mask值为1，其他别的记录的min_rec_mask值都是0

相同点：

  • 使用一样的数据页
  • 都会为主键值生成Page Directory（页目录），从而在按照主键值进行查找时可以使用二分法来加快查询速度。

再次查找主键为20的记录，可以分成两步：

  1. 先到存储目录项记录的页，也就是页30中通过二分法快速定位到对应目录项，定位到页29
  2. 到存储用户记录的页2通过二分法快速定位到主键为20的记录

迭代2次：多个目录项记录的页

由于一个页只有16KB大小，存放的目录项记录也是有限的，如果表中数据很多，以至于一个数据页不足以存放所有的目录项记录，此时，就需要分配一个新的目录项记录的页。

假设一个存储目录项记录的页最多只能存储4条目录项记录

image-20221114153018184

新增加的目录项记录的页之间，使用双链表进行关联。

此时查询操作则需要先确定目录项记录页，判断主键值是否在页30的最大值和最小值之间，如果不在，则去下一页中查询。查询到所在数据页之后，再到存储页中查询

迭代3次：目录项记录页的目录页

由于页不连续，因此在目录项记录页定位数据时，也需要依次遍历，无法快速定位，这时就需要为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据。

ps：实际B+树还会在非聚簇索引下，在目录项记录页中存储主键。

image-20221114153827053

如图，生成一个存储更高级目录项的页33，这个页中的两条记录分别代表页30和页32，如果记录的值在[1,320)之间，则到页30中查找更详细的目录项记录，如果主键不小于320，则在页32中查找。

随着这个记录的增加，目录层级也会继续增加，如果简化一下，则为下图：

image-20221114154223489

这个数据结构，就是**B+**树。

B+Tree

不存是存放用户记录的数据页，还是存放目录项记录的数据页，这些数据页都称为节点。

实际记录用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶子节点，其余用来存放目录项的节点称为非叶子节点或者内节点，B+树最上边的那个节点称为根节点。

一个B+树的节点可以分成好多层，最下面的称为0层，之后依次往上加。如果每层的一个节点可以存储的数据为n，则m层的B+树可以存储的数据条目则是n^m。一般情况下，根据数据量和查询次数，不会超过4层，层数越少，查询效率越高。

索引

索引按照物理实现方式，可以分为两种，聚簇（聚集）索引和非聚簇（非聚集）索引。非聚簇索引也成为二级索引或者辅助索引。

术语“聚簇”表示数据行和相邻的键值聚簇地存储在一起

聚簇索引

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式（所有的用户记录都存储在了叶子节点），也就是索引即数据，数据即索引。（InnoDB的数据存储方式时将数据和索引都存放在.ibd文件中。）

特定：

  1. 使用记录主键值的大小进行记录和页的排序，包括三个方面的含义：

    • 页内的记录是按照主键的大小顺序排成一个单向链表
    • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表
    • 存放目录项记录的页分为不同的层次，同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表

  2. B+树的叶子节点存储的是完整的用户记录。

具有这两种特性的B+树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引不需要显式使用INDEX语句创建，InnoDB存储引擎会自动创建聚簇索引。

优点：

  • 数据访问更快，将索引和聚簇索引都存放在同一个B+树上，从聚簇索引中获取数据比非聚簇索引更快。
  • 聚簇索引对于主键的排序查找和范围查找速度非常快
  • 按照聚簇索引排列顺序，查询显式一定范围数据时，由于数据紧密相连，数据库不用从多个数据块（也就是大量的页）中提取数据，索引节省了大量的IO操作。

缺点：

  • 插入速度严重依赖插入顺序，按照主键的顺序插入是最快的，否则会出现页分裂，严重影响性能。因此，对于InnoDB表，一般都会自定义一个自增的ID列为主键。
  • 更新主键的代价很高，因为会导致更新的行移动。因此一般定义InnoDB的主键为不可更新列
  • 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据

限制：

  • 对于MySQL数据库目前只有InnoDB存储引擎支持聚簇索引，MyISAM并不支持聚簇索引。（MyISAM数据、索引、表结构分开存储）
  • 数据物理存储排序方式只有一种，所以每个MySQL的表只能有一个聚簇索引，一般情况下就是该表的主键
  • 如果没有定义主键，InnoDB会选择非空的唯一索引替代，如果没有这样的索引，InnoDB会隐式的定义一个主键来作为聚簇索引
  • 为了充分利用聚簇索引的聚簇特性，InnoDB表的主键列尽量选用有序的顺序id，而不建议用无序的id，比如UUID、MD5、HASH、字符串列作为主键无法保证数据的顺序增长。

二级索引

也称为辅助索引、非聚簇索引

聚簇索引只能在搜索条件是主键值时才能发挥作用，因为B+树中的数据都是按照主键进行排序的。

如果通过其他列作为搜索条件，就需多建几颗B+树，不同的B+树中的数据采用不同的排序规则。比如用c2列的大小作为数据页、页中记录的排序规则，再建一颗B+树。

image-20221114170427069

与聚簇索引的不同点

  • 使用记录c2列的大小进行记录和页的排序：
    • 页内记录按照c2列的大小顺序排列成一个单向链表
    • 各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表
    • 存放目录项记录的页分为不同的层次，同层页根据页中目录项记录的c2列大小顺序排成一个双向链表
  • B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值
  • 目录项记录中不再是主键+页号的搭配，变成c2列+页号的搭配。

如果通过c2列的值查找某些记录，可以通过新的B+树，通过查找c2列的值查找目录项记录页，通过目录项记录的页查找叶子节点，通过叶子节点中的记录获取对应主键，再通过主键在聚簇索引中查找数据。

非聚簇索引没有唯一和非空约束，因此通过上一个最小值<= 查询值 <= 下一个最小值来查询，而且查询结果可能会有多个。

通过非聚簇索引查询到主键，再通过主键查询聚簇索引的过程，称为回表。也就是根据c2列的值查询一条完整的用户记录需要使用到2课B+树。

造成回表的原因：

如果将数据都放到二级索引中，会造成数据冗余，很占据存储空间。

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

image-20221114171718620

聚簇索引和非聚簇小结

  1. 聚簇索引的叶子节点存储的是数据记录，非聚簇索引叶子节点存储的是数据位置，非聚簇索引不会影响数据表的物理存储顺序
  2. 一个表只能有一个聚簇索引，因为只能有一种排序存储方式，但可以有多个非聚簇索引，也就是多个索引目录提供数据检索
  3. 使用聚簇索引的时候，数据的查询效率高，但如果对数据进行插入、删除、更新等操作，效率会比非聚簇索引低。（非聚簇索引在这个过程中可能不会发生变化）

联合索引

可以同时给多个列的大小作为排序规则，也就是同时为多个列建立索引，比如说B+树按照c2和c3列的大小进行排序，这个包含两层含义：

  • 先把记录和页按照c2列进行排序
  • 在记录的c2列相同的情况下，采用c3列进行排序

image-20221114172335350

如图：

  • 每条目录项记录都由c2,c3,页号这三个部分组成，各条记录先按照c2列的值进行排序，相同时，则按照c3列的值进行排序
  • B+树的叶子节点记录c2,c3,主键c1组成

以c2和c3列的大小为排序规则建立的B+树称为联合索引，本质上是一个二级索引，与分别创建c2和c3索引意义不同

  • 建立联合索引只会建1棵B+树（其实实际上可以理解为创建了一个c2索引和一个c2,c3索引）
  • 为c2和c3列分别建立索引会分别以c2和c3列排序规则创建2棵B+树

InnoDB的B+树索引注意事项

根页面无法变动

创建B+树的过程：

  • 为表创建B+树索引（聚簇索引不是人为创建的，默认就有）时，都会为这个索引创建一个根节点页面。最开始表中没有数据时，每个B+树索引对应的根节点中既没有用户记录，也没有目录项记录。
  • 插入用户记录时，先把用户记录存储到这个根节点中
  • 当根节点中的可用空间用完时，继续插入记录，此时会将根节点中的所有记录复制到一个新的页。此时插入的记录根据键值（聚簇索引则为主键，非聚簇索引则为对应列值）大小分配到新的页中，而根节点升级为存储目录项记录的页。

也就是说，B+树创建时，就不会移动，根节点的页号会被记录到某个地方，然后InnoDB引擎使用到这个索引的时候，都会从固定的地方取出根节点的页号，从而访问这个索引。

内节点中目录项记录的唯一性

内节点（非叶子节点）中的目录项记录要唯一（主要是针对非聚簇索引）。

为了在非聚簇索引的目录项数据一致时，插入新的数据，并且确定新数据插入所在页（例如当有两个页都存在同样的二级索引），此时需要能够区分该页，因此，内节点上还需要记录一个唯一字段，也就是主键。

非聚簇索引的内节点目录项记录的实际内容：

  • 索引列的值
  • 主键值
  • 页号

image-20221114200214549

一个页面最少存储2条记录

为了实现快速查找，不会出现目录层级查找很多之后，存放真实数据的目录中只存放一条数据，因此InnoDB的一个数据页至少可以存放两条数据。

B+树查找行记录，最多只需要1~3次磁盘I/O

页的大小为16KB，主键一般是INT，一个页存储主键和指针（都按照8Byte计算），那么可以存储的键值个数为16KB/8Byte = 1000 个，一个三层B+树可以存储10^9的数据，而且通常填不满。B+tree一般高度是2~4，而且根节点不会变动，一般会常驻内存，因此通常需要1~3次磁盘I/O操作。

MyISAM索引原理

B树索引适用存储引擎：

索引/存储引擎 MyISAM InnoDB Memory
B-Tree索引 支持 支持 支持

即使多个存储引擎支持同一种类型的索引，但是他们的原理不同。InnoDB和MyISAM默认的索引是Btree索引；而Memory默认索引是Hash索引。

MyISAM引擎使用B+Tree作为索引结构，叶子节点的data域存放的是数据记录的地址。

MyISAM索引的原理

MyISAM表结构

1
2
3
-rw-r-----  1 mysql mysql 2.4K Nov 11 14:26 myisam1_539.sdi        // 元数据，列的信息：列名，属性，约束等	
-rw-r-----  1 mysql mysql 1.0K Nov 11 14:26 myisam1.MYI                // 索引
-rw-r-----  1 mysql mysql    0 Nov 11 14:26 myisam1.MYD                // 数据

MyISAM的索引方案虽然也是树形结构，但是却是将数据和索引分开存储。

  • 将表中的记录按照记录的插入顺序单独存储在一个文件中，称之为数据文件。这个文件不划分为若干个数据页，有多少记录就往这个文件中塞多少记录就成了。由于在插入数据的时候并没有刻意按照主键大小排序，所以不能在这些数据上使用二分查找法。
  • MyISAM存储引擎会把索引信息另外存储到一个称为索引文件的另外一个文件中。MyISAM会单独为表的主键创建一个索引，只是索引的叶子节点中存储的不是完整的用户记录，而是主键值+数据记录地址的组合。

image-20221114201552971

在MyISAM中，主键索引和二级索引在结构上没有任何区别，只是主键索引要求key是唯一的，而二级索引的key可以重复。

MyISAM中索引检索的算法为：

首先按照B+Tree搜索算法搜索索引，如果指定的key存在，则取出其data域值，然后以data域的值为地址，读取相应数据记录。

MyISAM与InnoDB对比

MyISAM的索引方式都是非聚簇的，InnoDB包含1个聚簇索引。

  1. InnoDB存储引擎中，只需要对主键值对聚簇索引进行一次查找就能找到对应的记录，在MyISAM中却需要一次回表操作，也就是MyISAM中建立的索引相当于都是二级索引

  2. InnoDB的数据文件本身就是索引文件，MyISAM索引文件和数据文件分离，索引文件仅保存数据记录的地址

  3. InnoDB的非聚簇索引data域存储相应记录主键的值，MyISAM索引记录的是地址。InnoDB的所有非聚簇索引都是引用主键作为data域

  4. MyISAM的回表操作是十分快速的，因为拿着地址偏移量直接到文件中读取数据。InnoDB则是通过获取主键之后再去聚簇索引中找记录，相比而言，速度比不上直接用地址访问。

  5. InnoDB要求表必须有主键（MyISAM可以没有），如果没有显示指定，则MySQL会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在，则MySQL会自动为InnoDB生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

在InnoDB中，不建议使用过场的字段作为主键，因为会浪费二级索引的存储空间。

同时主键的字段不要使用非单调字段，因为新插入数据时可能导致页分裂。使用自增字段作为主键是一个很好的选择。

索引的代价

创建索引在时间和空间上都会有消耗：

  • 空间上的代价

    每建立一个索引都需要建立一个B+树，每一颗B+树的每一个节点都是一个数据页，一个页默认会占用16KB的存储空间，B+树越大越多，占用的存储空间就越大

  • 时间上的代价

    每次对表增、删、改时，都需要修改B+树索引。不论是叶子节点中的记录还是内节点中的记录，这些节点内部的记录是单向链表，增、删、改操作可能会对节点和记录的排序造成破坏。因此存储引擎需要额外的时间进行一些记录位移，页面分裂，页面回收等操作来维护好节点和记录的排序。索引越多，每个索引对应对应的B+树都要进行相应的维护。

索引建立的越多，也就越占用存储空间，增删改性能也就越差，因此创建索引需要谨慎。

MySQL数据结构选择的合理性

如果让索引的数据结构尽量减少磁盘的IO操作，消耗的时间也就越小，也就是说，磁盘的I/O操作次数对索引的使用效率至关重要。

查找都是索引操作，当数据量大的时候，索引大小可能达到G单位级。为了减少索引在内存中的占用，数据库索引是存储在外部磁盘上的。因此利用索引查询的时候，只能逐一加载，也就是MySQL衡量查询效率的标准就是磁盘I/O次数。

全表遍历

没有索引，全量遍历，效率低下

Hash结构

Hash本身是一个函数，又被成为散列函数，可以帮助大幅提升检索数据的效率。

Hash算法是通过某种确定性的算法，例如MD5，SHA1，SHA2，SHA3，将输入转变为输出。相同的输入永远可以得到相同的输出。

加速查找速度的数据结构，常见的有两类：

  1. 树，例如平衡二叉搜索树，查询、插入、修改、删除的平均时间复杂度都是o(log2N)

  2. 哈希，例如HashMap，查询、插入、修改、删除的平均时间复杂度都是o(1)

image-20221114204039108

采用Hash进行检索，效率很高，一次检索就可以得到数据。相比B+树需要自顶向下依次查找，多次访问才能找到数据，中间需要经过多次I/O操作，效率上来说，Hash比B+树快。

但是Hash索引不适合作为MySQL索引结构，原因如下：

  1. Hash索引仅能满足=和IN，如果进行范围查询，Hash索引的时间复杂度会退化为o(n)，而树型的有序特性，依然能够保持o(log2N)的效率。
  2. Hash索引，数据存储没有顺序，在ORDER BY的情况下，还需要重新排序
  3. 对于联合索引的情况，Hash值是将联合索引键合并后一起计算的，无法单独的一个键或者几个索引进行查询
  4. 等于等值查询来说，Hash效率通常更高，但是在索引列的重复值如果很多，效率也会低很多（hash取模之后，还是单向链表存储）。

Hash索引适用存储引擎：

索引/存储引擎 MyISAM InnoDB Memory
HASH索引 不支持 不支持 支持

Hash索引适用性：

在键值型数据库中，更有优势，例如Redis存储的核心就是Hash表。

MySQL中Memory存储引擎支持Hash存储，在查询临时表时，就可以选择Memory引擎，将某个字段设置为Hash索引，当字段重复度低，并且需要经常进行等值查询时，采用Hash索引是个不错的选择。

另外，InnoDB本身不支持Hash索引，但是提供自适应Hash索引。如果某个数据经常被访问，当满足一定条件时，就会将这个数据页的地址存放到Hash表中。下次查询的时候，就可以直接找到这个页面的位置，这样让B+树也具备Hash索引的优点。

image-20221114211020179

自适应Hash索引的目的是方便根据SQL的查询条件加速定位到叶子节点，特别是B+树比较深的时候，通过自适应Hash索引可以明显提高数据的检索效率。

1
2
-- 查看是否开启自适应Hash，默认打开
SHOW VARIABLES LIKE '%innodb_adaptive_hash_index';

二叉搜索树

二叉搜索树的特点

  • 一个节点只能有两个子节点，也就是一个节点度不能超过2
  • 左子节点<本节点；右子节点>=本节点

查找规则

  1. 如果key大于根节点，则在右子树查找
  2. 如果key小于根节点，则在左子树查找
  3. 如果等于根节点，返回这个节点

如果数据是顺序的，而且数据非常多，二叉树可能就会退化成一条链表，此时时间复杂度就从o(log2N)降低到o(n)。

image-20221114211901755

为了提高查询效率，就需要减少磁盘IO数，可以降低树的高度，树的每层分叉越多越好。

AVL树

为了解决上述退化成链表的问题，提出了平衡二叉搜索树（Balanced Binary Tree），又称为AVL树（有别于AVL算法），它在二叉搜索树的基础上增加了约束。

它是一颗空树，或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。

image-20221114211940150

此时，时间复杂度就是o(log2N)，需要通过5次I/O操作。虽然平衡二叉树效率高，但是树深度也高，因此，效率也不会很高。

此时，可以将二叉树改成M叉树（M>2），例如三叉树

image-20221114212206401

高度降低，I/O就减少。这样引申出来，将树的高度降低下来，就是B-Tree。

B-Tree

B树英文是Balance-Tree，也就是多路平衡查找树，简写B-Tree（横杠代表两个单词连起来，不是减号），它的高度远远小于平衡二叉树。

image-20221114212404226

B树每一个节点最多可以包括M个子节点，M称为B树的阶。每个磁盘块中包括了关键字和子节点的指针。

B树特点：

  1. B树在插入和删除节点时，如果导致树不平衡，就通过自动调整节点的位置来保持树的自平衡
  2. 关键字集合分布在整课树中，即叶子节点和非叶子节点都存放数据，搜索有可能在非叶子节点结束
  3. 其搜索性能等价于在关键字全集内左一次二分查找

image-20221114212821219

B+Tree

B+树也是一种多路搜索树，基于B树做出了改进，称为B+树（加，plus，加强版），主流的DBMS都支持B+树的索引方式，例如MySQL。先比B-Tree，**B+Tree更适合文件索引系统**。

B+树和B树的差异：

  1. B+树中，有K个孩子的节点就有k个关键字，也就是孩子数量=关键字数，而B树中，孩子数=关键字+1
  2. B+树中，非叶子结点的关键字也会同时存在子节点中，而且在子节点中所有关键字最大（或最小）
  3. B+树中，非叶子结点仅用于索引，不保存数据记录，跟记录有关的都记录在叶子节点中，而B树，非叶子节点既保存索引，也保存数据记录
  4. B+树中，所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而叶子节点本身按照关键字的大小从小到大顺序链接
  5. B+树中，节点和节点之间，通过双向指针链接，能够加快检索效率，而B树中没有

相比B树，B+树的中间节点不直接存储数据，好处是

  • B+树查询效率更稳定
  • B+树查询效率更高
  • 范围查询上，B+树的效率页比B树高

B树和B+树都可以作为索引的数据结构，在MySQL中采用的是B+树。但B树和B+树各有应用场景。

InnoDB数据存储结构

InnoDB数据存储结构，也就是页。

索引结构提供高效的索引方式，不过索引信息以及数据记录都是保存在文件上的，确切说是存储在页结构中。另一方面，索引是在存储引擎中实现的，MySQL服务器上的存储引擎负责对表中数据的读取和写入工作，不同的存储引擎中存放的格式不同，这里主要学习适用性最广的InnoDB存储引擎。

磁盘与内存交互的基本单位：页

InnoDB将数据划分为若干个页，InnoDB中也的大小默认是16KB。

以页作为磁盘和内存之间交互的基本单位，也就是一次最少从磁盘读取16KB的内容到内存，一次最少把内存中的16KB内容刷新到磁盘中。

数据库中，不论读一行还是读多行，都是将这些行所在的页进行加载。数据库管理存储空间的基本单位是页（Page），数据库IO操作的最小单位是页。一个页中可以存储多个行记录。

记录时按照行存储，但是读取不以行为单位。

image-20221114215355682

页结构概述

页可以不在物理结构上相连，只要通过双向链表相关联即可。每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边的记录生成一个页目录，在通过主键查找某条记录的时候，可以在页目录中使用二分法快速定位到对应的槽，然后再便利该槽对应分组中的记录即可快速找到指定的记录。

页的大小

不同的DBMS的页的大小不同，MySQL中InnoDB存储引擎，默认页大小是16KB

1
2
3
4
5
6
7
8
-- 获取页大小
SHOW VARIABLES LIKE '%innodb_page_size%';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.01 sec)

页的上层结构

在数据库中，还存在区，段和表空间的概念。行、也、区、段、表空间如下

image-20221114215847632

行：是数据条目一行一行存储

页：一个页中保存多行数据

区 Extent：InnoDB存储引擎中，一个区分配64个连续的页，一个区大小是1MB

段 Segment：由一个或多个区组成，区在文件系统时一个连续分配的空间（InnoDB中是连续的64个页），不过在段中不要求区与区之间相邻。段是数据库中的分配单位，不同类型数据库对象以不同的段形式存在。当创建数据表、索引时，会相应创建对应的段，比如创建一张表时会创建一个表段，创建一个索引时会创建一个索引段。

表空间 Tablespace：是一个逻辑容器，表空间存储的对象是段，在一个表空间中可以有一个或多个段，但是一个短只能属于一个表空间。数据库由一个或多个表空间组成，表空间从管理上可以划分为系统表空间ibdata1、用户表空间、撤销表空间、临时表空间等。

页的内部结构

页按照类型划分，常见有数据页，系统页，Undo页和事务数据页等，数据页例如保存B+树节点的页，最常使用。

数据页的16KB大小的存储空间被划分为七个部分：

image-20221114220646813

这7个部分作用如下

image-20221114220705153

可以将7个结构分成3个部分。

File Header和File Trailer

首先是文件通用部分，文件头和文件尾

文件头：描述一些针对各种页的描述信息，页的编号，页的类型，上一页，下一页，当前页的校验和（头尾都有校验和，如果头尾校验和相同，则代表数据完全同步成功，校验方式采用Hash算法），页面被最后修改时对应的日志序列位置（头尾都有日志序列位置，保证数据完整性和一致性）。

Free Space、User Records、Infimum+Supremum

主要是用于存储记录，Free Space（空闲空间）、User Records（用户记录）、Infimum+Supremum（最大最小记录）。

User Records 用户记录就是记录的数据。

image-20221114224323600

Page Header、Page Directory

Page Header（页面头部）、Page Directory（页目录）。

页中数据进行分组，除了第一组，其余组的记录数尽量平分，页目录用来存储每组最后一条记录的地址偏移量，按照先后顺序存储起来，每组的偏移量也称为槽（slot），相当于指针指向每组中的最后一个数据。页目录存储的就是槽的信息。

页面头部存储页目录中的槽数量，还为使用的最小地址，本也中记录的数量（包含最大、最小和删除的），第一个已经标记为删除的记录地址，已删除记录占用的字节数，最后插入记录的位置，记录插入的方向，一个方向连续插入的记录数量，该页中记录的数量（不包含最大、最小和删除的），修改当前页的最大事务id，当前页在B+树中所处的层级，索引ID，B+树叶子段的头部信息，B+树非叶子节点的头部信息，

InnoDB行格式（记录格式）

数据以行为单位插入表，在磁盘上的存放方式也被称为行格式或者记录格式。InnoDB存储引擎设计了4中不同类型的行格式：Compact，Redundant，Dynamic，Compressed

查看默认行格式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
SELECT @@innodb_default_row_format;
+-----------------------------+
| @@innodb_default_row_format |
+-----------------------------+
| dynamic                     | -- 动态
+-----------------------------+
1 row in set (0.00 sec)
-- 查看表的具体行格式
SHOW TABLE STATUS LIKE 'employee'\G
*************************** 1. row ***************************
           Name: employee
         Engine: InnoDB
        Version: 10
     Row_format: Dynamic
           Rows: 18
 Avg_row_length: 910
    Data_length: 16384
Max_data_length: 0
   Index_length: 49152
      Data_free: 0
 Auto_increment: 20
    Create_time: 2022-10-27 09:10:10
    Update_time: NULL
     Check_time: NULL
      Collation: utf8mb4_0900_ai_ci
       Checksum: NULL
 Create_options:
        Comment:
1 row in set (0.03 sec)

Compact

MySQL 5.1版本的默认行格式。一条完整的记录可以被分为记录的额外信息和记录的真实数据两大部分。

image-20221115202419761

边长字段长度列表：例如varchar这样的变长字段，这个字段记录所有变长字段的真实数据占用的字节长度，形成一个边长字段长度列表

NULL值列表：将NULL值的列统一管理起来，目的是为了记录NULL列之后的偏移量

记录头信息：就是上面的User Records信息，主要用来记录该条信息的一系列状态

记录的真实数据：除了真实的数据之外，还有三个隐藏列：row_id(行ID)，transaction_id(事务ID)，roll_pointer(回滚指针)。

  • row_id：行ID，唯一标识一条记录，如果表没有手动指定主键，则会选取一个Unique键作为主键，如果连Unique键都没有定义的话，则会为表默认添加一个名为row_id的隐藏列作为主键。
  • transaction_id，roll_pointer：事务ID和回滚指针，主要用于事务相关操作。

Dynamic和Compressed行格式

这两个行格式差别不大，而且根Compact格式也差别不大。

InnoDB存储引擎可以将一条记录中的某些数据存储在真正的数据页面之外。

1
2
3
4
5
6
7
8
9
-- 创建 65535长度的VARCHAR会报错
-- > 1118 - Row size too large. The maximum row size for the used table type, not counting BLOBs, is 65535. This includes storage overhead, check the manual. You have to change some columns to TEXT or BLOBs
CREATE TABLE varchar_size_demo(
c VARCHAR(65535)
) CHARSET = ASCII row_format=compact; 

CREATE TABLE varchar_size_demo(
c VARCHAR(65532) -- 实际上最大长度是65532，原因是要加上2个字节长度的变长字段的长度+ 1个字节的NULL值标识 
) CHARSET=ASCII ROW_FORMAT=COMPACT;

而一个页16KB，存储16384个字节，可能出现一个字段的长度就超过1页，这种现象就是行溢出。

在Compact和Redundant行格式中，会将部分数据存储在页中，剩余数据分散存储在几个其他的页中，而且记录其他的页的地址。

Dynamic和Compressed在处理行溢出的情况下，处理过程不一样，他们是将存放在BLOB中的数据采用完全的行溢出方式，实际的数据都存放在Off Page（溢出页）中。而且Compressed在存储行数据时，会以zlib的算法进行压缩，因此对于BLOB、TEXT、VARCHAR这类大长度类型的数据能够进行非常有效的存储。

image-20221115204751646

Redundant

是MySQL 5.0版本之前InnoDB的行记录存储方式。

与Compact区别主要是记录的额外信息有区别。

image-20221115204850330

区、段与碎片区

区

B+树的每一层中的页都会形成一个双向链表，如果以页来分类存储空间，双向链表之间的物理距离可能非常远，而顺序I/O可以加速页和页之间的寻址和访问，因此引入区的概念，一个区的可以存储64个页，也就是64 * 16KB = 1MB，当数据量大时，为索引分配空间就可以以区为单位，消除随机IO，提高性能。

区可以分为4中类型：

  • 空闲的区
  • 有剩余空间的碎片区
  • 没有剩余空间的碎片区
  • 附属于某个段的区

段

InnoDB对B+树的叶子节点和非叶子节点是会区别对待的，存放叶子节点的区的集合就算是一个段，存放非叶子区的集合也是一个段。

除了存放叶子节点的段称为数据段，存放非叶子节点的段称为索引段，还有存储一些特殊数据定义的回滚段。

段其实不是对应表空间中某一个连续的物理区域，而是一个逻辑的概念，由若干个零散的页面以及一些完整的区组成。

碎片区

默认情况下，只存储了几条记录的小表，不一定会存储2M（叶子节点的区和非叶子节点的区，占用2M）的存储空间，针对这种数据量较小的表浪费空间的情况，InnoDB提出碎片区的概念。一个碎片区中，不是所有页都是存储同一个段的数据，而是可以用于不同的目的，比如有些页存放于段A，有些页存放于段B，有些页哪个段都不属于。碎片去直属于表空间，并不属于任何一个段。

表空间

表空间可以看做是InnoDB存储引擎逻辑结构的最高层，所有的数据都存放于表空间

  • 系统表空间：存放的元数据，例如所有表、列、索引、索引对应的列、外键、外键对应的列、表空间等的信息
  • 独立表空间：每一个表有一个独立的表空间，由段、区、页组成。
  • 撤销表空间：
  • 临时表空间：

查看表空间类型

1
2
3
4
5
6
7
SHOW VARIABLES LIKE '%innodb_file_per_table%';
+-----------------------+-------+
| Variable_name         | Value |
+-----------------------+-------+
| innodb_file_per_table | ON    |  -- ON代表使用独立表空间
+-----------------------+-------+
1 row in set (0.02 sec)

用户不能直接访问InnoDB的系统表，但可以通过information_schema表获取一些系统信息

1
2
use information_schema;
show tables;

推荐阅读：

MySQL系列（4）— InnoDB数据页结构