B-树

定义：

1、根节点至少包含两个孩子

2、每个节点最多包含m个孩子(m >= 2)，m为树的深度

3、除了根节点和叶子节点，其他节点至少有ceil(m/2)个孩子，ceil函数为取上限，例如ceil(1.2)=2，就是小数位多少，都入，不是四舍五入

4、叶子节点的高度相同

如果我们需要寻找key为28的数据，会经历3次磁盘I/O操作过程

PS：

1、我们从上图看到B树和二分搜索树有一点相似的地方，数据是有序的，也就是按照关键字进行排序

2、非叶子节点包含key和value，以及指向其子节点地址的指针

3、叶子节点只有key和value

B+树

• 非叶子节点的子树指针与关键字个数相同
• 非叶子节点的子树指针P[i]，指向关键字值的子树
• 非叶子节点仅用来索引，数据都保存在叶子节点中
• 所有叶子节点均有一个链指针指向下一个叶子节点 （紫色块之间有链指针连接，从左到右升序排列）

B+树与B-树的区别

B+树是B树的一种优化
1、B树的每个结点都存储了key和data，B+树的data存储在叶子节点上。非叶子节点不存储data，这样一个节点就可以存储更多的key。可以使得树更矮，磁盘IO操作次数更少。查询效率更高
2、B+树查询路径都是从非叶子结点， 到叶子节点。 效率比较稳定
3、B+树叶子结点是一个链表， 扫描全表数据速度更快（只需要遍历叶子节点，并且范围查询也有优化）

因为B+树的这些好处，在 MySQL 中，MyISAM 引擎和 InnoDB 引擎都是使用 B+Tree 作为索引结构,

但是，两者的实现方式不太一样。MyISAM 引擎是使用的非聚簇索引，InnoDB 引擎使用的是聚簇索引

一棵B+树可以存放多少条数据？

假设B+树高度为2，一行数据记录大小为1k(实际上很多互联网业务数据就是1k左右)，单个叶子节点(页)中记录数16K/1K=16

B+树存在的数据总量 = 根节点节点指针数量 * 每页保存的数据量

假设主键为bigint，长度为8字节，指针大小在InnoDB源码中为6字节，这样一共14字节，我们一个页中存放16384/14=1170。那么一棵高度为

2的B+树，能存放1170*16=18720条这样的数据。

以此类推，一个高度为3的B+树可以存放：1170117016=21902400条这样的记录。

所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

索引类型

按照数据模型维度划分：

1. B-Tree索引：B树索引是MySQL中最常见的索引类型，适用于大部分场景。它支持等值查询、范围查询和前缀匹配。
2. 哈希索引：哈希索引是一种基于哈希表实现的索引，类似键值对的形式，一次即可定位, 等值查询非常快，但是不支持范围查询和前缀匹配
3. 全文索引：全文索引是一种用于文本数据模糊查询的特殊索引，它基于倒排索引实现。目前只有 CHAR、VARCHAR ，TEXT 列上可以创建全文索引。效率较低，通常使用搜索引擎如 ElasticSearch 代替。

从底层存储方式维度划分：

1. 聚簇索引（聚集索引）：索引结构和数据一起存放的索引，InnoDB 中的主键索引就属于聚簇索引。

2. 非聚簇索引（非聚集索引）：索引结构和数据分开存放的索引，二级索引(辅助索引)就属于非聚簇索引。MySQL 的 MyISAM 引擎，不管主键还是非主键，使用的都是非聚簇索引。

聚簇索引(密集索引)

行数据和主键索引存储在一起，辅助键索引只存储辅助键和主键，而不保存数据

InnoDB使用的是聚簇索引，行数据保存在叶子节点上。如果通过where id = 5，直接通过主键索引找到对应的关键字，然后返回行数据

如果通过where name = tom，首先通过辅助键索引找到对应id = 5，然后再通过主键索引找到行数据

PS：

1).如果存在主键，主键就是密集索引

2).如果没有主键，表中第一个唯一非空索引为密集索引

3).如果以上都没有，InnoDB生成一个隐藏主键作为密集索引，是一个6字节的列，随着数据的插入自增

所以，InnoDB必须有个密集索引，这是因为非主键索引叶子节点不保存行数据，而是保存着主键值

非聚簇索引(稀疏索引)：

B+树叶子节点存储的是指向数据的指针

MyISAM使用的为非聚簇索引，主键索引保存了主键，非主键索引保存了非主键，而数据行保存在其他位置，检索的过程都是通过叶子节点内

保存的地址找到对应的数据行。

InnoDB为什么使用聚簇索引呢？

从上面索引过程我们可以看到，对于非主键查询来说，聚簇索引需要经过两次检索，好像效率更低了，那么聚簇索引的优势在哪？

1、行数据和叶子节点保存在一起，会一起被加载到内存，找到叶子节点就可以将数据库返回。

2、辅助索引的叶子节点保存主键的指针，而不使用地址值作为指针，减少了当出现行移动或者数据页分裂时辅助索引的维护工作，使用主键

值当作指针会让辅助索引占用更多的空间，InnoDB在移动行时无须更新辅助索引中的这个"指针"。也就是说行的位置（实现中通过16K的Page来定

位，后面会涉及）会随着数据库里数据的修改而发生变化（前面的B+树节点分裂以及Page的分裂），使用聚簇索引就可以保证不管这个主键B+树的

节点如何变化，辅助索引树都不受影响。

页page:

InnoDB数据通过page存储，是最小的存储单位，page默认大小为16k，文件系统最小单位块为4k，通过下面参数设置

](https://img2018.cnblogs.com/blog/1351999/201907/1351999-20190709112105625-1669802737.png)

页可以用来存储数据也可以用来存储key和指针，分别对应非叶子节点和叶子节点。通过非叶子节点的二分查找和指针确定数据在哪一页，进

而查到对应的数据。

索引概念

MySQL中InnoDB引擎要求每张表都有要有一个聚簇索引（clustered index），也称为主键索引（primary key index），它的作用是将数据按照主键值排序，方便快速地访问单条记录。除了聚簇索引外，MySQL还可以有多辅助（二级）索引（secondary index），它们的作用是加速查询和排序操作。

回表查询

InnoDB索引有聚簇索引和辅助索引。聚簇索引的叶子节点存储行记录，InnoDB必须要有，且只有一个。

辅助索引的叶子节点存储的是主键值和索引字段值，通过辅助索引无法直接定位行记录，通常情况下，需要扫码两遍索引树。先通过辅助索引定位主键值，然后再通过聚簇索引定位行记录，这就叫做回表查询，它的性能比扫一遍索引树低。

主键索引

数据表的主键列使用的就是主键索引。B+Tree的叶子节点存放的是主键字段值

通常说的主键索引就是聚簇索引。InnoDB的表要求必须要有聚簇索引：
● 如果表定义了主键，则主键索引就是聚簇索引
● 如果表没有定义主键，则第一个非空unique列作为聚簇索引
● 否则InnoDB会从建一个隐藏的row-id作为聚簇索引

检索过程： 直接通过主键索引找到存储的数据

二级索引(辅助索引)

InnoDB二级索引，也叫作辅助索引，是根据索引列构建 B+Tree结构。但在 B+Tree 的叶子节点中只存了索引列和主键的信息。二级索引占用的空间会比聚簇索引小很多， 通常创建辅助索引就是为了提升查询效率。一个表InnoDB只能创建一个聚簇索引，但可以创建多个辅助索引。

检索过程： 先通过辅助索引找到主键索引， 通过回表查询，然后再找到存储的数据

索引覆盖

在MySQL官网，类似的说法出现在explain查询计划优化章节，即explain的输出结果Extra字段为Usingindex时，能够触发索引覆盖。

只需要在一棵索引树上就能获取SQL所需的所有列数据，无需回表，速度更快，这就叫做索引覆盖。实现索引覆盖最常见的方法就是：将被查询的字段，建立到组合索引。

最左匹配原则

复合索引使用时遵循最左匹配原则，最左匹配顾名思义，就是最左优先，即查询中使用到最左边的列，那么查询就会使用到索引，如果从索引的第二列开始查找，索引将失效。

索引下推

我们以市民表的联合索引（name, age）为例。如果现在有一个需求：检索出表中“名字第一个字是张，而且年龄是 10 岁的所有男孩”。那么，SQL 语句是这么写的：

mysql> select * from tuser where name like '张%' and age=10 and ismale=1; 

你已经知道了前缀索引规则，所以这个语句在搜索索引树的时候，只能用 “张”，找到第一个满足条件的记录 ID3。当然，这还不错，总比全表扫描要好。 然后呢？ 当然是判断其他条件是否满足。 在 MySQL 5.6 之前，只能从 ID3 开始一个个回表。到主键索引上找出数据行，再对比字段值。 而 MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

图 3 无索引下推执行流程

图 4 索引下推执行流程

在图 3 和 4 这两个图里面，每一个虚线箭头表示回表一次。 图 3 中，在 (name,age) 索引里面我特意去掉了 age 的值，这个过程 InnoDB 并不会去看 age 的值，只是按顺序把“name 第一个字是’张’”的记录一条条取出来回表。因此，需要回表 4 次。 图 4 跟图 3 的区别是，InnoDB 在 (name,age) 索引内部就判断了 age 是否等于 10，对于不等于 10 的记录，直接判断并跳过。在我们的这个例子中，只需要对 ID4、ID5 这两条记录回表取数据判断，就只需要回表 2 次。

索引为什么会失效

1. 列类型不匹配：如果索引列和查询条件的数据类型不匹配，例如在一个字符串类型的索引列上执行了数值比较，那么索引就会失效。
2. 函数操作：如果查询条件中使用了函数操作，例如在索引列上使用函数操作或者使用了自定义函数，那么索引也会失效。
3. 索引列值为空：如果查询条件中使用了IS NULL或者IS NOT NULL操作，那么如果索引列上存在NULL值，那么索引就会失效。
4. 表达式操作：如果查询条件中使用了表达式操作，例如对索引列进行加减乘除等操作，那么索引也会失效。
5. 隐式类型转换：如果查询条件中使用了隐式类型转换，例如在一个字符串类型的索引列上执行了数值比较，并且数据库自动将字符串转换为数字类型，那么索引也会失效。
6. 数据量太大：如果表中的数据量太大，那么对于一些非唯一索引列，索引的查询优化器可能会认为扫描整个表比使用索引更加高效，从而导致索引失效。
7. 索引列上存在函数：如果索引列上使用了函数，例如在索引列上使用了UPPER()函数，那么索引也会失效。
8. 最左匹配原则：联合索引要正确使用需满足最左匹配原则，即：符合第一列才会继续判断后面的字段。
9. 使用OR 一列不是索引

正确使用索引

1. 索引字段占用空间越小越好， 大文本，大对象不要创建索引

2. 索引并不是越多越好， 有维护成本，空间成本

   建议单表不超过5个索引

3. 频繁更新的字段不适合作为索引

4. 我们创建索引的字段应该是查询操作非常频繁的字段。

5. 频繁需要排序的字段：索引已经排序，这样查询可以利用索引的排序，加快排序查询时间。

如何分析sql使用索引情况

在 MySQL 中可以通过 EXPLAIN 关键字模拟优化器执行 SQL语句

explain select 列名 FROM 表名 WHERE 条件 ;

EXPLAIN输出内容如下：

各个字段的含义如下：

列名	含义
id	SELECT的查询序列号
select_type	主要用来说明查询的类型：普通查询、联合查询、子查询等
table	输出的行所引用的表
partitions	如果查询是基于分区表的话，显示查询将访问的分区。，对于未分区的表，值为 NULL
type	代表访问类型，是判断sql执行性能比较关键的一个字段
possible_keys	MySQL可能使用的键(索引)。
key	MySQL实际决定使用的键(索引)。如果没有选择索引,键是NULL。
key_len	所选索引的长度
ref	表示索引的哪一列被使用 显示使用哪个列或常数与key一起从表中选择行。
rows	预计要读取的行数
filtered	按表条件过滤后，留存的记录数的百分比
Extra	附加信息

---

type

联接类型。下面给出各种联接类型,按照从最佳类型到最坏类型进行排序:

type代表访问类型，是判断sql执行性能比较关键的一个字段，性能从高到低依次是：
system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL

• system:表仅有一行(=系统表)。这是const联接类型的一个特例。
• const:表最多有一个匹配行,它将在查询开始时被读取。因为仅有一行,在这行的列值可被优化器剩余部分认为是常数。const表很快,因为它们只读取一次!
• eq_ref:对于每个来自于前面的表的行组合,从该表中读取一行。这可能是最好的联接类型,除了const类型。
• ref:对于每个来自于前面的表的行组合,所有有匹配索引值的行将从这张表中读取。
• ref_or_:该联接类型如同ref,但是添加了MySQL可以专门搜索包含NULL值的行。
• index_merge:该联接类型表示使用了索引合并优化方法。
• unique_subquery:该类型替换了下面形式的IN子查询的ref: value IN (SELECT primary_key FROM single_table WHERE some_expr) unique_subquery是一个索引查找函数,可以完全替换子查询,效率更高。
• index_subquery:该联接类型类似于unique_subquery。可以替换IN子查询,但只适合下列形式的子查询中的非唯一索引: value IN (SELECT key_column FROM single_table WHERE some_expr)
• range:只检索给定范围的行,使用一个索引来选择行。
• index:该联接类型与ALL相同,除了只有索引树被扫描。这通常比ALL快,因为索引文件通常比数据文件小。
• ALL:对于每个来自于先前的表的行组合,进行完整的表扫描，说明查询就需要优化了。

一般来说，得保证查询至少达到range级别，最好能达到ref。