• DML（data manipulation language）数据操纵语言：
  SELECT、UPDATE、INSERT、DELETE .etc
• DDL（data definition language）数据库定义语言：
  CREATE、ALTER、DROP .etc
• DCL（Data Control Language）数据库控制语言：
  是用来设置或更改数据库用户或角色权限的语句，包括（grant,deny,revoke等）语句

一、MySQL架构原理

1.1. MySQL体系架构

image.png

MySQL Server架构自顶向下大致可以分网络连接层、服务层、存储引擎层和系统文件层。

一、网络连接层
客户端连接器（Client Connectors）：提供与MySQL服务器建立的支持。目前几乎支持所有主流的服务端编程技术，例如常见的 Java、C、Python、.NET等，它们通过各自API技术与MySQL建立连接。

二、服务层（MySQL Server）
服务层是MySQL Server的核心，主要包含系统管理和控制工具、连接池、SQL接口、解析器、查询优化器和缓存六个部分。

• 连接池（Connection Pool）：负责存储和管理客户端与数据库的连接，一个线程负责管理一个连接。
• 系统管理和控制工具（Management Services & Utilities）：例如备份恢复、安全管理、集群管理等
• SQL接口（SQL Interface）：用于接受客户端发送的各种SQL命令，并且返回用户需要查询的结果。比如DML、DDL、存储过程、视图、触发器等。
• 解析器（Parser）：负责将请求的SQL解析生成一个"解析树"。然后根据一些MySQL规则进一步检查解析树是否合法。
• 查询优化器（Optimizer）：当“解析树”通过解析器语法检查后，将交由优化器将其转化成执行计划，然后与存储引擎交互。

三、存储引擎层（Pluggable Storage Engines）
存储引擎负责MySQL中数据的存储与提取，与底层系统文件进行交互。MySQL存储引擎是插件式的，服务器中的查询执行引擎通过接口与存储引擎进行通信，接口屏蔽了不同存储引擎之间的差异 。现在有很多种存储引擎，各有各的特点，最常见的是MyISAM和InnoDB。

四、系统文件层（File System）
该层负责将数据库的数据和日志存储在文件系统之上，并完成与存储引擎的交互，是文件的物理存储层。主要包含日志文件，数据文件，配置文件，pid 文件，socket 文件等。

• 日志文件
  • 错误日志（Error log）
  • 默认开启，show variables like '%log_error%'
  • 通用查询日志（General query log）
  • 记录一般查询语句，show variables like '%general%';
  • 二进制日志（binary log）
    记录了对MySQL数据库执行的更改操作，并且记录了语句的发生时间、执行时长；但是它不记录select、show等不修改数据库的SQL。主要用于数据库恢复和主从复制。
    show variables like '%log_bin%'; //是否开启
    show variables like '%binlog%'; //参数查看
    show binary logs;//查看日志文件
  • 慢查询日志（Slow query log）
    记录所有执行时间超时的查询SQL，默认是10秒。
    show variables like '%slow_query%'; //是否开启
    show variables like '%long_query_time%'; //时长
• 配置文件
  用于存放MySQL所有的配置信息文件，比如my.cnf、my.ini等。
• 数据文件
  • db.opt 文件：记录这个库的默认使用的字符集和校验规则。
  • frm 文件：存储与表相关的元数据（meta）信息，包括表结构的定义信息等，每一张表都会有一个frm 文件。
  • MYD 文件：MyISAM 存储引擎专用，存放 MyISAM 表的数据（data)，每一张表都会有一个.MYD 文件。
  • MYI 文件：MyISAM 存储引擎专用，存放 MyISAM 表的索引相关信息，每一张 MyISAM 表对应一个 .MYI 文件。
  • ibd文件和 IBDATA 文件：存放 InnoDB 的数据文件（包括索引）。InnoDB 存储引擎有两种
    表空间方式：独享表空间和共享表空间。独享表空间使用 .ibd 文件来存放数据，且每一张
    InnoDB 表对应一个 .ibd 文件。共享表空间使用 .ibdata 文件，所有表共同使用一个（或多
    个，自行配置）.ibdata 文件。
  • ibdata1 文件：系统表空间数据文件，存储表元数据、Undo日志等 。
    ib_logfile0、ib_logfile1 文件：Redo log 日志文件。
• pid 文件
  pid 文件是 mysqld 应用程序在 Unix/Linux 环境下的一个进程文件，和许多其他 Unix/Linux 服务端程序一样，它存放着自己的进程 id。
• socket 文件
  socket 文件也是在 Unix/Linux 环境下才有的，用户在 Unix/Linux 环境下客户端连接可以不通过TCP/IP 网络而直接使用 Unix Socket 来连接 MySQL。

1.2. MySQL运行机制

image.png

1.3. MySQL存储引擎

存储引擎在MySQL的体系架构中位于第三层，负责MySQL中的数据的存储和提取，是与文件打交道的子系统，它是根据MySQL提供的文件访问层抽象接口定制的一种文件访问机制，这种机制就叫作存储引擎。

使用show engines命令，就可以查看当前数据库支持的引擎信息。

• InnoDB：支持事务，具有提交，回滚和崩溃恢复能力，事务安全
• MyISAM：不支持事务和外键，访问速度快
• Memory：利用内存创建表，访问速度非常快，因为数据在内存，而且默认使用Hash索引，但是一旦关闭，数据就会丢失
• Archive：归档类型引擎，仅能支持insert和select语句
• Csv：以CSV文件进行数据存储，由于文件限制，所有列必须强制指定not null，另外CSV引擎也不支持索引和分区，适合做数据交换的中间表
• BlackHole: 黑洞，只进不出，进来消失，所有插入数据都不会保存
• Federated：可以访问远端MySQL数据库中的表。一个本地表，不保存数据，访问远程表内容。
• MRG_MyISAM：一组MyISAM表的组合，这些MyISAM表必须结构相同，Merge表本身没有数据，对Merge操作可以对一组MyISAM表进行操作。

1.3.1. InnoDB和MyISAM对比

InnoDB和MyISAM是使用MySQL时最常用的两种引擎类型，我们重点来看下两者区别。

• 事务和外键
  InnoDB支持事务和外键，具有安全性和完整性，适合大量insert或update操作
  MyISAM不支持事务和外键，它提供高速存储和检索，适合大量的select查询操作
• 锁机制
  InnoDB支持行级锁，锁定指定记录。基于索引来加锁实现。
  MyISAM支持表级锁，锁定整张表。
• 索引结构
  InnoDB使用聚集索引（聚簇索引），索引和记录在一起存储，既缓存索引，也缓存记录。
  MyISAM使用非聚集索引（非聚簇索引），索引和记录分开。
• 并发处理能力
  MyISAM使用表锁，会导致写操作并发率低，读之间并不阻塞，读写阻塞。
  InnoDB读写阻塞可以与隔离级别有关，可以采用多版本并发控制（MVCC）来支持高并发
• 存储文件
  InnoDB表对应两个文件，一个.frm表结构文件，一个.ibd数据文件。InnoDB表最大支持64TB；
  MyISAM表对应三个文件，一个.frm表结构文件，一个MYD表数据文件，一个.MYI索引文件。从MySQL5.0开始默认限制是256TB。

image.png

• 适用场景
  • MyISAM
    不需要事务支持（不支持）
    并发相对较低（锁定机制问题）
    数据修改相对较少，以读为主
    数据一致性要求不高
  • InnoDB
    需要事务支持（具有较好的事务特性）
    行级锁定对高并发有很好的适应能力
    数据更新较为频繁的场景
    数据一致性要求较高
    硬件设备内存较大，可以利用InnoDB较好的缓存能力来提高内存利用率，减少磁盘IO

总结
两种引擎该如何选择？
是否需要事务？有，InnoDB
是否存在并发修改？有，InnoDB
是否追求快速查询，且数据修改少？是，MyISAM
在绝大多数情况下，推荐使用InnoDB

1.3.2. InnoDB存储结构

5.5 版本开始

image.png

5.7 & 8.0

image.png

一、InnoDB内存结构

内存结构主要包括Buffer Pool、Change Buffer、Adaptive Hash Index和Log Buffer四大组件。

• Buffer Pool：缓冲池，简称BP。BP以Page页为单位，默认大小16K，BP的底层采用链表数
  据结构管理Page。在InnoDB访问表记录和索引时会在Page页中缓存，以后使用可以减少磁
  盘IO操作，提升效率。
  • Page管理机制
    Page根据状态可以分为三种类型：
    • free page ： 空闲page，未被使用
    • clean page：被使用page，数据没有被修改过
    • dirty page：脏页，被使用page，数据被修改过，页中数据和磁盘的数据产生了不
      一致
      针对上述三种page类型，InnoDB通过三种链表结构来维护和管理
    • free list ：表示空闲缓冲区，管理free page
    • flush list：表示需要刷新到磁盘的缓冲区，管理dirty page，内部page按修改时间
      排序。脏页即存在于flush链表，也在LRU链表中，但是两种互不影响，LRU链表负
      责管理page的可用性和释放，而flush链表负责管理脏页的刷盘操作。
    • lru list：表示正在使用的缓冲区，管理clean page和dirty page，缓冲区以
      midpoint为基点，前面链表称为new列表区，存放经常访问的数据，占63%；后
      面的链表称为old列表区，存放使用较少数据，占37%。
  • 改进型LRU算法维护
    • 普通LRU：末尾淘汰法，新数据从链表头部加入，释放空间时从末尾淘汰
    • 改性LRU：链表分为new和old两个部分，加入元素时并不是从表头插入，而是从中间
      midpoint位置插入，如果数据很快被访问，那么page就会向new列表头部移动，如果
      数据没有被访问，会逐步向old尾部移动，等待淘汰。
      每当有新的page数据读取到buffer pool时，InnoDb引擎会判断是否有空闲页，是否足
      够，如果有就将free page从free list列表删除，放入到LRU列表中。没有空闲页，就会
      根据LRU算法淘汰LRU链表默认的页，将内存空间释放分配给新的页。
  • Buffer Pool配置参数
    show variables like '%innodb_page_size%'; //查看page页大小
    show variables like '%innodb_old%'; //查看lru list中old列表参数
    show variables like '%innodb_buffer%'; //查看buffer pool参数
    建议：将innodb_buffer_pool_size设置为总内存大小的60%-80%，
    innodb_buffer_pool_instances可以设置为多个，这样可以避免缓存争夺。
• Change Buffer：写缓冲区，简称CB。在进行DML操作时，如果BP没有其相应的Page数据，并不会立刻将磁盘页加载到缓冲池，而是在CB记录缓冲变更，等未来数据被读取时，再将数据合并恢复到BP中。
  ChangeBuffer占用BufferPool空间，默认占25%，最大允许占50%，可以根据读写业务量来
  进行调整。参数innodb_change_buffer_max_size;
  当更新一条记录时，该记录在BufferPool存在，直接在BufferPool修改，一次内存操作。如
  果该记录在BufferPool不存在（没有命中），会直接在ChangeBuffer进行一次内存操作，不
  用再去磁盘查询数据，避免一次磁盘IO。当下次查询记录时，会先进性磁盘读取，然后再从
  ChangeBuffer中读取信息合并，最终载入BufferPool中。
  写缓冲区，仅适用于非唯一普通索引页，为什么？
  如果在索引设置唯一性，在进行修改时，InnoDB必须要做唯一性校验，因此必须查询磁盘，
  做一次IO操作。会直接将记录查询到BufferPool中，然后在缓冲池修改，不会在ChangeBuffer操作。
  • Adaptive Hash Index：自适应哈希索引，用于优化对BP数据的查询。InnoDB存储引擎会监控对表索引的查找，如果观察到建立哈希索引可以带来速度的提升，则建立哈希索引，所以
    称之为自适应。InnoDB存储引擎会自动根据访问的频率和模式来为某些页建立哈希索引。
• Log Buffer：日志缓冲区，用来保存要写入磁盘上log文件（Redo/Undo）的数据，日志缓冲
  区的内容定期刷新到磁盘log文件中。日志缓冲区满时会自动将其刷新到磁盘，当遇到BLOB
  或多行更新的大事务操作时，增加日志缓冲区可以节省磁盘I/O。
  LogBuffer主要是用于记录InnoDB引擎日志，在DML操作时会产生Redo和Undo日志。
  LogBuffer空间满了，会自动写入磁盘。可以通过将innodb_log_buffer_size参数调大，减少
  磁盘IO频率
  innodb_flush_log_at_trx_commit参数控制日志刷新行为，默认为1
  • 0 ： 每隔1秒写日志文件和刷盘操作（写日志文件LogBuffer-->OS cache，刷盘OS
    cache-->磁盘文件），最多丢失1秒数据
  • 1：事务提交，立刻写日志文件和刷盘，数据不丢失，但是会频繁IO操作
  • 2：事务提交，立刻写日志文件，每隔1秒钟进行刷盘操作

二、InnoDB磁盘结构

InnoDB磁盘主要包含Tablespaces，InnoDB Data Dictionary，Doublewrite Buffer、Redo Log
和Undo Logs。

• 表空间（Tablespaces）：用于存储表结构和数据。表空间又分为系统表空间、独立表空间、通用表空间、临时表空间、Undo表空间等多种类型；

1.3.3. InnoDB数据文件

1.3.4. InnoDB数据文件

1.3.5. Undo Log

Undo Log介绍

• Undo：意为撤销或取消，以撤销操作为目的，返回指定某个状态的操作。
• Undo Log：数据库事务开始之前，会将要修改的记录存放到 Undo 日志里，当事务回滚时或者数据库崩溃时，可以利用 Undo 日志，撤销未提交事务对数据库产生的影响。
• Undo Log产生和销毁：Undo Log在事务开始前产生；事务在提交时，并不会立刻删除undo
  log，innodb会将该事务对应的undo log放入到删除列表中，后面会通过后台线程purge thread进行回收处理。Undo Log属于逻辑日志，记录一个变化过程。例如执行一个delete，undolog会记录一个insert；执行一个update，undolog会记录一个相反的update。
• Undo Log存储：undo log采用段的方式管理和记录。在innodb数据文件中包含一种rollback
  segment回滚段，内部包含1024个undo log segment。可以通过下面一组参数来控制Undo log存储。

Undo Log作用

• 实现事务的原子性
  Undo Log 是为了实现事务的原子性而出现的产物。事务处理过程中，如果出现了错误或者用户执行了 ROLLBACK 语句，MySQL 可以利用 Undo Log 中的备份将数据恢复到事务开始之前的状态。

• 实现多版本并发控制（MVCC）
  Undo Log 在 MySQL InnoDB 存储引擎中用来实现多版本并发控制。事务未提交之前，Undo Log保存了未提交之前的版本数据，Undo Log 中的数据可作为数据旧版本快照供其他并发事务进行快照读。

  
  
  image.png

1.3.6. Redo Log和Binlog

Redo Log和Binlog是MySQL日志系统中非常重要的两种机制，也有很多相似之处，下面介绍下两者细节和区别。

Redo Log日志

• Redo Log介绍
  Redo：顾名思义就是重做。以恢复操作为目的，在数据库发生意外时重现操作。
  Redo Log：指事务中修改的任何数据，将最新的数据备份存储的位置（Redo Log），被称为重做日志。
  Redo Log 的生成和释放：随着事务操作的执行，就会生成Redo Log，在事务提交时会将产生Redo Log写入Log Buffer，并不是随着事务的提交就立刻写入磁盘文件。等事务操作的脏页写入到磁盘之后，Redo Log 的使命也就完成了，Redo Log占用的空间就可以重用（被覆盖写入）。

• Redo Log工作原理
  Redo Log 是为了实现事务的持久性而出现的产物。防止在发生故障的时间点，尚有脏页未写入表的 IBD 文件中，在重启 MySQL 服务的时候，根据 Redo Log 进行重做，从而达到事务的未入磁盘数据进行持久化这一特性。

  
  
  image.png

• Redo Log写入机制
  Redo Log 文件内容是以顺序循环的方式写入文件，写满时则回溯到第一个文件，进行覆盖写。

  
  
  image.png
• Redo Log相关配置参数
  每个InnoDB存储引擎至少有1个重做日志文件组（group），每个文件组至少有2个重做日志文件，默认为ib_logfile0和ib_logfile1。可以通过下面一组参数控制Redo Log存储：

  show variables like '%innodb_log%';
  

  Redo Buffer 持久化到 Redo Log 的策略，可通过 Innodb_flush_log_at_trx_commit 设置：
  • 0：每秒提交 Redo buffer ->OS cache -> flush cache to disk，可能丢失一秒内的事务数
    据。由后台Master线程每隔 1秒执行一次操作。
  • 1（默认值）：每次事务提交执行 Redo Buffer -> OS cache -> flush cache to disk，最安
    全，性能最差的方式。
  • 2：每次事务提交执行 Redo Buffer -> OS cache，然后由后台Master线程再每隔1秒执行OS cache -> flush cache to disk 的操作。
    一般建议选择取值2，因为 MySQL 挂了数据没有损失，整个服务器挂了才会损失1秒的事务提交数据。

image.png

Binlog日志

• Binlog记录模式
  Redo Log 是属于InnoDB引擎所特有的日志，而MySQL Server也有自己的日志，即 Binary
  log（二进制日志），简称Binlog。Binlog是记录所有数据库表结构变更以及表数据修改的二进制日志，不会记录SELECT和SHOW这类操作。Binlog日志是以事件形式记录，还包含语句所执行的消耗时间。开启Binlog日志有以下两个最重要的使用场景。
  • 主从复制：在主库中开启Binlog功能，这样主库就可以把Binlog传递给从库，从库拿到
    Binlog后实现数据恢复达到主从数据一致性。
  • 数据恢复：通过mysqlbinlog工具来恢复数据。
    Binlog文件名默认为“主机名_binlog-序列号”格式，例如oak_binlog-000001，也可以在配置文件中指定名称。文件记录模式有STATEMENT、ROW和MIXED三种，具体含义如下。
  • ROW（row-based replication, RBR）：日志中会记录每一行数据被修改的情况，然后在
    slave端对相同的数据进行修改。
    优点：能清楚记录每一个行数据的修改细节，能完全实现主从数据同步和数据的恢复。
    缺点：批量操作，会产生大量的日志，尤其是alter table会让日志暴涨。
  • STATMENT（statement-based replication, SBR）：每一条被修改数据的SQL都会记录到
    master的Binlog中，slave在复制的时候SQL进程会解析成和原来master端执行过的相同的
    SQL再次执行。简称SQL语句复制。
    优点：日志量小，减少磁盘IO，提升存储和恢复速度
    缺点：在某些情况下会导致主从数据不一致，比如last_insert_id()、now()等函数。
  • MIXED（mixed-based replication, MBR）：以上两种模式的混合使用，一般会使用
    STATEMENT模式保存binlog，对于STATEMENT模式无法复制的操作使用ROW模式保存
    binlog，MySQL会根据执行的SQL语句选择写入模式。

• Binlog文件结构
  MySQL的binlog文件
  MySQL的binlog文件中记录的是对数据库的各种修改操作，用来表示修改操作的数据结构是Log event。不同的修改操作对应的不同的log event。比较常用的log event有：Query event、Row event、Xid event等。binlog文件的内容就是各种Log event的集合。
  Binlog文件中Log event结构如下图所示：

  
  
  image.png
• Binlog写入机制
  • 根据记录模式和操作触发event事件生成log event（事件触发执行机制）
  • 将事务执行过程中产生log event写入缓冲区，每个事务线程都有一个缓冲区
    Log Event保存在一个binlog_cache_mngr数据结构中，在该结构中有两个缓冲区，一个是
    stmt_cache，用于存放不支持事务的信息；另一个是trx_cache，用于存放支持事务的信息。
  • 事务在提交阶段会将产生的log event写入到外部binlog文件中。
    不同事务以串行方式将log event写入binlog文件中，所以一个事务包含的log event信息在
    binlog文件中是连续的，中间不会插入其他事务的log event。
• Binlog文件操作
  • Binlog状态查看

  show variables like 'log_bin';
  

  • 开启Binlog功能
    需要修改my.cnf或my.ini配置文件，在[mysqld]下面增加log_bin=mysql_bin_log，重启
    MySQL服务。

  #log-bin=ON 
  #log-bin-basename=mysqlbinlog 
  binlog-format=ROW 
  log-bin=mysqlbinlog
  

  • 使用show binlog events命令

  show binary logs; //等价于show master logs; 
  show master status; 
  show binlog events; 
  show binlog events in 'mysqlbinlog.000001';
  

  • 使用mysqlbinlog 命令

  mysqlbinlog "文件名" 
  mysqlbinlog "文件名" > "test.sql"
  

  • 使用 binlog 恢复数据

  //按指定时间恢复 
  mysqlbinlog --start-datetime="2020-04-25 18:00:00" --stop- datetime="2020-04-26 00:00:00" mysqlbinlog.000002 | mysql -uroot -p1234 
  //按事件位置号恢复 mysqlbinlog --start-position=154 --stop-position=957 mysqlbinlog.000002 | mysql -uroot -p1234
  

  • 删除Binlog文件

  purge binary logs to 'mysqlbinlog.000001'; //删除指定文件 
  purge binary logs before '2020-04-28 00:00:00'; //删除指定时间之前的文件 
  reset master; //清除所有文件
  

  可以通过设置expire_logs_days参数来启动自动清理功能。默认值为0表示没启用。设置为1表示超出1天binlog文件会自动删除掉。
• Redo Log和Binlog区别
  • Redo Log是属于InnoDB引擎功能，Binlog是属于MySQL Server自带功能，并且是以二进制文件记录。
  • Redo Log属于物理日志，记录该数据页更新状态内容，Binlog是逻辑日志，记录更新过程。
  • Redo Log日志是循环写，日志空间大小是固定，Binlog是追加写入，写完一个写下一个，不会覆盖使用。
  • Redo Log作为服务器异常宕机后事务数据自动恢复使用，Binlog可以作为主从复制和数据恢复使用。Binlog没有自动crash-safe能力。

二、MySQL索引原理

2.1. 索引类型

索引可以提升查询速度，会影响where查询，以及order by排序。MySQL索引类型如下：

• 从索引存储结构划分：B Tree索引、Hash索引、FULLTEXT全文索引、R Tree索引
• 从应用层次划分：普通索引、唯一索引、主键索引、复合索引
• 从索引键值类型划分：主键索引、辅助索引（二级索引）
• 从数据存储和索引键值逻辑关系划分：聚集索引（聚簇索引）、非聚集索引（非聚簇索引）

2.1.1. 普通索引

这是最基本的索引类型，基于普通字段建立的索引，没有任何限制。

2.1.2. 唯一索引

与"普通索引"类似，不同的就是：索引字段的值必须唯一，但允许有空值 。在创建或修改表时追加唯一约束，就会自动创建对应的唯一索引。

2.1.3. 主键索引

它是一种特殊的唯一索引，不允许有空值。在创建或修改表时追加主键约束即可，每个表只能有一个主键。

2.1.4. 复合索引

• 单一索引是指索引列为一列的情况，即新建索引的语句只实施在一列上；用户可以在多个列上建立索引，这种索引叫做组复合索引（组合索引）。复合索引可以代替多个单一索引，相比多个单一索引复合索引所需的开销更小。
• 索引同时有两个概念叫做窄索引和宽索引，窄索引是指索引列为1-2列的索引，宽索引也就是索引列超过2列的索引，设计索引的一个重要原则就是能用窄索引不用宽索引，因为窄索引往往比组合索引更有效。

复合索引使用注意事项：

• 何时使用复合索引，要根据where条件建索引，注意不要过多使用索引，过多使用会对更新操作效率有很大影响。
• 如果表已经建立了(col1，col2)，就没有必要再单独建立（col1）；如果现在有(col1)索引，如果查询需要col1和col2条件，可以建立(col1,col2)复合索引，对于查询有一定提高。

2.1.5. 全文索引

查询操作在数据量比较少时，可以使用like模糊查询，但是对于大量的文本数据检索，效率很低。如果使用全文索引，查询速度会比like快很多倍。在MySQL 5.6 以前的版本，只有MyISAM存储引擎支持全文索引，从MySQL 5.6开始MyISAM和InnoDB存储引擎均支持。

和常用的like模糊查询不同，全文索引有自己的语法格式，使用 match 和 against 关键字，比如 select * from user where match(name) against('aaa');

全文索引使用注意事项：

• 全文索引必须在字符串、文本字段上建立。
• 全文索引字段值必须在最小字符和最大字符之间的才会有效。（innodb：3-84；myisam：4-
  84）
• 全文索引字段值要进行切词处理，按syntax字符进行切割，例如b+aaa，切分成b和aaa
• 全文索引匹配查询，默认使用的是等值匹配，例如a匹配a，不会匹配ab,ac。如果想匹配可以在布尔模式下搜索a*

  select * from user where match(name) against('a*' in boolean mode);
  

2.2. 索引原理

MySQL官方对索引定义：是存储引擎用于快速查找记录的一种数据结构。需要额外开辟空间和数据维护工作。

• 索引是物理数据页存储，在数据文件中（InnoDB，ibd文件），利用数据页(page)存储。
• 索引可以加快检索速度，但是同时也会降低增删改操作速度，索引维护需要代价。
  索引涉及的理论知识：二分查找法、Hash和B+Tree。

2.2.1. 二分查找法

二分查找法也叫作折半查找法，它是在有序数组中查找指定数据的搜索算法。它的优点是等值查询、范围查询性能优秀，缺点是更新数据、新增数据、删除数据维护成本高。

• 首先定位left和right两个指针
• 计算(left+right)/2
• 判断除2后索引位置值与目标值的大小比对
• 索引位置值大于目标值就-1，right移动；如果小于目标值就+1，left移动

2.2.2. Hash结构

Hash底层实现是由Hash表来实现的，是根据键值 <key,value> 存储数据的结构。非常适合根据key查找value值，也就是单个key查询，或者说等值查询。

Hash索引在MySQL 中Hash结构主要应用在Memory原生的Hash索引 、InnoDB 自适应哈希索引。
InnoDB提供的自适应哈希索引功能强大，接下来重点描述下InnoDB 自适应哈希索引。
InnoDB自适应哈希索引是为了提升查询效率，InnoDB存储引擎会监控表上各个索引页的查询，当InnoDB注意到某些索引值访问非常频繁时，会在内存中基于B+Tree索引再创建一个哈希索引，使得内存中的 B+Tree 索引具备哈希索引的功能，即能够快速定值访问频繁访问的索引页。
InnoDB自适应哈希索引：在使用Hash索引访问时，一次性查找就能定位数据，等值查询效率要优于B+Tree。
自适应哈希索引的建立使得InnoDB存储引擎能自动根据索引页访问的频率和模式自动地为某些热点页建立哈希索引来加速访问。另外InnoDB自适应哈希索引的功能，用户只能选择开启或关闭功能，无法进行人工干涉。

show engine innodb status \G; 
show variables like '%innodb_adaptive%';

2.2.3. B+Tree结构

MySQL数据库索引采用的是B+Tree结构，在B-Tree结构上做了优化改造。

• B-Tree结构

  • 索引值和data数据分布在整棵树结构中
  • 每个节点可以存放多个索引值及对应的data数据

  • 树节点中的多个索引值从左到右升序排列

    
    
    image.png
    
    

    B树的搜索：从根节点开始，对节点内的索引值序列采用二分法查找，如果命中就结束查找。没有命中会进入子节点重复查找过程，直到所对应的的节点指针为空，或已经是叶子节点了才结束。

• B+Tree结构

  • 非叶子节点不存储data数据，只存储索引值，这样便于存储更多的索引值
  • 叶子节点包含了所有的索引值和data数据

  • 叶子节点用指针连接，提高区间的访问性能

    
    
    image.png