一、存储引擎

1.1 查看存储引擎

查看mysql提供什么存储引擎：

show engines;

show engines \G;

显式如下：

*************************** 1. row ***************************
Engine: InnoDB
Support: DEFAULT
Comment: Supports transactions, row-level locking, and foreign keys
Transactions: YES
XA: YES
Savepoints: YES
*************************** 2. row ***************************
Engine: MRG_MYISAM
Support: YES
Comment: Collection of identical MyISAM tables
Transactions: NO
XA: NO
Savepoints: NO
*************************** 3. row ***************************
Engine: MEMORY
Support: YES
Comment: Hash based, stored in memory, useful for temporary tables
Transactions: NO
XA: NO
Savepoints: NO
*************************** 4. row ***************************
Engine: BLACKHOLE
Support: YES
Comment: /dev/null storage engine (anything you write to it disappears)
Transactions: NO
XA: NO
Savepoints: NO
*************************** 5. row ***************************
Engine: MyISAM
Support: YES
Comment: MyISAM storage engine
Transactions: NO
XA: NO
Savepoints: NO
*************************** 6. row ***************************
Engine: CSV
Support: YES
Comment: CSV storage engine
Transactions: NO
XA: NO
Savepoints: NO
*************************** 7. row ***************************
Engine: ARCHIVE
Support: YES
Comment: Archive storage engine
Transactions: NO
XA: NO
Savepoints: NO
*************************** 8. row ***************************
Engine: PERFORMANCE_SCHEMA
Support: YES
Comment: Performance Schema
Transactions: NO
XA: NO
Savepoints: NO
*************************** 9. row ***************************
Engine: FEDERATED
Support: NO
Comment: Federated MySQL storage engine
Transactions: NULL
XA: NULL
Savepoints: NULL

1.2 设置系统默认的存储引擎

• 查看默认的存储引擎：

show variables like '%storage_engine%';
#或
SELECT @@default_storage_engine;

• 修改默认的存储引擎
  如果在创建表的语句中没有显式指定表的存储引擎的话，那就会默认使用InnoDB 作为表的存储引擎。如果我们想改变表的默认存储引擎的话，可以这样写启动服务器的命令行：

SET DEFAULT_STORAGE_ENGINE=MyISAM;

或者修改my.cnf 文件：

default-storage-engine=MyISAM
# 重启服务
systemctl restart mysqld.service

1.3 设置表的存储引擎

存储引擎是负责对表中的数据进行提取和写入工作的，我们可以为不同的表设置不同的存储引擎，也就是说不同的表可以有不同的物理存储结构，不同的提取和写入方式。

1.3.1 创建表时指定存储引擎

我们之前创建表的语句都没有指定表的存储引擎，那就会使用默认的存储引擎InnoDB 。如果我们想显式的指定一下表的存储引擎，那可以这么写：

CREATE TABLE 表名(
建表语句;
) ENGINE = 存储引擎名称;

1.3.2 修改表的存储引擎

如果表已经建好了，我们也可以使用下边这个语句来修改表的存储引擎：

ALTER TABLE 表名 ENGINE = 存储引擎名称;

比如我们修改一下engine_demo_table表的存储引擎：

mysql> ALTER TABLE engine_demo_table ENGINE = InnoDB;
Query OK, 0 rows affected (0.05 sec)
Records: 0 Duplicates: 0 Warnings: 0

这时我们再查看一下engine_demo_table 的表结构：

mysql> SHOW CREATE TABLE engine_demo_table\G
*************************** 1. row ***************************
Table: engine_demo_table
Create Table: CREATE TABLE `engine_demo_table` (
`i` int(11) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8
1 row in set (0.01 sec)

1.4 引擎介绍

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

• MySQL从3.23.34a开始就包含InnoDB存储引擎。大于等于5.5之后，默认采用InnoDB引擎。
• InnoDB是MySQL的默认事务型引擎，它被设计用来处理大量的短期(short-lived)事务。可以确保事务的完整提交(Commit)和回滚(Rollback)。
• 除了增加和查询外，还需要更新、删除操作，那么，应优先选择InnoDB存储引擎。
• 除非有非常特别的原因需要使用其他的存储引擎，否则应该优先考虑InnoDB引擎。
• 数据文件结构：（在《第02章_MySQL数据目录》章节已讲）
  • 表名.frm 存储表结构（MySQL8.0时，合并在表名.ibd中）
  • 表名.ibd 存储数据和索引
• InnoDB是为处理巨大数据量的最大性能设计。
  • 在以前的版本中，字典数据以元数据文件、非事务表等来存储。现在这些元数据文件被删除了。比如： .frm ， .par ， .trn ， .isl ，.db.opt 等都在MySQL8.0中不存在了。
  • 对比MyISAM的存储引擎， InnoDB写的处理效率差一些，并且会占用更多的磁盘空间以保存数据和索引。
  • MyISAM只缓存索引，不缓存真实数据；InnoDB不仅缓存索引还要缓存真实数据， 对内存要求较高，而且内存大小对性能有决定性的影响。

1.4.2 MyISAM 引擎：主要的非事务处理存储引擎

• MyISAM提供了大量的特性，包括全文索引、压缩、空间函数(GIS)等，但MyISAM 不支持事务、行级锁、外键，有一个毫无疑问的缺陷就是崩溃后无法安全恢复。
• 5.5之前默认的存储引擎
• 优势是访问的速度快，对事务完整性没有要求或者以SELECT、INSERT为主的应用
• 针对数据统计有额外的常数存储。故而 count(*) 的查询效率很高
• 数据文件结构：（在《第02章_MySQL数据目录》章节已讲）
  • 表名.frm 存储表结构
  • 表名.MYD 存储数据 (MYData)
  • 表名.MYI 存储索引 (MYIndex)
• 应用场景：只读应用或者以读为主的业务

1.4.3 Archive 引擎：用于数据存档

• 下表展示了ARCHIVE 存储引擎功能
  
  

1.4.4 Blackhole 引擎：丢弃写操作，读操作会返回空内容

1.4.5 CSV 引擎：存储数据时，以逗号分隔各个数据项

使用案例如下:

mysql> CREATE TABLE test (i INT NOT NULL, c CHAR(10) NOT NULL) ENGINE = CSV;
Query OK, 0 rows affected (0.06 sec)
mysql> INSERT INTO test VALUES(1,'record one'),(2,'record two');
Query OK, 2 rows affected (0.05 sec)
Records: 2 Duplicates: 0 Warnings: 0
mysql> SELECT * FROM test;
+---+------------+
| i | c          |
+---+------------+
| 1 | record one |
| 2 | record two |
+---+------------+
2 rows in set (0.00 sec)

创建CSV表还会创建相应的元文件，用于存储表的状态和表中存在的行数。此文件的名称与表的名称相同，后缀为CSM 。如图所示

如果检查test.CSV 通过执行上述语句创建的数据库目录中的文件，其内容使用Notepad++打开如下：

"1","record one"
"2","record two"

这种格式可以被 Microsoft Excel 等电子表格应用程序读取，甚至写入。使用Microsoft Excel打开如图所示

1.4.6 Memory 引擎：置于内存的表

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

主要特征：

• Memory同时支持哈希（HASH）索引和B+树索引。
• Memory表至少比MyISAM表要快一个数量级。
• MEMORY 表的大小是受到限制的。表的大小主要取决于两个参数，分别是max_rows 和max_heap_table_size 。其中，max_rows可以在创建表时指定；max_heap_table_size的大小默认为16MB，可以按需要进行扩大。
• 数据文件与索引文件分开存储。
• 缺点：其数据易丢失，生命周期短。基于这个缺陷，选择MEMORY存储引擎时需要特别小心。

使用Memory存储引擎的场景：

1. 目标数据比较小，而且非常频繁的进行访问，在内存中存放数据，如果太大的数据会造成内存溢出。可以通过参数max_heap_table_size 控制Memory表的大小，限制Memory表的最大的大小。
2. 如果数据是临时的，而且必须立即可用得到，那么就可以放在内存中。
3. 存储在Memory表中的数据如果突然间丢失的话也没有太大的关系。

1.4.7 Federated 引擎：访问远程表

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

1.4.8 Merge引擎：管理多个MyISAM表构成的表集合

1.4.9 NDB引擎：MySQL集群专用存储引擎

也叫做 NDB Cluster 存储引擎，主要用于 MySQL Cluster 分布式集群环境，类似于 Oracle 的 RAC 集
群。

1.4.10 引擎对比

MySQL中同一个数据库，不同的表可以选择不同的存储引擎。如下表对常用存储引擎做出了对比。

1.5. MyISAM和InnoDB

• 很多人对 InnoDB 和 MyISAM 的取舍存在疑问，到底选择哪个比较好呢？
  MySQL5.5之前的默认存储引擎是MyISAM，5.5之后改为了InnoDB。
  

1.6. 阿里巴巴、淘宝用哪个

• Percona 为 MySQL 数据库服务器进行了改进，在功能和性能上较 MySQL 有很显著的提升。
• 该版本提升了在高负载情况下的 InnoDB 的性能、为 DBA 提供一些非常有用的性能诊断工具；另外有更多的参数和命令来控制服务器行为。
• 该公司新建了一款存储引擎叫Xtradb 完全可以替代Innodb ，并且在性能和并发上做得更好
• 阿里巴巴大部分mysql数据库其实使用的percona的原型加以修改。

1.7课外补充：

1、InnoDB表的优势
InnoDB存储引擎在实际应用中拥有诸多优势，比如操作便利、提高了数据库的性能、维护成本低等。如果由于硬件或软件的原因导致服务器崩溃，那么在重启服务器之后不需要进行额外的操作。InnoDB崩溃恢复功能自动将之前提交的内容定型，然后撤销没有提交的进程，重启之后继续从崩溃点开始执行。
InnoDB存储引擎在主内存中维护缓冲池，高频率使用的数据将在内存中直接被处理。这种缓存方式应用于多种信息，加速了处理进程。
在专用服务器上，物理内存中高达80%的部分被应用于缓冲池。如果需要将数据插入不同的表中，可以设置外键加强数据的完整性。更新或者删除数据，关联数据将会被自动更新或删除。如果试图将数据插入从表，但在主表中没有对应的数据，插入的数据将被自动移除。如果磁盘或内存中的数据出现崩溃，在使用脏数据之前，校验和机制会发出警告。当每个表的主键都设置合理时，与这些列有关的操作会被自动优化。插入、更新和删除操作通过做改变缓冲自动机制进行优化。InnoDB不仅支持当前读写，也会缓冲改变的数据到数据流磁盘。
InnoDB的性能优势不只存在于长时运行查询的大型表。在同一列多次被查询时，自适应哈希索引会提高查询的速度。使用InnoDB可以压缩表和相关的索引，可以在不影响性能和可用性的情况下创建或删除索引。对于大型文本和BLOB数据，使用动态行形式，这种存储布局更高效。通过查询INFORMATION_SCHEMA库中的表可以监控存储引擎的内部工作。在同一个语句中，InnoDB表可以与其他存储引擎表混用。即使有些操作系统限制文件大小为2GB，InnoDB仍然可以处理。当处理大数据量时，InnoDB兼顾CPU，以达到最大性能。

2、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的操作系统。
   • 持续的电力供应。
   • 备份策略。
   • 对分布式或托管的应用，最主要的在于硬件设备的地点以及网络情况。

3、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表数据。遇到意外崩溃后，未完成的更改会自动在初始化期间重新进行。

二、索引的数据结构

2.1 为什么使用索引

假如给数据使用二叉树这样的数据结构进行存储，如下图所示

2.2. 索引及其优缺点

2.2.1 索引概述

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。
索引的本质：索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”，满足特定查找算法。
这些数据结构以某种方式指向数据， 这样就可以在这些数据结构的基础上实现高级查找算法。

2.2.2 优点

1. 类似大学图书馆建书目索引，提高数据检索的效率，降低数据库的IO成本，这也是创建索引最主要的原因。
2. 通过创建唯一索引，可以保证数据库表中每一行数据的唯一性。
3. 在实现数据的参考完整性方面，可以加速表和表之间的连接。换句话说，对于有依赖关系的子表和父表联合查询时，可以提高查询速度。
4. 在使用分组和排序子句进行数据查询时，可以显著减少查询中分组和排序的时间，降低了CPU的消耗。

2.2.3 缺点

增加索引也有许多不利的方面，主要表现在如下几个方面：

1. 创建索引和维护索引要耗费时间，并且随着数据量的增加，所耗费的时间也会增加。
2. 索引需要占磁盘空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间， 存储在磁盘上，如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。
3. 虽然索引大大提高了查询速度，同时却会降低更新表的速度。当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，这样就降低了数据的维护速度。
   因此，选择使用索引时，需要综合考虑索引的优点和缺点。

2.3 InnoDB中索引的推演

2.3.1 索引之前的查找

先来看一个精确匹配的例子：

SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;

1. 在一个页中的查找
2. 在很多页中查找
   在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们上面的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的。如果一个表有一亿条记录呢？此时索引应运而生。

2.3.2 设计索引

建一个表：

mysql> CREATE TABLE index_demo(
-> c1 INT,
-> c2 INT,
-> c3 CHAR(1),
-> PRIMARY KEY(c1)
-> ) ROW_FORMAT = Compact;

这个新建的index_demo 表中有2个INT类型的列，1个CHAR(1)类型的列，而且我们规定了c1列为主键，这个表使用Compact 行格式来实际存储记录的。这里我们简化了index_demo表的行格式示意图：

我们只在示意图里展示记录的这几个部分：

• record_type ：记录头信息的一项属性，表示记录的类型， 0 表示普通记录、2 表示最小记录、3 表示最大记录、1 暂时还没用过，下面讲。
• next_record ：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，我们用箭头来表明下一条记录是谁。
• 各个列的值：这里只记录在index_demo 表中的三个列，分别是c1 、c2 和c3 。
• 其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。
  将记录格式示意图的其他信息项暂时去掉并把它竖起来的效果就是这样：
  

把一些记录放到页里的示意图就是：

1. 一个简单的索引设计方案
   我们在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。所以如果我们想快速的定位到需要查找的记录在哪些数据页中该咋办？我们可以为快速定位记录所在的数据页而建立一个目录，建这个目录必须完成下边这些事：

• 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。
• 给所有的页建立一个目录项。
  所以我们为上边几个页做好的目录就像这样子：
  
  以页28为例，它对应目录项2，这个目录项中包含着该页的页号28以及该页中用户记录的最小主键值5 。我们只需要把几个目录项在物理存储器上连续存储（比如：数组），就可以实现根据主键值快速查找某条记录的功能了。比如：查找主键值为20 的记录，具体查找过程分两步：

1. 先从目录项中根据二分法快速确定出主键值为20的记录在目录项3 中（因为 12 < 20 < 209 ），它对应的页是页9 。

2. 再根据前边说的在页中查找记录的方式去页9 中定位具体的记录。
   至此，针对数据页做的简易目录就搞定了。这个目录有一个别名，称为索引。

3. InnoDB中的索引方案
   ① 迭代1次：目录项纪录的页
   我们把前边使用到的目录项放到数据页中的样子就是这样：
   
   从图中可以看出来，我们新分配了一个编号为30的页来专门存储目录项记录。这里再次强调目录项记录和普通的用户记录的不同点：

• 目录项记录的record_type 值是1，而普通用户记录的record_type 值是0。
• 目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有InnoDB自己添加的隐藏列。
• 了解：记录头信息里还有一个叫min_rec_mask 的属性，只有在存储目录项记录的页中的主键值,最小的目录项记录的min_rec_mask 值为1 ，其他别的记录的min_rec_mask 值都是0 。
  相同点：两者用的是一样的数据页，都会为主键值生成Page Directory （页目录），从而在按照主键
  值进行查找时可以使用二分法来加快查询速度。
  现在以查找主键为20的记录为例，根据某个主键值去查找记录的步骤就可以大致拆分成下边两步：

1. 先到存储目录项记录的页，也就是页30中通过二分法快速定位到对应目录项，因为12 < 20 < 209 ，所以定位到对应的记录所在的页就是页9。
2. 再到存储用户记录的页9中根据二分法快速定位到主键值为20 的用户记录。
   ② 迭代2次：多个目录项纪录的页
   
   从图中可以看出，我们插入了一条主键值为320的用户记录之后需要两个新的数据页：
   为存储该用户记录而新生成了页31 。
   因为原先存储目录项记录的页30的容量已满（我们前边假设只能存储4条目录项记录），所以不得
   不需要一个新的页32 来存放页31 对应的目录项。
   现在因为存储目录项记录的页不止一个，所以如果我们想根据主键值查找一条用户记录大致需要3个步骤，以查找主键值为20的记录为例：
3. 确定目录项记录页
   我们现在的存储目录项记录的页有两个，即页30 和页32 ，又因为页30表示的目录项的主键值的范围是[1, 320)，页32表示的目录项的主键值不小于320 ，所以主键值为20 的记录对应的目录项记录在页30 中。
4. 通过目录项记录页确定用户记录真实所在的页。
   在一个存储目录项记录的页中通过主键值定位一条目录项记录的方式说过了。
5. 在真实存储用户记录的页中定位到具体的记录。
   ③ 迭代3次：目录项记录页的目录页
   
   如图，我们生成了一个存储更高级目录项的页33 ，这个页中的两条记录分别代表页30和页32，如果用
   户记录的主键值在[1, 320) 之间，则到页30中查找更详细的目录项记录，如果主键值不小于320 的
   话，就到页32中查找更详细的目录项记录。
   我们可以用下边这个图来描述它：
   
   这个数据结构，它的名称是B+树。
   ④ B+Tree
   一个B+树的节点其实可以分成好多层，规定最下边的那层，也就是存放我们用户记录的那层为第0层，之后依次往上加。之前我们做了一个非常极端的假设：存放用户记录的页最多存放3条记录，存放目录项记录的页最多存放4条记录。其实真实环境中一个页存放的记录数量是非常大的，假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录，所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录，那么：

• 如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放100条记录。
• 如果B+树有2层，最多能存放1000×100=10,0000 条记录。
• 如果B+树有3层，最多能存放1000×1000×100=1,0000,0000条记录。
• 如果B+树有4层，最多能存放1000×1000×1000×100=1000,0000,0000 条记录。相当多的记录！！！
  你的表里能存放100000000000 条记录吗？所以一般情况下，我们用到的B+树都不会超过4层，那我们
  通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页），又
  因为在每个页面内有所谓的Page Directory （页目录），所以在页面内也可以通过二分法实现快速
  定位记录。

2.3.3 常见索引概念

索引按照物理实现方式，索引可以分为 2 种：聚簇（聚集）和非聚簇（非聚集）索引。我们也把非聚集索引称为二级索引或者辅助索引。

1. 聚簇索引
   特点：
2. 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
   • 页内的记录是按照主键的大小顺序排成一个单向链表。
   • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
   • 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
3. B+树的叶子节点存储的是完整的用户记录。
   所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

优点：

• 数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
• 聚簇索引对于主键的排序查找和范围查找速度非常快
• 按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以节省了大量的io操作。
  缺点：
• 插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
• 更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新
• 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据

2. 二级索引（辅助索引、非聚簇索引）
   

概念：回表 我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值，所以如果我们想根据c2列的值查找到完整的用户记录的话，仍然需要到聚簇索引中再查一遍，这个过程称为回表。也就是根据c2列的值查询一条完整的用户记录需要使用到2棵B+树！
问题：为什么我们还需要一次回表操作呢？直接把完整的用户记录放到叶子节点不OK吗？

3. 联合索引
   我们也可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按照c2和c3列的大小进行排序，这个包含两层含义：

• 先把各个记录和页按照c2列进行排序。
• 在记录的c2列相同的情况下，采用c3列进行排序
  注意一点，以c2和c3列的大小为排序规则建立的B+树称为联合索引，本质上也是一个二级索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的，不同点如下：
• 建立联合索引只会建立如上图一样的1棵B+树。
• 为c2和c3列分别建立索引会分别以c2和c3列的大小为排序规则建立2棵B+树。

2.3.4 InnoDB的B+树索引的注意事项

1. 根页面位置万年不动
2. 内节点中目录项记录的唯一性
3. 一个页面最少存储2条记录

2.4 MyISAM中的索引方案

B树索引适用存储引擎如表所示：

2.4.1 MyISAM索引的原理

下图是MyISAM索引的原理图。

如果我们在Col2上建立一个二级索引，则此索引的结构如下图所示：

2.4.2 MyISAM 与 InnoDB对比

MyISAM的索引方式都是“非聚簇”的，与InnoDB包含1个聚簇索引是不同的。小结两种引擎中索引的区别：
① 在InnoDB存储引擎中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM 中却需要进行一次回表操作，意味着MyISAM中建立的索引相当于全部都是二级索引。
② InnoDB的数据文件本身就是索引文件，而MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
③ InnoDB的非聚簇索引data域存储相应记录主键的值，而MyISAM索引记录的是地址。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。
④ MyISAM的回表操作是十分快速的，因为是拿着地址偏移量直接到文件中取数据的，反观InnoDB是通
过获取主键之后再去聚簇索引里找记录，虽然说也不慢，但还是比不上直接用地址去访问。
⑤ InnoDB要求表必须有主键（ MyISAM可以没有）。如果没有显式指定，则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。

2.5 索引的代价

索引是个好东西，可不能乱建，它在空间和时间上都会有消耗：

• 空间上的代价
  每建立一个索引都要为它建立一棵B+树，每一棵B+树的每一个节点都是一个数据页，一个页默认会占用16KB 的存储空间，一棵很大的B+树由许多数据页组成，那就是很大的一片存储空间。
• 时间上的代价
  每次对表中的数据进行增、删、改操作时，都需要去修改各个B+树索引。而且我们讲过，B+树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收等操作来维护好节点和记录的排序。如果我们建了许多索引，每个索引对应的B+树都要进行相关的维护操作，会给性能拖后腿。

2.6 MySQL数据结构选择的合理性

2.6.1 全表遍历

这里都懒得说了。

2.6.2 Hash结构

上图中哈希函数h有可能将两个不同的关键字映射到相同的位置，这叫做碰撞，在数据库中一般采用链接法来解决。在链接法中，将散列到同一槽位的元素放在一个链表中，如下图所示：

实验：体会数组和hash表的查找方面的效率区别

// 算法复杂度为 O(n)
@Test
public void test1(){
int[] arr = new int[100000];
for(int i = 0;i < arr.length;i++){
arr[i] = i + 1;
}
long start = System.currentTimeMillis();
for(int j = 1; j<=100000;j++){
int temp = j;
for(int i = 0;i < arr.length;i++){
if(temp == arr[i]){
break;
}
}
}
long end = System.currentTimeMillis();
System.out.println("time： " + (end - start)); //time： 823
}

//算法复杂度为 O(1)
@Test
public void test2(){
HashSet<Integer> set = new HashSet<>(100000);
for(int i = 0;i < 100000;i++){
set.add(i + 1);
}
long start = System.currentTimeMillis();
for(int j = 1; j<=100000;j++) {
int temp = j;
boolean contains = set.contains(temp);
}
long end = System.currentTimeMillis();
System.out.println("time： " + (end - start)); //time： 5
}

Hash结构效率高，那为什么索引结构要设计成树型呢？
Hash索引适用存储引擎如表所示：

索引 / 存储引擎	MyISAM	InnoDB	Memory
HASH索引	不支持	不支持	支持
Hash索引的适用性：
采用自适应 Hash 索引目的是方便根据 SQL 的查询条件加速定位到叶子节点，特别是当 B+ 树比较深的时候，通过自适应 Hash 索引可以明显提高数据的检索效率。
我们可以通过innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash，比如：

mysql> show variables like '%adaptive_hash_index';

2.6.3 二叉搜索树

如果我们利用二叉树作为索引结构，那么磁盘的IO次数和索引树的高度是相关的。

1. 二叉搜索树的特点
2. 查找规则
   
   创造出来的二分搜索树如下图所示：
   
   为了提高查询效率，就需要减少磁盘IO数。为了减少磁盘IO的次数，就需要尽量降低树的高度，需要把原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好。

2.6.4 AVL树

针对同样的数据，如果我们把二叉树改成 M 叉树（M>2）呢？当 M=3 时，同样的 31 个节点可以由下面的三叉树来进行存储：

2.6.5 B-Tree

B 树的结构如下图所示：

一个 M 阶的 B 树（M>2）有以下的特性：

1. 根节点的儿子数的范围是 [2,M]。
2. 每个中间节点包含 k-1 个关键字和 k 个孩子，孩子的数量 = 关键字的数量 +1，k 的取值范围为[ceil(M/2), M]。
3. 叶子节点包括 k-1 个关键字（叶子节点没有孩子），k 的取值范围为 [ceil(M/2), M]。
4. 假设中间节点节点的关键字为：Key[1], Key[2], …, Key[k-1]，且关键字按照升序排序，即 Key[i]<Key[i+1]。此时 k-1 个关键字相当于划分了 k 个范围，也就是对应着 k 个指针，即为：P[1], P[2], …,P[k]，其中 P[1] 指向关键字小于 Key[1] 的子树，P[i] 指向关键字属于 (Key[i-1], Key[i]) 的子树，P[k]指向关键字大于 Key[k-1] 的子树。
5. 所有叶子节点位于同一层。
   上面那张图所表示的 B 树就是一棵 3 阶的 B 树。我们可以看下磁盘块 2，里面的关键字为（8，12），它有 3 个孩子 (3，5)，(9，10) 和 (13，15)，你能看到 (3，5) 小于 8，(9，10) 在 8 和 12 之间，而 (13，15)大于 12，刚好符合刚才我们给出的特征。
   然后我们来看下如何用 B 树进行查找。假设我们想要查找的关键字是 9 ，那么步骤可以分为以下几步：
6. 我们与根节点的关键字 (17，35）进行比较，9 小于 17 那么得到指针 P1；
7. 按照指针 P1 找到磁盘块 2，关键字为（8，12），因为 9 在 8 和 12 之间，所以我们得到指针 P2；
8. 按照指针 P2 找到磁盘块 6，关键字为（9，10），然后我们找到了关键字 9。

你能看出来在 B 树的搜索过程中，我们比较的次数并不少，但如果把数据读取出来然后在内存中进行比较，这个时间就是可以忽略不计的。而读取磁盘块本身需要进行 I/O 操作，消耗的时间比在内存中进行比较所需要的时间要多，是数据查找用时的重要因素。B 树相比于平衡二叉树来说磁盘 I/O 操作要少，在数据查询中比平衡二叉树效率要高。所以只要树的高度足够低，IO次数足够少，就可以提高查询性能。
再举例1：

2.6.6 B+Tree

• MySQL官网说明：
  

B+ 树和 B 树的差异：

1. 有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数+1。
2. 非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）。
3. 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中， 非叶子节点既保存索引，也保存数据记录。
4. 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。

B 树和 B+ 树都可以作为索引的数据结构，在 MySQL 中采用的是 B+ 树。
但B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然。

• 思考题：为了减少IO，索引树会一次性加载吗？
• 思考题：B+树的存储能力如何？为何说一般查找行记录，最多只需1~3次磁盘IO
• 思考题：为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？
• 思考题：Hash 索引与 B+ 树索引的区别
• 思考题：Hash 索引与 B+ 树索引是在建索引的时候手动指定的吗？

2.6.7 R树

R-Tree在MySQL很少使用，仅支持geometry数据类型，支持该类型的存储引擎只有myisam、bdb、innodb、ndb、archive几种。举个R树在现实领域中能够解决的例子：查找20英里以内所有的餐厅。如果没有R树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中，一个字段记录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满足要求。如果一个地区有100家餐厅的话，我们就要进行100次位置计算操作了，如果应用到谷歌、百度地图这种超大数据库中，这种方法便必定不可行了。R树就很好的解决了这种高维空间搜索问题。它把B树的思想很好的扩展到了多维空间，采用了B树分割空间的思想，并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R树就是一棵用来存储高维数据的平衡树。相对于B-Tree，R-Tree的优势在于范围查找。

2.7 附录：算法的时间复杂度

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。