导航：
【Java笔记+踩坑汇总】Java基础+JavaWeb+SSM+SpringBoot+SpringCloud+瑞吉外卖/谷粒商城/学成在线+设计模式+面试题汇总+性能调优/架构设计+源码解析
目录
2.2.2、演示innoDB的B+树聚簇索引，存储数据和目录
一、存储引擎
1.1、查看、设置存储引擎的命令
查看mysql提供什么存储引擎：
show engines;
查看默认的存储引擎：
show variables like '%storage_engine%';
或者：
SELECT @@default_storage_engine;
创建表时指定存储引擎:
CREATE TABLE 表名( 建表语句; ) ENGINE = 存储引擎名称;
修改表的存储引擎
ALTER TABLE 表名 ENGINE = 存储引擎名称;
1.2、InnoDB引擎
1.2.1、介绍
InnoDB：支持外键和事务，行锁适合高并发，缓存索引和数据，内存要求高（因为要缓存索引和记录），适合存大数据量，增删改性能更优（行级锁高并发），耗费磁盘（因为有多个非聚簇索引，索引可能比记录空间还大）。
InnoDB索引文件在数据库中存放的对应表的磁盘文件有*.frm，*.ibd结尾的两个文件；
- frm文件是存放的表结构，表的定义信息；
- *.ibd文件是存放着表中的数据、索引信息；
特点：
- MySQL从3.23.34a开始就包含InnoDB存储引擎。大于等于5.5之后，默认采用InnoDB引擎。
- InnoDB是MySQL的默认事务型引擎，它被设计用来处理大量的短期(short-lived)事务。可以确保事务的完整提交(Commit)和回滚(Rollback)。
- 除了增加和查询外，还需要更新、删除操作，那么，应优先选择InnoDB存储引擎。
- 除非有非常特别的原因需要使用其他的存储引擎，否则应该优先考虑InnoDB引擎。
- InnoDB是为处理巨大数据量的最大性能设计。
- 在以前的版本中，字典数据以元数据文件、非事务表等来存储。现在这些元数据文件被删除了。比如： .frm ， .par ， .trn ， .isl ， .db.opt 等都在MySQL8.0中不存在了。
- 表名.frm 存储表结构（MySQL8.0时，合并在表名.ibd中）；表名.ibd 存储数据和索引
- InnoDB增删改性能更优；MyISAM查询性能更优。
- MyISAM只缓存索引，不缓存真实数据；InnoDB不仅缓存索引还要缓存真实数据， 对内存要求较高，而且内存大小对性能有决定性的影响。
1.2.2、优势
InnoDB存储引擎在实际应用中拥有诸多优势，比如操作便利、提高了数据库的性能、维护成本低等。如果由于硬件或软件的原因导致服务器崩溃，那么在重启服务器之后不需要进行额外的操作。InnoDB崩溃恢复功能自动将之前提交的内容定型，然后撤销没有提交的进程，重启之后继续从崩溃点开始执行。
InnoDB存储引擎在主内存中维护缓冲池，高频率使用的数据将在内存中直接被处理。这种缓存方式应用于多种信息，加速了处理进程。
在专用服务器上，物理内存中高达80%的部分被应用于缓冲池。如果需要将数据插入不同的表中，可以设置外键加强数据的完整性。更新或者删除数据，关联数据将会被自动更新或删除。如果试图将数据插入从表，但在主表中没有对应的数据，插入的数据将被自动移除。如果磁盘或内存中的数据出现崩溃，在使用脏数据之前，校验和机制会发出警告。当每个表的主键都设置合理时，与这些列有关的操作会被自动优化。插入、更新和删除操作通过做改变缓冲自动机制进行优化。InnoDB不仅支持当前读写，也会缓冲改变的数据到数据流磁盘。
InnoDB的性能优势不只存在于长时运行查询的大型表。在同一列多次被查询时，自适应哈希索引会提高查询的速度。使用InnoDB可以压缩表和相关的索引，可以在不影响性能和可用性的情况下创建或删除索引。对于大型文本和BLOB数据，使用动态行形式，这种存储布局更高效。通过查询INFORMATION_SCHEMA库中的表可以监控存储引擎的内部工作。在同一个语句中，InnoDB表可以与其他存储引擎表混用。即使有些操作系统限制文件大小为2GB，InnoDB仍然可以处理。当处理大数据量时，InnoDB兼顾CPU，以达到最大性能。
1.2.3、InnoDB事务的ACID特性
隔离性：事务之间互相隔离。
持久性：一旦事务成功，数据一定会落入数据库。
ACID模型是一系列数据库设计规则，这些规则着重强调可靠性，而可靠性对于商业数据和任务关键型应用非常重要。MySQL包含类似InnoDB存储引擎的组件，与ACID模型紧密相连，这样出现意外时，数据不会崩溃，结果不会失真。如果依赖ACID模型，可以不使用一致性检查和崩溃恢复机制。如果拥有额外的软件保护，极可靠的硬件或者应用可以容忍一小部分的数据丢失和不一致，可以将MySQL设置调整为只依赖部分ACID特性，以达到更高的性能。
下面讲解InnoDB存储引擎与ACID模型相同作用的四个方面：
1. 原子方面 ACID的原子方面主要涉及InnoDB事务，与MySQL相关的特性主要包括：
- 自动提交设置。
- COMMIT语句。
- ROLLBACK语句。
- 操作INFORMATION_SCHEMA库中的表数据。
2. 一致性方面 ACID模型的一致性主要涉及保护数据不崩溃的内部InnoDB处理过程，与MySQL相关的特性主要包括：
- InnoDB双写缓存。
- InnoDB崩溃恢复。
3. 隔离方面 隔离是应用于事务的级别，与MySQL相关的特性主要包括：
- 自动提交设置。
- SET ISOLATION LEVEL语句。
- InnoDB锁的低级别信息。
4. 持久性方面 ACID模型的持久性主要涉及与硬件配置相互影响的MySQL软件特性。由于硬件复杂多样化，耐久性方面没有具体的规则可循。与MySQL相关的特性有：
- InnoDB双写缓存，通过innodb_doublewrite配置项配置。
- 配置项innodb_flush_log_at_trx_commit。
- 配置项sync_binlog。
- 配置项innodb_file_per_table。
- 存储设备的写入缓存。
- 存储设备的备用电池缓存。
- 运行MySQL的操作系统。
- 持续的电力供应。
- 备份策略。
- 对分布式或托管的应用，最主要的在于硬件设备的地点以及网络情况。
1.2.4、InnoDB架构
1. 缓冲池 缓冲池是主内存中的一部分空间，用来缓存已使用的表和索引数据。缓冲池使得经常被使用的数据能够直接在内存中获得，从而提高速度。
2. 更改缓存 更改缓存是一个特殊的数据结构，当受影响的索引页不在缓存中时，更改缓存会缓存辅助索引页的更改。索引页被其他读取操作时会加载到缓存池，缓存的更改内容就会被合并。不同于集群索引，辅助索引并非独一无二的。当系统大部分闲置时，清除操作会定期运行，将更新的索引页刷入磁盘。更新缓存合并期间，可能会大大降低查询的性能。在内存中，更新缓存占用一部分InnoDB缓冲池。在磁盘中，更新缓存是系统表空间的一部分。更新缓存的数据类型由innodb_change_buffering配置项管理。
3. 自适应哈希索引 自适应哈希索引将负载和足够的内存结合起来，使得InnoDB像内存数据库一样运行，不需要降低事务上的性能或可靠性。这个特性通过innodb_adaptive_hash_index选项配置，或者通过--skip-innodb_adaptive_hash_index命令行在服务启动时关闭。
4. 重做日志缓存 重做日志缓存存放要放入重做日志的数据。重做日志缓存大小通过innodb_log_buffer_size配置项配置。重做日志缓存会定期地将日志文件刷入磁盘。大型的重做日志缓存使得大型事务能够正常运行而不需要写入磁盘。
5. 系统表空间 系统表空间包括InnoDB数据字典、双写缓存、更新缓存和撤销日志，同时也包括表和索引数据。多表共享，系统表空间被视为共享表空间。
6. 双写缓存 双写缓存位于系统表空间中，用于写入从缓存池刷新的数据页。只有在刷新并写入双写缓存后，InnoDB才会将数据页写入合适的位置。
7. 撤销日志 撤销日志是一系列与事务相关的撤销记录的集合，包含如何撤销事务最近的更改。如果其他事务要查询原始数据，可以从撤销日志记录中追溯未更改的数据。撤销日志存在于撤销日志片段中，这些片段包含于回滚片段中。
8. 每个表一个文件的表空间 每个表一个文件的表空间是指每个单独的表空间创建在自身的数据文件中，而不是系统表空间中。这个功能通过innodb_file_per_table配置项开启。每个表空间由一个单独的.ibd数据文件代表，该文件默认被创建在数据库目录中。
9. 通用表空间 使用CREATE TABLESPACE语法创建共享的InnoDB表空间。通用表空间可以创建在MySQL数据目录之外能够管理多个表并支持所有行格式的表。
10. 撤销表空间 撤销表空间由一个或多个包含撤销日志的文件组成。撤销表空间的数量由innodb_undo_tablespaces配置项配置。
11. 临时表空间 用户创建的临时表空间和基于磁盘的内部临时表都创建于临时表空间。innodb_temp_data_file_path配置项定义了相关的路径、名称、大小和属性。如果该值为空，默认会在innodb_data_home_dir变量指定的目录下创建一个自动扩展的数据文件。
12. 重做日志 重做日志是基于磁盘的数据结构，在崩溃恢复期间使用，用来纠正数据。正常操作期间，重做日志会将请求数据进行编码，这些请求会改变InnoDB表数据。遇到意外崩溃后，未完成的更改会自动在初始化期间重新进行。
1.3、MyISAM 引擎
1.3.1、MyISAM 引擎介绍
MyISAM：不支持外键和事务，表锁不适合高并发，缓存索引和数据地址，内存要求低（因为不用缓存记录），查询性能更优（因为查询时InnoDB要维护MVCC一致，而且多缓存了记录），节省磁盘（因为磁盘不存完整记录）。
MyISAM索引文件在数据库中存放的对应表的磁盘文件有*.frm，*.MYD，*.MYI结尾的三个文件；
- frm文件是存放的表结构，表的定义信息；
- MYD文件是存放着表中的数据；
- MYI文件存放着表的索引信息；
MyISAM特点：
- MyISAM提供了大量的特性，包括全文索引、压缩、空间函数(GIS)等，但MyISAM 不支持事务、行级锁、外键，有一个毫无疑问的缺陷就是崩溃后无法安全恢复。
- 5.5之前默认的存储引擎
- 优势是访问的速度快，对事务完整性没有要求或者以SELECT、INSERT为主的应用
- 针对数据统计有额外的常数存储。故而 count(*) 的查询效率很高
- 表名.frm 存储表结构；表名.MYD 存储数据 (MYData)；表名.MYI 存储索引 (MYIndex)
- 应用场景：只读应用或者以读为主的业务
1.3.2、InnoDB对比MyISAM
InnoDB：支持外键和事务，行锁适合高并发，缓存索引和数据，内存要求高（因为要缓存索引和记录），适合存大数据量，增删改性能更优（行级锁高并发），耗费磁盘（因为有多个非聚簇索引，索引可能比记录空间还大）。
MyISAM：不支持外键和事务，表锁不适合高并发，缓存索引和数据地址，内存要求低（因为不用缓存记录），查询性能更优（因为查询时InnoDB要维护MVCC一致，而且多缓存了记录），节省磁盘（因为磁盘不存完整记录）。
对比 |
InnoDB |
MyISAM |
特点 |
支持外键和事务 |
不支持外键和事务 |
行表锁 |
行锁，操作时只锁某一行，不对其它行有影响， 适合高并发的操作 |
表锁，即使操作一条记录也会锁住整个表，不适合高并发的操作 |
缓存 |
缓存索引和数据，对内存要求较高，而且内存大小对性能有决定性的影响 |
只缓存索引，不缓存真实数据 |
关注点 |
事务：并发写、事务、更大资源 |
性能：节省资源、消耗少、简单业务、查询快 |
默认使用 |
5.5及其之后 | 5.5之前 |
1.4、其他引擎
- Archive 引擎：用于数据存档。非常适合存储大量的独立的，作为历史记录的数据，因为它们不经常被读取。它 拥有高效的插入速度，但其对查询的支持相对较差。
- Blackhole 引擎：丢弃写操作，读操作会返回空内容
- CSV 引擎：存储数据时，以逗号分隔各个数据项
- Memory 引擎：置于内存的表。将所有数据存储在 RAM 中，以便在需要快速查找非关键数据的环境中进行快速访问，以前被称为 HEAP 引擎。
- Federated 引擎：访问远程表。提供连接单独的 MySQL 服务器，从多个物理服务器创建一个逻辑数据库的能力，非常适合分布式或数据集市环境。
- Merge引擎：管理多个MyISAM表构成的表集合
- NDB引擎：MySQL集群专用存储引擎。高冗余的存储引擎，用多台数据机器联合提供服务以提高整体性能和安全性。适合数据量大，安全和性能要求高的应用。
二、索引
2.1、介绍
MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。
索引是一种用于快速查询的排好序的数据结构。
索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满足特定查找算法。这些数据结构以某种方式指向数据， 这样就可以在这些数据结构的基础上实现高级查找算法。
索引是在存储引擎中实现的，因此每种存储引擎的索引不一定完全相同，并且每种存储引擎不一定支持所有索引类型。innoDB存储引擎的索引是B+树。同时，存储引擎可以定义每个表的 最大索引数和最大索引长度。所有存储引擎支持每个表至少16个索引，总索引长度至少为256字节。有些存储引擎支持更多的索引数和更大的索引长度。
优点：
（1）类似大学图书馆建书目索引，提高数据检索的效率，降低数据库的IO成本，减少磁盘I/O次数，这也是创建索引最主要的原因。
（2）通过创建唯一索引，可以保证数据库表中每一行数据的唯一性。
（3）在实现数据的参考完整性方面，可以加速表和表之间的连接。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。
（4）在使用分组和排序子句进行数据查询时，可以显著提高查询速度，因为索引是“排好序的”，减少查询中分组和排序的时间，降低了CPU的消耗。
缺点
增加索引也有许多不利的方面，主要表现在如下几个方面：
（1）创建索引和维护索引要耗费时间，并且随着数据量的增加，所耗费的时间也会增加。
（2）索引需要占磁盘空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间， 存储在磁盘上，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。
（3）虽然索引大大提高了查询速度，同时却会降低更新表的速度。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。
因此，选择使用索引时，需要综合考虑索引的优点和缺点。
2.2、B+树
2.2.1、B+树介绍
B+树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，最底层是0层，这与二叉树恰好相反。
m阶 B+树有如下特征:
- 每个非叶节点关键字个数和孩子个数相等；
- 根结点关键字个数2到m，非跟结点关键字个数⌈m/2⌉到m；
- 所有叶子在同一层；
B+树结构：
数的层数越低，IO次数越少，查询越快。
InnoDB的B+树索引的注意事项：
1. 根页面位置万年不动
2. 内节点中目录项记录的唯一性
3. 一个页面最少存储2条记录
真实一个数据页可以存100条记录， 一个目录页能存1000条数据；4层B+树能存一千万条数据，我们用到的B+树都不会超过4层，每个页内部可以用二分查找更快查找。
InnoDB非聚簇索引情况：
InnoDB 页的大小为 16KB，一般表的主键类型为 INT(占用4个字节)或 BIGINT (占用8个字节)，指针类型也一般为4或8个字节，也就是说一个页 (B+Tree 中的一个节点)中大概存储16KB/(8B+8B)=1K个键值 (因为是估值，为方便计算，这里的K取值为 10^3。也就是说一个深度为3的B+Tree 索引可以维护 10^3*10^3*10^3= 1 亿条记录(这里假定一个数据页也存储10A3条行记录数据了)
实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree 的高度一般都在 2~4 层。MySQL的lnnoDB 存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要 1~3 次磁盘IO操作（根节点被缓存，不算IO次数）。
数据页大小：
MyISAM 的数据页大小是固定的，是 1KB，也就是说，MyISAM 存储引擎的数据都是以 1KB 的块进行管理的。
InnoDB 存储引擎的数据页大小是可调的，默认是 16KB。在 MySQL 5.7 版本之前，InnoDB 的数据页大小默认是 8KB。可以通过参数
innodb_page_size来设置 InnoDB 的数据页大小，取值范围是 4KB、8KB、16KB 和 32KB。
2.2.2、演示innoDB的B+树聚簇索引，存储数据和目录
每条记录是Compact 行格式：
CREATE TABLE index_demo( c1 INT, c2 INT, c3 CHAR(1), PRIMARY KEY(c1) ) ROW_FORMAT = Compact;
演示：假设一个数据页只能存三条数据，一个目录页只能存四条数据，下面是存储状态：
单个目录（两层B+树）：
大目录嵌套多个小目录（3层B+树）：
2.3、innoDB的索引方案
2.3.1、聚簇索引
聚族索引并不是一种单独的索引类型，而是一种数据存储方式(基于主键映射目录和排序的B+树，所有的用户记录都存储在了叶子节点)，也就是所谓的索引即数据（因为记录就存在B+树叶节点），数据即索引。
特点：
1. 使用记录主键值的大小进行各层之间的映射、层内的排序，这包括三个方面的含义：
- 页内的记录是按照主键的大小顺序排成一个单向链表。
- 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
- 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
2. B+树的叶子节点存储的是完整的用户记录。
所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。
优点：
- 数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
- 聚簇索引对于主键的排序查找和范围查找速度非常快
- 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以节省了大量的io操作。
缺点：
- 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
- 更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新
- 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据
2.3.2、非聚簇索引（又称辅助索引、二级索引）
聚簇索引基于主键映射目录和页内页间排序，查询条件为主键时才有用。
想查第二列时，就得新创建一个B+树，也就是非聚簇索引B+树，它基于非主键列映射目录和排序，叶节点存非主键字段的值和主键字段的值。通过第二列查到了主键值，再回表（回到聚簇索引的表）根据主键值查完整记录。
非聚簇索引是一种数据存储方式(基于非主键字段映射目录和排序的B+树，叶节点存非主键字段的值和主键字段的值)。
注意：innoDB主键建议使用自增策略，从0开始。因为：
- innoDB的主键不建议过长，因为每个二级索引都要存主键，主键过长会耗费磁盘空间和性能（每个数据页只能16KB，主键空间占多会导致每页存记录个数变少，导致B+树层级变深）；
- B+树插入速度严重依赖于插入顺序，非单调主键会使B+树频繁分裂调整为自增顺序，性能变差。
实际中，一个MySQL表会有一个聚簇索引用于查主键或者回表，有多个非聚簇索引（辅助索引、二级索引）用于查非主键字段。
为什么非聚簇索引B+树的叶节点不存完整记录，还要回表多此一举呢？
如果表中有100列，那就需要99个非聚簇索引，要是都存完整记录，那就太浪费磁盘空间了。
2.3.3、聚簇索引和非聚簇索引区别
- 叶节点：聚簇索引的 叶子节点 存储的就是我们的 数据记录，非聚簇索引的叶子节点存储的是 数据位置 。非聚簇索引不会影响数据表的物理存储顺序。
- 数量：一个表只能有一个聚簇索引，因为只能有一种排序存储的方式，但可以有多个非聚簇索引，也就是多个索引目录提供数据检索。
- 效率：使用聚簇索引的时候，数据的查询效率高 ，但如果对数据进行插入，删除，更新等操作，效率会比非聚簇索引低。因为聚簇索引存的完整记录，移动起来慢；
2.3.4、联合索引
我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立非聚簇索引。
比方说我们想让B+树按照c2和c3列的大小进行排序，这个包含两层含义：
- 每个目录记录包括c2字段、c3字段、页码，每个用户记录包括c2字段、c3字段、主键；
- 先把各个记录和页按照c2列进行排序；
- 在记录的c2列相同的情况下，采用c3列进行排序
注意：
以c2和c3列的大小为排序规则建立的B+树称为联合索引，本质上也是一个非聚簇索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的，不同点如下：
- 建立联合索引只会建立如上图一样的1棵B+树。
- 为c2和c3列分别建立索引会分别以c2和c3列的大小为排序规则建立2棵B+树。
2.4、MyISAM的索引方案
MyISAM引擎使用B+Tree 作为索引结构，叶子节点的data域存放的是待查询字段和数据记录的地址。
MyISAM引擎没有二级索引，只有聚簇索引。
2.5、MyISAM 与 InnoDB对比
MyISAM的索引方式都是“非聚簇”的，与InnoDB包含1个聚簇索引是不同的。
① 查找次数：在InnoDB存储引擎中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM 中却需要进行一次回表操作，意味着MyISAM中建立的索引相当于全部都是二级索引。
② 是否“索引即数据”：InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
③ 叶节点data域存储内容：InnoDB的非聚簇索引data域存储相应记录主键的值，而MyISAM索引记录的是待查询字段和地址。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。
④ 查询速度：MyISAM的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通过获取主键之后再回表去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。
⑤ 是否必须有主键：InnoDB要求表必须有主键（ MyISAM可以没有）。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。
2.6、索引的代价
索引是个好东西，可不能乱建，它在空间和时间上都会有消耗：
空间上的代价
每建立一个索引都要为它建立一棵B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会占用16KB 的存储空间，一棵很大的B+树由许多数据页组成，那就是很大的一片存储空间。
时间上的代价
每次对表中的数据进行增、删、改操作时，都需要去修改各个B+树索引。而且我们讲过，B+树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位， 页面分裂、页面回收等操作来维护好节点和记录的排序。如果
我们建了许多索引，每个索引对应的B+树都要进行相关的维护操作，会给性能拖后腿。
2.7、Hash结构
2.7.1、Hash结构介绍
哈希表+链地址法处理冲突+链表长度大于8时转为红黑树；
Hash 本身是一个函数，又被称为散列函数，它可以帮助我们大幅提升检索数据的效率Hash 算法是通过某种确定性的算法(比如 MD5、SHA1、SHA2、SHA3) 将输入转变为输出。相同的输入永远可以得到相同的输出，假设输入内容有微小偏差，在输出中通常会有不同的结果。
优点：增删改查时间复杂度O（1），从效率上来看，比B+树快；
缺点：范围查找效率差，退化成O（n）；排序效率极慢，数据存储没有顺序；每个节点是联合所有字段计算哈希值，无法对单独一个字段索引；不建议重复值多的情况使用，冲突时要不断比较整理链地址或红黑树耗费时间；
2.7.2、innoDB自适应的哈希索引
innoDB不支持哈希索引，但支持自适应的哈希索引。如果某个数据经常被访问，当满足一定条件的时候，就会将这个数据页的地址存放到Hash 表中。这样下次查询的时候，就可以直接找到这个页面的所在位置。这样让 B+ 树也具备了 Hash 索引的优点。
2.7.3、Hash 索引与 B+ 树索引的区别
1、Hash 索引不能进行范围查询，而 B+ 树可以。这是因为 Hash 索引指向的数据是无序的，而 B+ 的叶子节点是个有序的链表。
2、Hash 索引 不支持联合索引的最左侧原则 (即联合索引的部分索引无法使用)，而 B+ 树可以。对于联合索引来说，Hash 索引在计算 Hash 值的时候是将索引键合并后再一起计算 Hash 值，所以不会针对每个索引单独计算 Hash 值。因此如果用到联合索引的一个或者几个索引时，联合索引无法被利用。
3、Hash 索不支持 ORDER BY 排序，因为 Hash 索引指向的数据是无序的，因此无法起到排序优化的作用，而 B+ 树索引数据是有序的，可以起到对该字段 ORDER BY 排序优化的作用。同理，我们也无法用 Hash索引进行 模糊查询，而 B+ 使用LKE 进行模糊查询的时候，LIKE 后面后模糊查询(比如 % 结尾)的话就可
2.8、B树
2.8.1、介绍
B树的英文是 Balance Tree，也就是 多路平衡查找树。简写为B-Tree (注意横杠表示这两个单词连起来的意思，不是减号)。它的高度远小于平衡二叉树的高度，毕竟是多叉不是二叉。
B树作为多路平衡查找树，它的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶。每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块中包括了x 个关键字，那么指针数就是x+1（例如节点有17和35两个关键字，它的三个子节点主键值范围分别是小于17、17~35之间、大于35）。对于一个 100 阶的B 树来说，如果有 3 层的话最多可以存储约 100 万的索引数据。
小结：
1.B树在插入和删除节点的时候如果导致树不平衡，就通过自动调整节点的位置来保持树的自平衡.
2.关键字集合分布在整棵树中,即叶子节点和非叶子节点都存放数据。搜索有可能在非叶子节点结束
3.其搜索性能等价于在关键字全集内做一次二分查找。
2.8.2、B+ 树和 B 树的差异
1. 非叶节点的关键字数量：k阶树，B+树非叶节点有k个值、k个孩子，B树非叶节点有k-1个值、k个孩子；
2. 记录存储位置：B+树记录全存在叶节点，B树记录存在所有节点；
3. 非叶节点功能：B+树非叶节点存索引，B树非叶节点存记录；
4. 叶子结点之间关系：B+树所有叶子节点构成一个有序双向链表；B树叶节点之间没指针，只是有序；
B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树。
但B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然。
B+树中间结点不直接存储数据，好处：
查询效率更高（比B树矮胖），IO次数也少，更稳定，查询范围也更大。
为了减少IO，索引树会一次性加载吗？
不会，会逐一加载数据页，先加载大目录页、再加载小目录页、再加载记录页。
- 数据库索引是存储在磁盘上的，如果数据量很大，必然导致索引的大小也会很大，超过几个G。
- 当我们利用索引查询时候，是不可能将全部几个G的索引都加载进内存的，我们能做的只能是: 逐一加载每一个磁盘页，因为磁盘页对应着索引树的节点。
B+树的存储能力如何? 为何说一般查找行记录，最多只需1~3次磁盘IO
lnnoDB 存储引擎中页的大小为 16KB，一般表的主键类型为 INT(占用4个字节)或 BIGINT (占用8个字节)，指针类型也一般为4或8个字节，也就是说一个页 (B+Tree 中的一个节点)中大概存储16KB/(8B+8B)=1K个键值 (因为是估值，为方便计算，这里的K取值为 10^3。也就是说一个深度为3的B+Tree 索引可以维护 10^3*10^3*10^3= 1 亿条记录(这里假定一个数据页也存储10A3条行记录数据了)
实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree 的高度一般都在 2~4 层。MySQL的lnnoDB 存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要 1~3 次磁盘IO操作（根节点被缓存，不算IO次数）
2.9、红黑树
数据库为什么不用红黑树而用B+树？
因为B+树是多叉，红黑树是二叉，B+树更矮胖，查询性能更高，IO次数更少。
红黑树： 近似平衡二叉树，左右子树高差有可能大于 1，查找效率略低于平衡二叉树，但增删效率高于平衡二叉树，适合频繁插入删除。
- 结点非黑即红；
- 根结点是黑色，叶节点是黑色空节点（常省略）；
- 任何相邻节点不能同时为红色；
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点；
- 查询性能稳定O(logN)，高度最高2log(n+1)；
三、innoDB数据存储结构
3.1、页
3.1.1、页：数据库的基本存储单位
页是磁盘与内存交互基本单位。
InnoDB 将数据划分为若千个页，InnoDB中页的大小默认为 16KB
以页作为磁盘和内存之间交互的基本单位，也就是一次最少从磁盘中读取16KB的内容到内存中，一次最少把内存中的16KB内容刷新到磁盘中。也就是说，在数据库中，不论读一行，还是读多行，都是将这些行所在的页进行加载。
也就是说，数据库管理存储空间的基本单位是页 (Page) ，数据库I/0 操作的最小单位是页。一个页中可以存储多个行记录。
记录是按照行来存储的，但是数据库的读取并不以行为单位，否则一次读取(也就是一次 /0 操作)只能处理一行数据，效率会非常低。
3.1.2、数据页的大小
MyISAM 的数据页大小是固定的，是 1KB，也就是说，MyISAM 存储引擎的数据都是以 1KB 的块进行管理的。
InnoDB 存储引擎的数据页大小是可调的，默认是 16KB。在 MySQL 5.7 版本之前，InnoDB 的数据页大小默认是 8KB。可以通过参数 innodb_page_size 来设置 InnoDB 的数据页大小，取值范围是 4KB、8KB、16KB 和 32KB。
3.1.3、页结构
页a、页b、页c...页n 这些页可以 不在物理结构上相连，只要通过双向表相关联即可。每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表 ，每个数据页都会为存储在它里边的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法（有序表可以用二分法）快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
不同的数据库管理系统(简称DBMS )的页大小不同。比如在 MySQL 的 nnoDB 存储引擎中，默认页的大小是16KB。查看页大小:
show variables like '%innodb_page_size%'
页的内部结构：
页如果按类型划分的话，常见的有 数据页(保存 B+ 树节点)、系统页、Undo 页和 事务数据页 等。数据页是我们最常使用的页。
数据页的 16KB 大小的存储空间被划分为七个部分，分别是文件头 (File Header)、页头 (Page Header)、最大最小记录 (Infimum+supremum) 、用户记录 (User Records) 、空闲空间 (Free Space)、页目录 (PageDirectory) 和文件尾 (File Tailer) 。
页结构的示意图如下所示:
这7个部分作用分别如下，我们简单梳理如下表所示
我们可以把这7个结构分成3个部分：
第1部分: File Header (文件头部)和 File Trailer(文件尾部)
第2部分: User Records (用户记录)、最大最小记录、Free Space(空闲空间)
第3部分: Page Directory (页目录)、Page Header(页面头部)
3.2、行、页、区、段、表空间的关系
另外在数据库中，还存在着区(Extent)、段 (Segment) 和表空间 (Tablespace) 的概念。
行、页、区、段、表空间的关系如下图所示:
区(Extent)是比页大一级的存储结构，在 innoDB 存储引擎中，一个区会分配 64 个连续的页。因为nnoDB 中的页大小默认是 16KB，所以一个区的大小是 64*16KB= 1MB。
段(Segment)由一个或多个区组成，区在文件系统是一个连续分配的空间(在innoDB 中是连续的 64 个页)不过在段中不要求区与区之间是相邻的。段是数据库中的分配单位 ，不同类型的数据库对象以不同的段形式存在。当我们创建数据表、索引的时候，就会相应创建对应的段，比如创建一张表时会创建一个表段，创建一个索引时会创建一个索引段。
表空间(Tablespace)是一个逻辑容器，表空间存储的对象是段，在一个表空间中可以有一个或多个段，但是一个段只能属干一个表空间。数据库由一个或多个表空间组成，表空间从管理上可以划分为 系统表空间、用户表空间、撤销表空间、 临时表空间 等。
3.3、innoDB行格式
3.3.1、四种行格式
我们平时的数据以行为单位来向表中插入数据，这些记录在磁盘上的存放方式也被称为行格式（也叫记录格式）。
InnoDB存储引擎设计了4种不同类型的行格式，分别是Compact、Redundant、Dynamic、Compressed行格式。
Compact
在MySQL 5.1版本中，默认设置为Compact行格式。一条完整的记录其实可以被分为记录的额外信息和记录的真实数据两大部分。
Dynamic
在MySQL 8.0中，默认行格式就是Dynamic。
Dynamic、Compressed行格式和Compact行格式挺像，只不过在处理行溢出数据时有分歧：
- Compressed和Dynamic两种记录格式对于存放在BLOB中的数据采用了完全的行溢出的方式。如图，在数据页中只存放20个字节的指针（溢出页的地址），实际的数据都存放在Off Page（溢出页）中。
- Compact和Redundant两种格式会在记录的真实数据处存储一部分数据（存放768个前缀字节）。
Compressed
Compressed行记录格式的另一个功能就是，存储在其中的行数据会以zlib的算法进行压缩，因此对于BLOB、TEXT、VARCHAR这类大长度类型的数据能够进行非常有效的存储。
Redundant
Redundant是MySQL 5.0版本之前InnoDB的行记录存储方式，MySQL 5.0支持Redundant是为了兼容之前版本的页格式。
从上图可以看到，不同于Compact行记录格式，Redundant行格式的首部是一个字段长度偏移列表，同样是按照列的顺序逆序放置的。
3.3.2、指定行格式的命令
查看MySQL8的默认行格式：
SELECT @@innodb_default_row_format;
也可以使用如下语法查看具体表使用的行格式：
SHOW TABLE STATUS like '表名'\G
在创建或修改表的语句中指定行格式：
CREATE TABLE 表名 (列的信息) ROW_FORMAT=行格式名称 ALTER TABLE 表名 ROW_FORMAT=行格式名称
举例：
CREATE TABLE record_test_table ( col1 VARCHAR(8), col2 VARCHAR(8) NOT NULL, col3 CHAR(8), col4 VARCHAR(8) ) CHARSET=ascii ROW_FORMAT=COMPACT;
向表中插入两条记录：
INSERT INTO record_test_table(col1, col2, col3, col4) VALUES ('zhangsan', 'lisi', 'wangwu', 'songhk'), ('tong', 'chen', NULL, NULL);
