1、索引

索引起到加快数据库查询速度的作用。 假设需要查询一条数据， * from user where id = '1'; 如果没有索引，则需要逐条匹配记录，最终匹配到对应的记录。 时间复杂度为O(N)。

如果通过索引查询，以mysql为例，索引是采用B+树结构构建的。 B+树是B树的变体。 该变体的主要目的是减少树的深度和大小，从而减少IO次数，提高效率。 。 B树可以理解为平衡多树，所以在这种数据结构下，查找的时间复杂度可以理解为二分查找的时间复杂度。 同样，上述SQL的时间复杂度为O(log(N))。

B+树和B-树的区别参见：【数据结构】二叉树 平衡二叉树 B-树 B+树

为什么二分查找的时间复杂度是O(logN) 参见：为什么二分查找的时间复杂度是logN

2、索引查询

添加 sql * from user where id = '55';

如果我们要加载id=55的数据，那么

将磁盘块1的数据从磁盘加载到内存中。 这时候就发生IO了。 使用二分查找来确定内存中的55。 50 - 100时，确认磁盘块1的P2指针，并确定磁盘块3的位置。加载磁盘块3数据传输到内存，发生第二次IO，在50和60之间确定55。P2盘块3的指针被锁定，盘块7的位置被确定。 将磁盘块7的数据加载到内存中，发生第三次IO，在内存中进行二分查找确定数据55，结束查询，一共3次IO。

真实情况是3层b+树可以表示数百万数据。 如果百万级数据搜索只需要3次IO，性能提升将是巨大的。 如果没有索引，则每个数据项都会发生一次IO。 ，那么总共需要数百万次IO，这显然是非常非常昂贵的。

2.1. B+树和B树的区别

B树和B+树最大的区别在于数据存储在非叶子节点中。 B树会保存每个节点上的索引值和关键数据，对应磁盘指针地址。 子节点对应磁盘指针地址，而B+树则存储数据。 存储在叶子节点中，非叶子节点只存储索引值，子节点对应磁盘位置。

2.2. 为什么使用B+树？ 降低树的高度：从上面的推导可以得出，如果想要加快索引搜索的速度，就应该尽可能的降低树的高度。 树的深度越深，查询效率越低，因为B+树的所有叶子节点都是水平的，在不考虑缓存的情况下，树结构每增加一个深度就会多增加一次IO。 因此，降低树的高度是需要考虑的核心因素。 B树会将数据指针和关键数据保存在非叶子节点中，这意味着非叶子节点需要比B+树存储更多的数据。 叶子节点中的数据越多，每个叶子节点中的数据就越多。 一个磁盘块存储的数据较少，从而增加了树的高度。 B+树的每个叶子节点都有一个指向下一个叶子节点的指针。 范围查询的实现比较简单，降低复杂度还可以提高查询效率。 3. 指标实施 3.1． 聚集索引

B+树用于实现索引，原始数据本身就是一棵B+树，也称为聚集索引。 因此，每个表数据必须只有一个聚集索引。 聚集索引的B+树在地下。 保存的数据为原始数据，如下图

表结构有3个字段，id int key,name(32),age int,sex(char)； 指数（年龄）

3.2. 辅助索引

辅助索引，也称为二级索引，有时也称为普通索引，它的数据结构也是一棵B+树，但是普通索引叶子节点的数据是聚集索引的值，所以普通索引定位到簇后，需要到聚簇表中再次查询，这就是所谓的回表。 因此，尽量避免使用数据量较大的字段作为聚集索引。 一方面，它会增加聚集索引的高度，更重要的是，它会增加所有辅助索引的大小。 大小，下图是年龄索引的结构。

查询age=30的数据，根据age索引找到聚集索引=1，然后再根据1去聚集索引查找对应的数据。

3.3. 如何避免表返回？

辅助索引定位到聚集索引的值后，如果当前索引数据不能满足返回值，就会发生退表。 即根据聚簇值，在聚簇索引中再次查询数据，如上所示。 以sql为例

id,age from user where Age = 30 不需要返回表，因为id是聚集索引，age是辅助索引。

id,age,sex from user 其中age = 30，需要返回表，因为id是聚集索引，age是辅助索引，sex不在索引数据范围内，需要定位聚集值1根据30岁，然后根据1表检查返回。

如果想避免返回表，可以在age索引后添加sex，将其变成组合索引。 修改索引后，会看到索引如下

再次执行同样的sql，你会发现没有返回表。

4. 索引原则 4.1． 聚集索引

上面提到，辅助索引定位到聚集索引后，需要进行回表操作，所以如果查询可以使用聚集索引，就会优先使用聚集。

基于聚集索引搜索，type = 'const'

指示基于所使用索引的字节数。 因为用户表的主键id是int，int占用4个字节，所以 = 4

4.2. 组合索引最左原则

组合索引的原则是向左匹配。 如果左侧无法匹配，则后续索引字段将不会被索引。 这和B+树的实现有关。 因为组合索引建立后，索引的数据顺序与创建的顺序是一致的。 B+树的生成也是按照这个顺序。 因此，查询时必须先匹配索引排序中的第一个字段，然后再匹配第二个和第三个字段。 个人的。

接下来我们一一分析为什么可以使用索引，为什么不能使用索引。

案例表：

| user  | CREATE TABLE `user` (
  `id` int NOT NULL,
  `a` int DEFAULT NULL,
  `b` varchar(4) DEFAULT NULL,
  `c` char(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx_a_b_c` (`a`,`b`,`c`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci |

在下面的示例中，

a 字段类型为 int null，int 为 4 个字节 b 字段类型为（4）因为我本地 mysql 使用的编码是，1 占用 4 个字符，（4）大小为 4 x 4 = 16 个字节 c 字段类型为 char ( 1）

4.2.1. 其中 a = 3

可以在索引(a,b,c)中使用字段a的索引。

type为ref，表示使用的辅助索引=5。5是因为该字段是a且该字段是int类型，4个字节，加上一个可为空的字段加1个字节，所以等于5。可以推导出来使用组合索引中的多个字段。

4.2.2. 其中 a = 3 且 b = 5

可以使用索引(a,b,c)中字段a和b的索引

是24，a字段是上面计算出来的5个字节，b字段是（4），16字节+2字节变长+1字节可空字段，=5+16+2+1=24

4.2.3. 其中 a = 3、b = 5、c = 4

= 29，a加b就是24。按照上面的计算，1个char就是4个字节，加上可以留空的1个字节（因为char是定长的，所以不需要加上这2个字节），所以最后是24 + 4 + 1 = 29

4.2.4. 其中 b = 5

前面解释过，索引的匹配是从最左边开始的，索引创建是a、b、c。 如果只有b，则索引无法匹配。

索引无法匹配后，就会变成全表扫描，即一次扫描一条记录，type=ALL，这种情况应该尽量避免。

4.2.5. 其中 a = 3 且 c = 4

在这种情况下，c 不能使用上索引，因为没有 b。 a字段可以匹配上索引，所以对应的是4，一个int。

4.2.6. 其中 a = 3 且 b > 5 且 c = 4

a和b可以建立索引，但c不能建立索引

是24，就是a+b的字节数

4.2.6.1. 为什么范围查询后的字段无法建立索引？

以这张图为例，你可以看到

a的数据集为1,1,2,2,3,3

b的数据集为1,2,1,4,1,2

我们看到a的数据范围是一个有序集合，所以在查询B+树时，a字段本身仍然是一棵树。 可以基于二分查找找到数据。 时间复杂度仍然是logN。 当给定 a 范围时，如上图，如果 a >= 0，就会得到 1, 2, 3。 下面 b 的集合不是有序集，也不是树。 无法通过二分查找，所以只能使用。

4.2.6.2. 为什么等式查询之后的范围查询可以建立索引？

再看上面的例子，我们可以发现，当a为固定值时，b一定是有序的，比如

当a = 1时，b = 1,2 当a = 2时，b = 1,4 当a = 3时，b = 1,2

所以a的值确定后，b就是一个有序集合，可以通过二分查找的方式定位并建立索引。

4.2.7. 其中 a = 3 和 b 如 'abc%' 且 c = 4

从=29可以看出，这确实是abc这三个字段的索引，但是为什么range查询后面的字段不能索引，而like条件后面的字段却可以索引呢？

4.2.8. 其中 a = 3 和 b 类似 '%abc' 且 c = 4

通配符出现在开头，索引b无法使用，间接导致c字段无法使用索引。

= 5，代表字段a

4.3. 其他参考原则4.3.1。 包含函数计算的查询条件不能包含在索引中

对查询字段进行函数计算，不能使用索引、type=ALL、全表扫描

4.3.2. 不相等的条件无法建立索引

这个原理和范围查询后的字段不能建立索引是一样的。

4.3.3. 减少磁盘IO读取

假设有一个购物车表，其中包含购物车id、用户id以及其他必要的购物车信息。 在购物车场景中，大部分查询都是通过用户id来查询用户的购物车信息。 我们来看一下索引的创建：

购物车id为主键，用户id用于构建辅助索引。 根据用户id查询时，会返回很多购物车id，从而产生很多表返回。 此外，由于购物车场景，用户可能每隔几天添加一次购物车。 因此，某个用户下的购物车ID可能不在物理上位于磁盘块中，从而会发生多次IO。 使用用户id+购物车id作为主键的优点：与数据查询时使用购物车id作为主键相比，由于用户id在前，集群上的数据更加连续，会减少IO次数查询时读取。 缺点：写入时，由于聚簇的顺序是根据用户id进行的，因此写入数据时，不一定会写入聚簇索引的末尾，这样会导致B+树频繁，牺牲部分写入输入性能。

如何构建索引需要根据当前的业务场景来进行。 如果读多写少，可以覆盖轻读，反之亦然。

4.3.4. 减少表返回

如果需要查询的列可以被索引覆盖，则不要添加额外的查询列。

示例：用户表有一个辅助索引（年龄）。

通过辅助索引查询，当索引能够满足查询数据时，不需要回表，使用索引会在extra中显示。

通过辅助索引查询，当索引不能满足查询数据时，需要返回表。

4.3.5. 减少表返回量

在limit场景下，如果通过二级索引过滤了limit，则会返回到达到limit之前的表。 子查询可用于减少表返回量。

例如sql：

-- 回表之后在进行 limit
select * from user where no in (5934,5935,5936) limit 3000,5;

可以优化为：

-- 先 limit 筛选出 id，然后再回表
select * from user a 
inner join (
  select id from user where no in (5934,5935,5936) limit 3000,5
) b on a.id = b.id;

主意：

优化的思路是先通过子查询或者内连接确定要查询的ID，然后返回表。 这样可以减少表返回量。 如果是原始未优化的SQL，则会在辅助索引中查询所有可能的sql。 id，全部返回到表中。 返回表后发现数据然后限制是3000,5。 其中前3000条数据会被mysql丢弃，比较浪费性能。

原则：

可以通过查看内存缓存页的数据。 桌子。 您可以使用该值来确定有多少数据加载到内存页中。 可以看到，如果该语句通过子查询进行优化，优化前加载到内存的记录数为8.8W。 执行该SQL语句后，缓存页的记录数为49W。

5. 参考文献

/2014/06/30/mysql-index.html

/p/

//-of-mysql-index.html

modb.pro/db/52861

/邮政/