关系型数据库知识

整理一下关系型数据库的知识~

关系数据库（Relational database），是建立在 关系模型 基础上的数据库，借助于集合代数等数学概念和方法来处理数据库中的数据。现实世界中的各种实体以及实体之间的各种联系均用关系模型来表示。关系模型是由埃德加·科德于1970年首先提出的，并配合“科德十二定律”。现如今虽然对此模型有一些批评意见，但它还是数据存储的传统标准。标准数据查询语言SQL就是一种基于关系数据库的语言，这种语言执行对关系数据库中数据的检索和操作。关系模型由关系数据结构、关系操作集合、关系完整性约束三部分组成。常见的关系型数据库：MySQL、PostgreSQL、Oracle、Microsoft SQL Server、SQLite、MariaDB。

Mysql 架构

连接层

连接层接收请求，分配一个线程来处理连接，并进行身份验证。

客户端连接的建立与处理：当客户端发起连接请求时，MySQL会创建一个专用的线程（以操作系统级别的线程实现）来为该客户端服务。这些服务线程使用线程池里的长连接服务多个用户请求，减少了线程切换的开销。
安全认证：当客户端连接到MySQL服务器时，服务器首先需要验证客户端的身份。
连接资源管理：MySQL支持可配置的最大连接数。当到达最大连接数时，新的连接请求会被拒绝。符合条件的客户端可以设置连接超时时间、客户端闲置关闭时间等参数。同时，可以通过"mysql.user"表配置特定用户对于数据库的操作权限。
线程管理：MySQL会自动创建和管理连接线程，其中包括以线程数作为上限的线程池。线程池的目的是复用连接线程，避免了线程切换和创建的开销。此外，MySQL使用异步I/O机制和协程，尽可能提高了并发和吞吐量。

服务层

服务层是MySQL中的核心组件，负责提供各种数据库操作所需的基本功能。

SQL语法处理

从客户端接收来自连接层的SQL查询请求，并进行初始分析、解析和预处理。
- SQL解析器：服务层的SQL解析器主要进行语法解析。解析器会根据MySQL词法分析器和语法分析器的解析规则，将查询语句解析成一个字符串表示的树状结构，用于存储语法单位（词素）及它们之间的关系。
- SQL预处理：在构建完成解析树后，预处理模块对解析树进行优化和处理。这包括检查权限、完整性约束、函数调用和数据类型等。在预处理阶段，还可能对查询进行改写，例如将"UNION"操作转换为"JOIN"操作，或者将子查询转换为连接操作。
事务管理

确保在执行一系列操作时满足 ACID 原则。
- 事务隔离：定义了事务间数据访问的隔离程度，包括：Read Uncommitted、Read Committed、Repeatable Read(Default)、SERIALIZABLE。
- 锁管理：在事务过程中，可能需要对数据加锁，以确保数据的一致性。MySQL支持的锁类型包括共享锁、排它锁、意向锁、行锁、表锁等。
- Undo日志：通过Undo日志实现了事务回滚操作，当事务执行中途出现异常或用户发出回滚请求时，可以通过Undo日志回滚数据到事务开始前的状态。
- Redo日志：为了保证事务的持久性，在事务执行过程中，修改的数据首先写入到Redo日志中，再更新到磁盘文件上。在系统恢复过程中，可以通过Redo日志进行数据恢复。
缓存管理

MySQL优化器使用缓存来提高查询速度。
- 查询缓存：MySQL会将查询语句和其结果缓存在内存中。当收到一个相同的查询请求时，先检查缓存中是否有匹配的结果。如果有匹配结果，则直接返回，并跳过剩余的处理步骤。如果没有匹配，将继续执行下一个步骤。
- 表缓存：用于存储表的元数据，如表的结构定义。当查询需要表信息时，优先从表缓存中获取，避免磁盘操作。
- 线程缓存：用于复用服务器的连接线程。当一个连接关闭后，它的线程会被放回线程缓存池中，供新的连接使用。线程池意味着减少了创建和销毁线程的开销。
- 缓冲池：主要用于InnoDB存储引擎，缓冲池管理缓存的数据页，包括数据和索引。当需要访问这些页时，可以直接从缓冲池读取，提高访问速度。

引擎层

引擎层负责存储数据和执行SQL语句。通过标准API与服务层交互，实现数据的存储和查询。

InnoDB

默认存储引擎，提供了事务支持、行级锁定、外键约束等功能，主要用于高并发、高可靠性的OLTP场景。
MyISAM

通常用于只读数据表，适用于简单查询和全文索引。其不支持事务、行级锁等功能，适用于OLAP场景。
Memory

支持哈希和B树索引，它将数据存储在内存中，易受到系统断电或宕机等影响，具有较高的写性能但不适用于大规模数据分布。
其他

Archive、NDB Cluster 等其他存储引擎，它们分别适用于存档表、分布式数据库等不同场景。

Mysql 语句执行流程

主要步骤：

语法分析

语法分析器会对SQL语句进行分析，检查其是否符合语法规则。如果SQL语句不符合语法规则，MySQL将会返回一个错误消息。详细的来说又可分为以下几步：

词法分析：主要负责从SQL语句中提取关键字，比如：查询的表，字段名，查询条件等等。词法分析器会将SQL语句分割成一个个的词法单元（token），并为每个token赋予一个类型（type）和值（value）。
语法规则：主要判断SQL语句是否合乎MySQL的语法。语法规则模块会使用yacc工具生成的语法分析器，根据MySQL的语法规则（grammar rule）来检查词法单元是否符合语法要求。
语义分析：主要负责检查SQL语句的语义是否正确，比如：表名和字段名是否存在，数据类型是否匹配，函数是否合法等。语义分析器会根据数据字典（data dictionary）和目录（catalog）来验证SQL语句的有效性。

查询优化

SQL语句在查询优化阶段会经历以下步骤：

查询重写：MySQL会对SQL语句进行一些语法和逻辑上的变换，以便于后续的优化和执行。例如，将子查询转换为连接，将or条件转换为union，将in条件转换为exists等。
查询分解：MySQL会将一条复杂的SQL语句分解为多个简单的子查询，每个子查询可以单独优化和执行。例如，将union查询分解为多个select查询，将关联子查询分解为独立的select查询等。
预处理：MySQL会对SQL语句进行一些基本的检查和处理，例如检查语法错误，解析参数，分配内部资源等。
优化器：根MySQL会根据统计信息和成本模型，为SQL语句选择一个最佳的执行计划。执行计划包括了连接顺序，访问方法，索引选择，排序策略等。

执行SQL语句

执行器会按照执行计划的步骤，逐步执行SQL语句。执行器会根据查询语句，从磁盘读取数据，并将其存储在内存中。然后，执行器会对数据进行排序、分组、聚合等操作，最终生成查询结果。主要步骤如下：

打开表：MySQL会根据执行计划中涉及到的表，打开相应的表文件，并为每个表分配一个表句柄（table handle）。
锁定表：MySQL会根据SQL语句的类型（读或写）和事务的隔离级别，为涉及到的表加上相应的锁（共享锁或排他锁）。锁的作用是保证数据的一致性和并发性。
读取数据：MySQL会根据执行计划中选择的访问方法（全表扫描或索引扫描），从存储引擎中读取数据。
过滤数据：MySQL会根据执行计划中的过滤条件（where，group by，having，order by，limit等），对读取到的数据进行过滤和处理。过滤条件可以减少返回给客户端的数据量，提高查询效率。
返回结果：MySQL会将过滤后的数据返回给客户端，并释放相关的资源（表句柄，锁等）。客户端可以接收到结果集，并进行后续的操作。

可以通过 show profile 查看执行过程。

InnoDB 存储结构

InnoDB 是 MySQL 默认的存储引擎，它提供了事务支持、行级锁、外键约束等功能，适用于高并发、高可靠性的 OLTP 场景。InnoDB的底层结构主要由两部分组成：内存结构和磁盘结构。

内存结构

InnoDB的内存结构主要包括：

缓冲池（Buffer Pool）
更改缓冲区（Change Buffer）
日志缓冲区（Log Buffer）
自适应哈希索引（Adaptive Hash Index）

缓冲池（Buffer Pool）

主要用于缓存表数据和索引数据，加快访问速度。缓冲池是 InnoDB 内存结构中最重要的部分，通常占用宿主机 80% 的内存。缓冲池被分成多个页，每页默认大小为 16KB，每页可以存放多条记录。缓冲池中的页按照 LRU（最近最少使用）算法进行淘汰，同时也被分成两个子链表：New Sublist 和 Old Sublist，分别存放访问频繁和不频繁的页。

New Sublist：占用缓冲池5/8的空间，存放最近被访问过的页。当一个新的页被读入缓冲池时，会被放在New Sublist的最前端。当一个已经存在于缓冲池的页被访问时，如果它在New Sublist中，则不会改变位置；如果它在Old Sublist中，则会被移动到New Sublist的最前端。
Old Sublist：占用缓冲池3/8的空间，存放较久未被访问过的页。当一个已经存在于缓冲池的页被访问时，如果它在Old Sublist中，则会被移动到New Sublist的最前端；如果它在New Sublist中，则不会改变位置。
淘汰策略：当缓冲池已满时，需要淘汰一些页来腾出空间。淘汰策略是从Old Sublist的尾部开始扫描，找到第一个没有被修改过（clean）且没有被锁定（unlocked）的页，并将其淘汰出缓冲池。

更改缓冲区（Change Buffer）

主要用于缓存对非聚集索引的修改操作，减少磁盘I/O。更改缓冲区是缓冲池的一部分，当对非聚集索引进行插入、删除或更新时，不会立即修改磁盘上的索引页，而是先记录在写缓冲中。当缓冲池中的数据页被刷新到磁盘时，会将写缓冲中的修改操作合并到相应的索引页中。

修改缓冲类型：
- Insert Buffer：用于记录对非聚集索引进行插入操作时产生的新条目（entry）。
- Delete Buffer：用用于记录对非聚集索引进行删除操作时需要删除的条目（entry）。
- Update Buffer：用于记录对非聚集索引进行更新操作时需要删除和插入的条目（entry）。
修改缓冲结构：修改缓冲是由多个段（segment）组成的，每个段有一个位图（bitmap），用于标记哪些页有写缓冲条目（entry）。每个段都有一个根页（root page），用于存储修改缓冲条目（entry）。每个根页都有一个B+树结构，用于按照空间ID（space ID）和页号（page number）排序修改缓冲条目（entry）。
写缓冲合并：当缓冲池中的数据页被刷新到磁盘时，会触发修改缓冲的合并操作。合并操作的步骤如下：
- 根据数据页的空间ID（space ID）和页号（page number），在修改缓冲中查找是否有对应的条目（entry）。
- 如果有，就将修改缓冲中的条目（entry）应用到磁盘上的索引页中，完成修改操作。
- 如果没有，就直接刷新数据页到磁盘，不做任何修改操作。
- 将修改缓冲中已经合并的条目（entry）删除，释放空间。

日志缓冲区（Log Buffer）

主要用于缓存 Redo Log，保证事务的持久性。日志缓冲是一个循环使用的内存区域，默认大小为 16MB，可以通过参数innodb_log_buffer_size来调整。当事务提交时，会将日志缓冲中的 Redo Log 刷新到磁盘上的 Redo Log 文件中。日志缓冲中的 Redo Log 也会在以下情况下被刷新：日志缓冲已满、每秒钟一次、每个事务检查点一次。

Redo Log：一种物理日志，记录了对数据页进行的物理修改操作。可以用于恢复事务在崩溃或异常情况下未完成的修改操作，保证数据的完整性和一致性。
Redo Log 格式：由多个固定大小的日志块（log block）组成，每个日志块默认大小为512字节。每个日志块包含以下信息：
- 日志块头（log block header）：占用 12 字节，包含了日志块编号（log block number），校验和（checksum），数据长度（data length）等信息。
- 日志记录（log record）：占用不定长度，包含了对数据页进行的物理修改操作的详细信息。例如，修改了哪个数据页，修改了哪个偏移量，修改前后的值是什么等。
- 日志块尾（log block tail）：占用4字节，包含了日志块编号（log block number）的副本。
Redo Log 文件：磁盘上存储 Redo Log 的文件，通常有两个或多个，以实现循环写入和备份。可以通过参数 innodb_log_files_in_group 来指定数量，通过参数 innodb_log_file_size 来指定大小。Redo Log 文件中有一个特殊的位置叫做检查点（checkpoint），表示到这个位置之前的所有 Redo Log 都已经被应用到数据文件中，可以被覆盖或删除。

自适应哈希索引（Adaptive Hash Index）

主要用于加速等值查询，提高查询效率。自适应哈希索引是InnoDB根据查询频率和模式自动建立的一种哈希索引，可以将某些B+树索引转换为哈希索引，从而减少树的搜索次数。自适应哈希索引是可选的，可以通过参数innodb_adaptive来开启或关闭。

原理：当 InnoDB 发现某个 B+ 树索引被频繁用于等值查询时，就会为该索引建立一个对应的哈希索引。哈希索引是一种基于键值对的索引，可以通过哈希函数快速定位到数据页的位置。哈希索引比 B+ 树索引更简单，更高效，但只能用于等值查询，不能用于范围查询或排序查询。
结构：由多个分区（partition）组成，每个分区有一个哈希表（hash table），用于存储键值对。每个键值对包含以下信息：
- key：由 B+ 树索引的键值和空间ID（space ID）组成。
- value：由数据页的页号（page number）和记录的偏移量（offset）组成。
使用：当 InnoDB 执行一个等值查询时，会先在自适应哈希索引中查找是否有匹配的键值对。如果有，就直接定位到数据页的位置，并获取记录。如果没有，就回退到 B+ 树索引中进行搜索。

磁盘结构

Tablespace 表空间

表空间是InnoDB存储引擎逻辑结构的最高层，所有的数据都存放在表空间中。表空间分类：

系统表空间(System tablespace)：InnoDB 默认表空间，通常存储在ibdata1文件中，也可以分成多个文件。系统表空间包含了 InnoDB的数据字典，双写缓冲区，Change Buffer 和 undo log 等重要信息。系统表空间是共享的，可以存储多个表的数据和索引。系统表空间的大小是不可缩小的，只能通过重建整个数据库来减小。
临时表空间(temporary tablespace)：用于存储临时表的数据和索引，例如在执行复杂查询时产生的中间结果。临时表空间通常存储在ibtmp1文件中，可以配置为自动扩展或固定大小。临时表空间不会持久化到磁盘，每次数据库重启后都会被清空。
常规表空间(general tablespace)：一种共享表空间，可以存储多个表的数据和索引。常规表空间可以在任意位置创建多个文件，文件的扩展方式可以是自动扩展或预分配。常规表空间可以用于跨数据库存储数据，或者将不同类型或大小的表分开存储。
undo 表空间(undo tablespace)：包含 undo log 撤销记录的集合，用于事务回滚和一致性读。undo log 记录了数据页修改前的值，用于恢复未提交或已回滚的事务所做的修改，或者提供给其他事务一个数据修改前的快照。undo 表空间可以有多个文件组成，文件存储在 innodb_undo_directory 指定的目录下，以 undofile 开头命名。
文件每表表空间(file-per-table tablespace)：文件每表表空间是一种独占表空间，含单个 InnoDB 表的数据和索引，并存储在文件系统中自己的数据文件中。文件每表表空间的文件名与表名相同，以.ibd为扩展名，位于数据库目录下。文件每表表空间可以实现单个表的压缩，加密，传输和优化等操作。

Data Dictionary 数据字典

数据字典包含用于跟踪对象，如表、索引、列等元数据的内部系统表。元数据实际上位于 InnoDB 系统表空间中。InnoDB 使用数据字典来管理和访问数据库对象，并检查用户对对象的权限。数据字典在数据库启动时加载到内存中，并在数据库关闭时刷新到磁盘上。

Doublewrite Buffer 双写缓冲区

双写缓冲区位于系统表空间中的存储区域，用于保证数据页在写入磁盘时不会损坏。InnoDB 在 Buffer Pool 中刷新页面时，会将数据页写入Doublewrite Buffer 后才会写入磁盘。如果在写入 OS Cache 或者磁盘 mysql 进程奔溃后， InnoDB 启动崩溃恢复能从 Doublewrite Buffer 找到完整的副本用来恢复。

Redo Log 重做日志

基于磁盘的数据结构，在崩溃恢复期间用于纠正不完整事务写入的数据。MySQL以循环方式写入重做日志文件，默认会产生 ib_logfile0 和 ib_logfile1 两个文件。InnoDB 在提交事务之前刷新事务的 redo log，InnoDB 使用组提交（group commit）技术来提高性能。重做日志记录了数据页的物理修改，而不是逻辑修改，这样可以减少日志的大小和恢复的时间。重做日志可以通过 innodb_log_file_size 和 innodb_log_files_in_group 参数来调整大小和数量。

Change Buffer 修改缓冲区

更改缓冲区是Buffer Pool中的一部分，用于缓存对辅助索引页的修改。当InnoDB需要修改一个辅助索引页时，如果该页在Buffer Pool中，则直接修改；如果该页不在Buffer Pool中，则将修改记录在Change Buffer中，而不是从磁盘读取该页。这样可以减少磁盘I/O操作，提高性能。Change Buffer中的修改会在后台或者检查点时合并到辅助索引页中。Change Buffer的大小可以通过innodb_change_buffer_max_size参数来调整。

InnoDB 磁盘空间管理结构

Tablespace 表空间：InnoDB存储数据和索引的逻辑单位，它由一个或多个文件组成。表空间可以分为系统表空间（System Tablespace），通用表空间（General Tablespace），文件表空间（File-Per-Table Tablespace）和临时表空间（Temporary Tablespace）。
Segment 段：段是表空间中分配和管理空间的单位，它由一个或多个连续或不连续的区（Extent）组成。段可以分为数据段（Data Segment），索引段（Index Segment），回滚段（Rollback Segment），撤销日志段（Undo Log Segment）和系统段（System Segment）。
Extend 区：区是段中分配空间的单位，它由一组连续的页（Page）组成。每个区的大小固定为 1MB，包含 64 个页。
Page 页：页是 InnoDB 在磁盘和内存之间传输数据的基本单位，它由一个固定大小的块（Block）组成。每个页的大小默认为16KB，可以通过参数 innodb_page_size 来调整。页可以分为不同的类型，根据存储的内容而定，比如数据页（Data Page），索引页（Index Page），系统页（System Page），事务系统页（Transaction System Page），撤销日志页（Undo Log Page）等。
Row 行：行是InnoDB存储数据记录的最小单位，它由一个或多个列（Column）组成。每个行的大小不能超过半个页。行可以分为两种格式，根据存储方式而定，比如紧凑格式（Compact Format）和动态格式（Dynamic Format）。

Mysql 的数据结构

数据结构怎么设计由数据的存储方式决定，数据存储方式有两种：内存（小数据量）、磁盘（大数据量），数据量决定基本都是要用磁盘的。磁盘的运转方式：寻址 -> 读盘（io）到内存 -> 寻址 -> 读盘 -> ... -> 寻址 -> 读盘（取到数据），其中读盘是最耗时的（每次读盘会读 16k）。

可以做索引的数据结构：数组、链表、红黑树、B树、B+树。对数据库来说，时间复杂度达到 O(n) 是不能接受的。

数组：增 O(1)、删 O(n)、改 O(1)、查 O(n)

链表：增 O(1)、删 O(n)、改 O(n)、查 O(n)

红黑树：增 O(logn)、删 O(logn)、改 O(logn)、查 O(logn)。红黑树相对来说已经比较好了，但是红黑树高度较高，查找数据时，需要的次数多，即磁盘 io 比较多，会导致效率低。改进点：

常见面试题

in 和 exist 的区别，哪个速度更快？

in 语句只执行一次，确定给定的值是否与子查询或列表中的值相匹配。in 在查询的时候，首先查询子查询的表，然后将内表和外表做一个笛卡尔积，然后按照条件进行筛选。所以相对内表比较小的时候，in 的速度较快。

exist 语句执行n次（外表行数），指定一个子查询，检测行的存在。遍历循环外表，检查外表中的记录有没有和内表的的数据一致的。匹配得上就放入结果集。

in 和 exists 的区别：如果子查询得出的结果集记录较少，主查询中的表较大且又有索引时应该用 in，反之如果外层的主查询记录较少，子查询中的表大，又有索引时使用 exists。其实我们区分 in 和 exists 主要是造成了驱动顺序的改变（这是性能变化的关键），如果是 exists，那么以外层表为驱动表，先被访问，如果是 in，那么先执行子查询，所以我们会以驱动表的快速返回为目标，那么就会考虑到索引及结果集的关系，另外 in 是不对 NULL 进行处理。in 是把外表和内表作 hash 连接，而 exists 是对外表作 loop 循环，每次 loop 循环再对内表进行查询。一直以来认为 exists 比 in 效率高的说法是不准确的。

如果查询语句使用 not in，那么内外表都进行全表扫描，没有用到索引；而 not exists 的子查询依然能用到表上的索引。所以无论那个表大，用 not exists 都比 not in 要快。

目录