【数据库】索引

一、索引

MySQL索引

1. B+树索引

是InnoDB引擎默认的索引

• B+树结构
  • B+树是平衡树，即所有叶子节点都在同一层的多叉树
  • 每个节点中key和指针交替排列，两个key之间的指针指向的是大于等于左边key且小于等于右边key的节点
  • 叶子节点顺次连接，所以沿着B+树的叶子节点走能得到按key排序后的数据
• 操作
  • 查找：先在根节点二分查找，找到key所在的指针，递归地去相应的节点继续查找
  • 增删节点：为了维护树的平衡性，需要进行节点的分裂合并，旋转等操作
• 与B树的对比
  • B树中间节点也存数据，没有冗余的索引，而B+树只在叶子节点存数据，key值不止会出现在一个地方，因为节点不存数据，比较小，所以磁盘读写代价更低
  • B树搜索路径是根到中间节点，B+树是根到叶子节点，所以搜索过程比较稳定
• 与红黑树的对比
  • B+树的树高更矮，因为红黑树是二叉树
  • B+树更适合磁盘读取，因为树高低，磁盘寻道次数少
  • B+树叶子节点顺序存储，磁盘预读的特性更适合

2. 哈希索引

InnoDB引擎的索引

有O(1)的查询速度，但是失去了有序性

• 不支持排序和分组
• 只支持精确查找，无法用于范围查找和部分查找

InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找

3. 全文索引

MyISAM引擎的索引，InnoDB也支持

• 用于查找关键词，使用倒排索引实现

主索引和辅助索引

InnoDB 存储引擎根据索引类型不同，分为聚簇索引和二级索引。

它们区别在于，聚簇索引的叶子节点存放的是实际数据，所有完整的用户数据都存放在聚簇索引的叶子节点，而二级索引的叶子节点存放的是主键值，而不是实际数据。

主索引：也叫聚簇索引，指的是叶子节点直接存数据本体的索引

辅助索引：叶子节点存的是索引列-主键，先找索引列对应的主键，找到主键后再到主索引上找数据本体，这个过程叫回表

使用索引时的trick

1. 独立的列

   在进行查询时，索引列不能是表达式的一部分，也不能是函数的参数，否则无法使用索引

   例如下面的查询不能使用 actor_id 列的索引：

SELECT actor_id FROM sakila.actor WHERE actor_id + 1 = 5;
1

2. 多列索引

   在需要使用多个列作为条件进行查询时，使用多列索引比使用多个单列索引性能更好。例如下面的语句中，最好把 actor_id 和 film_id 设置为多列索引

SELECT film_id, actor_ id FROM sakila.film_actor
WHERE actor_id = 1 AND film_id = 1;
1
2

3. 索引列的顺序

   让选择性最强的索引列放在前面

4. 前缀索引

   对于 BLOB、TEXT 和 VARCHAR 类型的列，必须使用前缀索引，只索引开始的部分字符。

   前缀长度的选取需要根据索引选择性来确定

5. 覆盖索引

   索引包含所有需要查询的字段的值

索引失效的情况

1. 查询条件中带有or，除非所有的查询条件都建有索引，否则索引失效

2. like查询是以%开头

   因为索引 B+ 树是按照「索引值」有序排列存储的，只能根据前缀进行比较

   如果前缀有值，可以通过索引缩小范围，但如果是%，无法比较，只能走整个索引

3. 对索引使用函数

   因为索引保存的是索引字段的原始值，而不是经过函数计算后的值，自然就没办法走索引

4. 对索引进行表达式计算

   同上

5. 对索引隐式类型转换

6. 联合索引非最左匹配

   对主键字段建立的索引叫做聚簇索引，对普通字段建立的索引叫做二级索引
   那么多个普通字段组合在一起创建的索引就叫做联合索引，也叫组合索引

   联合索引要能正确使用需要遵循最左匹配原则，也就是按照最左优先的方式进行索引的匹配

   顺序不重要，而是需要相应的字段不缺失

   • 比如，如果创建了一个 (a, b, c) 联合索引，如果查询条件是以下这几种，就可以匹配上联合索引：
     where a=1；
     where a=1 and b=2 and c=3；
     where a=1 and b=2；

   • 但是，如果查询条件是以下这几种，联合索引就会失效:
     where b=2；
     where c=3；
     where b=2 and c=3；

   • 但如果是截断情况，有一个比较特殊的查询条件：where a = 1 and c = 3 ：
     会使用索引下推功能，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

二、查询性能优化

使用 Explain 进行分析

Explain 用来分析 SELECT 查询语句，开发人员可以通过分析 Explain 结果来优化查询语句。

比较重要的字段有：

select_type : 查询类型，有简单查询、联合查询、子查询等
key : 使用的索引
rows : 扫描的行数

优化数据访问

1. 减少请求的数据量

   只返回必要的列：最好不要使用 SELECT * 语句

   只返回必要的行：使用 LIMIT 语句来限制返回的数据

   缓存重复查询的数据：使用缓存可以避免在数据库中进行查询

2. 减少服务器端扫描的行数

   最有效的方式是使用索引来覆盖查询

重构查询方式

1. 切分大查询

一个大查询如果一次性执行的话，可能一次锁住很多数据、占满整个事务日志、耗尽系统资源、阻塞很多小的但重要的查询

删除所有数据

DELETE FROM messages WHERE create < DATE_SUB(NOW(), INTERVAL 3 MONTH);
1

改为一次删除10000行

rows_affected = 0
do {
    rows_affected = do_query(
    "DELETE FROM messages WHERE create  < DATE_SUB(NOW(), INTERVAL 3 MONTH) LIMIT 10000")
} while rows_affected > 0
1
2
3
4
5

2. 分解大连接

将一个大连接查询分解成对每一个表进行一次单表查询，然后在应用程序中进行关联

好处：

• 让缓存更高效。对于连接查询，如果其中一个表发生变化，那么整个查询缓存就无法使用。而分解后的多个查询，即使其中一个表发生变化，对其它表的查询缓存依然可以使用。
• 分解成多个单表查询，这些单表查询的缓存结果更可能被其它查询使用到，从而减少冗余记录的查询。
• 减少锁竞争；
• 在应用层进行连接，可以更容易对数据库进行拆分，从而更容易做到高性能和可伸缩。
• 查询本身效率也可能会有所提升。例如下面的例子中，使用 IN() 代替连接查询，可以让 MySQL 按照 ID 顺序进行查询，这可能比随机的连接要更高效。

三、存储引擎

InnoDB

• 是 MySQL 默认的事务型存储引擎

• 实现了四个标准的隔离级别，默认级别是可重复读（REPEATABLE READ）。在可重复读隔离级别下，通过多版本并发控制（MVCC）+ Next-Key Locking 防止幻影读

• 主索引是聚簇索引

MyISAM

• 不支持事务

• 不支持行级锁，只能对整张表加锁

比较

事务：InnoDB 是事务型的，可以使用 Commit 和 Rollback 语句

并发：MyISAM 只支持表级锁，而 InnoDB 还支持行级锁

外键：InnoDB 支持外键

备份：InnoDB 支持在线热备份

崩溃恢复：MyISAM 崩溃后发生损坏的概率比 InnoDB 高很多，而且恢复的速度也更慢

其它特性：MyISAM 支持压缩表和空间数据索引

四、切分

分库分表

水平切分

水平切分又称为 Sharding，它是将同一个表中的记录拆分到多个结构相同的表中

当一个表的数据不断增多时，Sharding 是必然的选择，它可以将数据分布到集群的不同节点上，从而缓存单个数据库的压力

垂直切分

垂直切分是将一张表按列切分成多个表，通常是按照列的关系密集程度进行切分，也可以利用垂直切分将经常被使用的列和不经常被使用的列切分到不同的表中。

在数据库的层面使用垂直切分将按数据库中表的密集程度部署到不同的库中，例如将原来的电商数据库垂直切分成商品数据库、用户数据库等。

Sharding 存在的问题

1. 事务问题

   使用分布式事务来解决，比如 XA 接口。

2. 连接

   可以将原来的连接分解成多个单表查询，然后在用户程序中进行连接。

3. ID 唯一性

   使用全局唯一 ID（GUID）

   为每个分片指定一个 ID 范围

   分布式 ID 生成器 (如 Twitter 的 Snowflake 算法)

五、主从复制，读写分离

主服务器处理写操作以及实时性要求比较高的读操作，而从服务器处理读操作。

读写分离能提高性能的原因在于：

• 主从服务器负责各自的读和写，极大程度缓解了锁的争用；
• 从服务器可以使用 MyISAM，提升查询性能以及节约系统开销；
• 增加冗余，提高可用性。
• 读写分离常用代理方式来实现，代理服务器接收应用层传来的读写请求，然后决定转发到哪个服务器