一、数据结构
B树、 B+树和红黑树都是常见的平衡查找树数据结构，用于在大规模数据集中高效地进行查找、插入和删除操作。它们的设计目标是通过平衡树的结构来保证在最坏情况下的时间复杂度接近于 O(log n) ，其中 n 表示数据集的大小。
1. B树
B 树是一种自平衡的树型数据结构，其叶子节点与非叶子节点都可用于存储数据。
如存在一组数据 [2, 4, 6, 8, 10] 则其对应的 B 树形式之一为下图所示。
- 它的结构类似于一个多路搜索树，每个节点可以包含多个子节点和关键字。
B树的特点是可以存储大量的数据，并且能够高效地支持随机访问和范围查询。B树的节点可以存储大量的关键字，而且节点可以有多个子节点，这使得B树在磁盘等外部存储上具有良好的性能，因为每个节点可以存储大量的关键字，从而减少了磁盘I/O的次数。
2. B+树
B+ 树是在 B 树基础上进行了改进的一种树型数据结构，其所有数据皆在叶子节点，MySQL 中即通过 B+ 树存储数据。
同样的若存在一组数据 [2, 4, 6, 8, 10] 则其对应的 B+ 树形式之一为下图所示，非叶子节点仅用于数据的索引，不存储真实数据。注意这里仅以最基本的二路 B+ 树为例，若在 MySQL 中通常为数十上百路的形式存储。
B+树与B树相似，但其所有的关键字都出现在叶子节点上。B+树中每个叶子节点之间通过链表连接，形成一个有序的数据链表。- 内部节点只包含用于导航的关键字，而不存储数据本身。这样的设计使得
B+树更适合用于范围查询，因为范围查询可以直接沿着叶子节点的链表进行遍历，而无需回溯到内部节点。
3. 红黑树
红黑树是一种自平衡的二叉查找树，它在树的节点上增加了额外的颜色属性，可以是红色或黑色。红黑树的数据存储于非叶子节点，而叶子节点通常是 NIL(占位符) 节点，即不存储实际的数据，只是用来表示树的末端。
红黑树具有以下特点：
- 每个节点都有一个颜色属性，要么是红色，要么是黑色。
- 根节点是黑色的。
- 所有叶子节点（
NIL节点）都是黑色的。- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从根节点到叶子节点的每条路径上，黑色节点的数量相同。
红黑树通过保持上述特性来保持平衡。这使得红黑树在插入和删除节点时能够保持树的平衡性，并且可以在最坏情况下保证 O(log n) 的查找、插入和删除操作。
4. 差异点
B 树和 B+ 树适用于存储大规模数据的场景，特别是磁盘上的数据存储，它们具有高度的扇出性能，可以减少磁盘 I/O 次数，提高数据访问效率。而 B+ 树相对于 B 树在范围查询和顺序访问方面有更好的性能。
红黑树则适用于内存中的数据结构，它通过颜色属性的调整来保持树的平衡性，具有更快的插入和删除操作。
二、聚簇索引
1. 索引分类
常用的数据库索引分类如下：
| 方法 | 作用 |
|---|---|
| B-Tree索引 | B-Tree 索引是最常见的一种索引，也是默认索引类型，适用于等值查询、范围查询、排序等场景。 |
| 哈希索引 | 哈希索引是将关键字通过哈希算法转化为哈希值，然后根据哈希值进行查找。哈希索引适用于等值查询，但不适用于范围查询和排序。 |
| 全文索引 | 全文索引适用于对文本内容进行检索的场景。全文索引可以解决 like 查询效率低下的问题。 |
| 空间索引 | 空间索引是在空间数据类型(例如点、线、多边形等) 上建立的索引，适用于 GIS (地理信息系统) 应用。 |
| 全文空间索引 | 全文空间索引是全文索引和空间索引的结合，适用于 GIS 应用中的文本检索场景。 |
| 唯一索引 | 唯一索引要求每个索引值都是唯一的，适用于不允许出现重复值的字段。 |
| 聚簇索引 | 聚簇索引是按照表中数据物理存储的顺序建立的索引，聚簇索引的叶子节点存储的是整个数据行，适用于基于范围查询的场景。 |
| 非聚簇索引 | 非聚簇索引是独立于数据存储的一种索引类型，非聚簇索引的叶子节点存储的是索引值和一个指向对应数据行的指针，适用于基于等值查询的场景。 |
2. 结构介绍
聚簇索引是将索引与数据存储进行共同存储，以 Innodb 中的 B-Tree 结构为例，其叶子节点存储的即为真实记录数据。如存在存在一张表其包含四条记录，则其对应的逻辑索引结构如下图所示。
3. 辅助索引
聚簇索引具有唯一性即一张表仅允许存在一个聚簇索引，通常使用主键作为索引键构建，若表未手动声明主键则会使用默认生成的 db_row_id 作为索引键。由于一张表仅有一个聚簇索引，因此其它索引都基于聚簇索引，通常称此类索引为 辅助索引。
辅助索引的叶子节点末端不再存储完整的真实数据，取而代之存储的是对应记录的主键值。因此，针对辅助索引的查询会涉及到两步骤，首先根据辅助索引树查询到目标记录主键，再根据该主键查询聚簇索引最终查询到目标记录，这个过程也称之为回表。
同样以上述数据为例，在聚簇索引的基础上创建一个以 name 为索引列的索引，当查询 where name = 'Alex'，其查询路径为下图中黄色路径。
4. 结构优点
在 Innodb 中数据的存储单位是页，即当查询时数据时将同一页的数据刷入内存中，又因为聚簇索引数据是直接存储于叶子节点，此时内容中已经包含了具体数据。同时 MySQL 中提供了一系列缓存 (buffer) 机制，当再次访问时内存中数据命中率将会提高从而减少 IO 操作提高查询效率。
在聚簇索引中，其物理存储结构使得相邻的数据行存储于相邻的物理磁盘中，因此对于范围查询此类涉及到大量数据的操作而言，可减少数据磁盘的 IO 次数，从而提高查询效率。
5. 结构缺点
聚簇索引同样也存在一些不足之处，由于叶子节点存储的为真实数据，当发生插入与更新操作时导致存储结构自平衡引发的数据读写移动，可能会涉及到较为频繁的磁盘 IO 操作。而非聚簇索引叶子节点存储的指定数据的指针索引，其相对应的效率更高。
此外，在聚簇索引中对应主键字段的取值并不建议使用随机数或 UUID，而更建议使用自增或雪花 ID 以保证数据的连贯性，从而减少磁盘 IO 次数提高存储效率。
三、非聚簇索引
1. 基本介绍
非聚簇索引是独立于数据存储的一种索引类型，非聚簇索引的叶子节点存储的是索引值和一个指向对应数据行的指针，在 MyISAM 中采用的即该数据结构。
还是以上述的数据为例，其对应的非聚簇索引逻辑结构如下图所示：
2. 插入缓冲
在非聚簇索引中涉及到一个重要概念 —— 插入缓冲 (Insert Buffer)，其为 Change Buffer 中的一部分。
对于非聚簇索引结构而言，其检索的依据是根据辅助索引与聚簇索引二者共同构成，但对于辅助索引而言其物理磁盘数据可能是相邻的，但其对应的 B+ 树索引结构却是离散的。
因此，在执行插入或更新时，并不是每一次都会直接插入到索引页中，而是先判断插人的非聚集索引页是否在缓冲池中，若在则执行插入操作，否则先放入 Insert Buffer 中，再由另一线程异步定期根据缓存和索引页数据执行 merge 操作，提高了对于非聚簇索引插入的性能。
四、索引创建
1. 普通索引
在数据查询中，可以为查询条件中字段添加索引从而提高查询效率，创建索引的基本语法如下：
CREATE INDEX <index_name>
ON <table_name> (column_1);
2. 主键索引
若一张表没有设置主键列时会自动为每条记录生成一条 6 位数的标识码作为隐式主键。
主键索引创建较为简单，当一个字段被表示为主键时会自动为其创建索引，注意主键字段必须设置为非空字段。
CREATE TABLE <table_name> (
`<column_name>` varchar(100) NOT NULL PRIMARY KEY,
);
ALTER TABLE <table_name>
ADD PRIMARY KEY (<column_name>)
3. 唯一索引
唯一索引与主键索引不同是其列的值可以包含空值，在指定多列时只有在这多个列的值都不相同时才互斥。
如果表中已经存在重复数据，则创建唯一索引时会失败。在这种情况下，需要先删除重复数据，或者使用 IGNORE 关键字来忽略重复数据并创建唯一索引。
-- 创建多列唯一索引
CREATE UNIQUE INDEX <index_name>
ON <table_name> (column_1, ..., column_n);
-- 方式二，作用同上
ALTER TABLE <table_name>
ADD UNIQUE (column_1, ..., column_n);
-- 忽略重复数据创建唯一索引
CREATE UNIQUE INDEX <index_name>
ON <table_name> (column_1, ..., column_n) IGNORE;
4. 外键索引
当两种表存在关联关系时通常可以为表创建外键索引从而提高查询效率，如 学生表 与 成绩表 之间存在明显的关联关系即可为其创建外键索引。
创建外键之前需要先为 主表 和 从表 先创建索引，否则无法为 从表 创建外键。
-- 为外键列创建索引
CREATE INDEX <index_name>
ON <slave_table> (<slave_column>);
-- 为外键列创建索引
ALTER TABLE <slave_table>
ADD INDEX <index_name> (<slave_column>);
需要注意针对已经存在的表添加外键索引时，若 从表 中存在没有与 主表 的关联的记录需要先删除，否则将会异常创建失败。
-- 建表指定
CREATE TABLE parent (
id INT PRIMARY KEY,
name VARCHAR(50) NOT NULL
);
CREATE TABLE child (
id INT PRIMARY KEY,
parent_id INT NOT NULL,
name VARCHAR(50) NOT NULL,
FOREIGN KEY (parent_id) REFERENCES parent(id)
);
-- 存在表新增
ALTER TABLE <slave_table>
ADD CONSTRAINT <foreign_name>
FOREIGN KEY (<column_name>)
REFERENCES <master_table>(<master_column>)
5. 联合索引
联合索引查询条件中涉及到的列的顺序需要与索引中建立的列的顺序一致，才能充分利用索引的优势。否则即使该列已经建立了索引，也无法发挥优化效果。
CREATE INDEX <index_name>
ON <table_name> (column_1, ..., column_n);
ALTER TABLE <table_name>
ADD INDEX <index_name> (column_1, ..., column_n);
五、索引应用
1. 基本使用
通过 show index 关键字可以查看对应表已经存在的索引。
show index
from <table_name>
通过 force 关键字可以强制语句使用索引。
select
*
from
<table_name>
force
index(<index_name>)
2. 失效场景
在实际应用场景中，创建的索引不一定每次都能都能生效，在一些特定的情况下索引可能失效。
索引失效场景包含如下几类：
- 对索引列进行运算，一定会导致索引失效。
- 在索引列上使用内置函数，一定会导致索引失效。
where语句中包含or时，可能会导致索引失效。where语句中索引列使用了负向查询(NOT、!=、<>、!<、!>、NOT IN、NOT LIKE)，可能会导致索引失效。like通配符可能会导致索引失效，未满足最左匹配原则。- 隐式类型转换导致的索引失效，如索引列
user_id为varchar类型，使用int做条件关联，或者关联表字符集编码不一致。- 索引字段可以为
null，使用is null或is not null时，可能会导致索引失效。- 联合索引未满足最左匹配原则，
(k1,k2,k3)相当于创建了(k1)、(k1,k2)和(k1,k2,k3)三个索引。
这里以索引运算为例，先准备如下测试表并构造一些测试数据。
CREATE TABLE `tb_user` (
`Column1` varchar(100) NOT NULL,
`Column2` varchar(100) DEFAULT NULL,
PRIMARY KEY (`Column1`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
完成后通过主键执行条件查询，通过执行计划中的 type 与 key 可以看到语句使用了主键索引进行查询。
现在让我们更换一下查询条件，将条件中的 '1' 替换为 1 并重新查询执行计划，可以看到此时 type = ALL 执行了全表扫描，而这则是因为 Column1 字段类型为 varchar，当通过数字 1 查询时 MySQL 会执行隐式的类型转化从而导致索引失效。
上述中提到的其余几类索引失效场景这里就不一一进行介绍，感兴趣的话可以自行通过执行计划进行验证。
