MySQL

标签（空格分隔）： 数据库

1. B树和B+树

1.1 B树

1.1.1 定义

自平衡多路查找树（m路）。基本操作不在本篇范围内，可见参考资料链接。

1.1.2 特性

  • 所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。
  • 每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。（每个结点包含多对key、value）
  • 每个结点最多有m-1个关键字。
  • 非根结点至少有Math.ceil(m/2)-1个关键字。
  • 根结点最少可以只有1个关键字。

1.2 B+树

1.2.1 定义

自平衡多路查找树（m路）

1.2.2 特性

  • 所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。
  • B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。
    • 内部结点：内部结点不保存数据，只用于索引；内部结点中的key都按照从小到大的顺序排列
    • 叶子结点：所有数据（或者说记录）都保存在叶子结点中；左树中的所有key都小于它，右子树中的key都大于等于它；每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。（用于区间搜索）。
  • m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。

1.3 二者差别

  • B+树结点分为了内部结点和叶子结点
  • 由于内部结点没有数据，只有关键字，所以可以容纳更多的路数，高度越低，搜索次数越少，搜索效率越高
  • 叶子结点都有下一个相邻结点的指针，用于区间搜索，效率高

B树、B+树的插入删除

2. B+树在数据库索引的应用

在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引，而这种数据结构是用B+树来实现的。

2.1为什么要选择B+树作为数据库索引的数据结构

2.1.1 背景

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

2.1.2 更少的查找次数

平衡树特性：平衡树查找操作的时间复杂度和树高 h 相关，O(h)=O(logdN)，其中 d 为每个节点的出度。

红黑树的出度为 2，而 B+ Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多，查找的次数也就更多。

2.1.3 利用磁盘结构和预读特性

磁盘预读：为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是利用了局部性原理，每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的旋转时间，速度会非常快。

磁盘结构：操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页（4K），内存与磁盘以页为单位交换数据。

数据库系统将B+树的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。并且可以利用预读特性，相邻的节点也能够被预先载入。这样相比于磁盘IO，内存比较可以忽略不记。

2.2 不同存储引擎的实现

2.2.1 MyISAM索引

实现（三个文件：表定义文件、表数据文件、索引文件）

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。

分为主索引、辅助索引，在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

2.2.2 InnoDB索引

实现（两个文件：表定义文件、数据与索引文件）

虽然InnoDB也使用B+Tree作为索引结构，但实现方式不同。第一，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

分为主索引、辅助索引，与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域，即为非聚簇索引，而主索引为聚簇索引。

2.2.3 总结

相同： 都是B+树作为索引结构

不相同： 前者叶子结点data域存放的是数据记录的地址，后者是记录本身；InnoDB的所有辅助索引都引用主键作为data域。

2.3 索引类型

2.3.1 按数据结构

  • B+Tree 索引

  • 哈希索引

    • 哈希索引能以 O(1) 时间进行查找，但是失去了有序性：无法用于排序与分组；只支持精确查找，无法用于部分查找和范围查找。
    • InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。

  • 全文索引：MyISAM 存储引擎支持全文索引，用于查找文本中的关键词，而不是直接比较是否相等。查找条件使用 MATCH AGAINST，而不是普通的 WHERE。

  • 空间数据索引：MyISAM 存储引擎支持空间数据索引（R-Tree），可以用于地理数据存储。空间数据索引会从所有维度来索引数据，可以有效地使用任意维度来进行组合查询。

2.3.2 按物理结构

  • 聚集索引
  • 非聚集索引

2.3.3 按逻辑

  • 主键索引
  • 唯一索引或者非唯一索引
  • 普通索引
  • 复合索引
  • 全文索引
  • 空间索引

2.4 索引优化

2.4.1 索引优化

单列索引

  • 精确匹配。
  • 匹配索引列的前缀字符串。

复合索引

  • 全列匹配：当按照索引中所有列进行精确匹配（这里精确匹配指“=”或“IN”匹配）时，索引可以被用到。理论上索引对顺序是敏感的，但是由于MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引
  • 最左前缀原则
    • 当查询条件精确匹配索引的左边连续一个或几个列时，如<emp_no>或<emp_no, title>，所以可以被用到，但是只能用到一部分，即条件所组成的最左前缀。
    • 查询条件用到了索引中列的精确匹配，但是中间某个条件未提供。那么也只会用到最左前缀连续的索引，此时索引用一部分，条件中最左前缀。
    • 查询条件没有指定索引第一列，那么不符合最左前缀原则
    • 范围查询。范围列可以用到索引（前提必须是最左前缀），但是范围列后面的列无法用到索引。同时，索引最多用于一个范围列，因此如果查询条件中有两个范围列则无法全用到索引。
    • 匹配某列的前缀字符串，前提是查询中前一列或者多列精确匹配索引的最左前缀

为何需要复合索引：

  • 建了一个(a,b,c)的复合索引，那么实际等于建了(a),(a,b),(a,b,c)三个索引，因为每多一个索引，都会增加写操作的开销和磁盘空间的开销。
  • 索引列越多，通过索引筛选出的数据越少，而这也是由业务需求决定的。
  • 覆盖索引。这减少了很多的随机io操作。

覆盖索引

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

优点：

  • 索引通常远小于数据行的大小，只读取索引能大大减少数据访问量。
  • 对于 InnoDB 引擎，若辅助索引能够覆盖查询，则无需访问主索引。
  • 一些存储引擎（例如 MyISAM）在内存中只缓存索引，而数据依赖于操作系统来缓存。因此，只访问索引可以不使用系统调用（通常比较费时）。

索引不当使用：

  • 如果查询条件中含有函数或表达式，则MySQL不会为这列使用索引。
  • 应该尽量与使用业务无关的自增字段作为主键。如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置。

2.4.2 索引的优点

  • 大大减少了服务器需要扫描的数据行数。

  • 帮助服务器避免进行排序和分组，以及避免创建临时表（B+Tree 索引是有序的，可以用于 ORDER BY 和 GROUP BY ）

  • 将随机 I/O 变为顺序 I/O（B+Tree 索引是有序的，会将相邻的数据都存储在一起）。

2.4.3 索引的使用条件

对于非常小的表、大部分情况下简单的全表扫描比建立索引更高效；对于中到大型的表，索引就非常有效；但是对于特大型的表，建立和维护索引的代价将会随之增长。这种情况下，需要用到一种技术可以直接区分出需要查询的一组数据，而不是一条记录一条记录地匹配，例如可以使用分区技术。

3. 查询优化

3.1 使用 Explain 进行分析

MySQL 性能优化神器 Explain 使用分析

3.2 优化数据访问

3.2.1 减少请求的数据量

  • 只返回必要的列：最好不要使用 SELECT * 语句。
  • 只返回必要的行：使用 LIMIT 语句来限制返回的数据。
  • 缓存重复查询的数据：使用缓存可以避免在数据库中进行查询，特别在要查询的数据经常被重复查询时，而不经常更新的情况，缓存带来的查询性能提升将会是非常明显的。

3.2.2 减少服务器端扫描的行数

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

3.3 重构查询方式

3.3.1 切分大查询

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

3.3.2 分解大连接查询

将一个大连接查询分解成对每一个表进行一次单表查询，然后在应用程序中进行关联，大查询锁住很多数据、占满整个事务日志、耗尽系统资源、阻塞很多小的但重要的查询。

好处：

  • 减少锁竞争；
  • 让缓存更高效。对于连接查询，如果其中一个表发生变化，那么整个查询缓存就无法使用。而分解后的多个查询，即使其中一个表发生变化，对其它表的查询缓存依然可以使用。
  • 分解成多个单表查询，这些单表查询的缓存结果更可能被其它查询使用到，从而减少冗余记录的查询。

4. 结构优化

4.1 整型

TINYINT, SMALLINT, MEDIUMINT, INT, BIGINT 分别使用 8, 16, 24, 32, 64 位存储空间，一般情况下越小的列越好。
INT(11) 中的数字只是规定了交互工具显示字符的个数，对于存储和计算来说是没有意义的。

4.2 浮点数

FLOAT 和 DOUBLE 为浮点类型，DECIMAL 为高精度小数类型。CPU 原生支持浮点运算，但是不支持 DECIMAl 类型的计算，因此 DECIMAL 的计算比浮点类型需要更高的代价。

FLOAT、DOUBLE 和 DECIMAL 都可以指定列宽，例如 DECIMAL(18, 9) 表示总共 18 位，取 9 位存储小数部分，剩下 9 位存储整数部分。

4.3 字符串

主要有 CHAR 和 VARCHAR 两种类型，一种是定长的，一种是变长的。（参数填的是字符个数）
VARCHAR 这种变长类型能够节省空间，因为只需要存储必要的内容。但是在执行 UPDATE 时可能会使行变得比原来长，当超出一个页所能容纳的大小时，就要执行额外的操作。
CHAR这种定长不够节省空间。但更新时效率高，由于长度是预先分好的，不像VARCHAR超过一个页就要执行额外操作。

如何选择?

  • VARCHAR：字符串长度长，且大于平均长度，长度变化较大；更新少。
  • CHAR：字符串长度短，变化幅度小，较为固定的一个值；更新多。

4.4 时间和日期

DATETIME：

能够保存从 1001 年到 9999 年的日期和时间，精度为秒，使用 8 字节的存储空间。

TIMESTAMP：

和 UNIX 时间戳相同，保存从 1970 年 1 月 1 日午夜（格林威治时间）以来的秒数，使用 4 个字节，只能表示从 1970 年到 2038 年。
应该尽量使用 TIMESTAMP，因为它比 DATETIME 空间效率更高。

5. 切分

5.1 水平切分

水平切分又称为 Sharding，它是将同一个表中的记录拆分到多个结构相同的表中。当一个表的数据不断增多时，Sharding 是必然的选择，它可以将数据分布到集群的不同节点上，从而缓存单个数据库的压力。

5.2 垂直切分

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

5.3 Sharding 策略

  • 哈希取模：hash(key) % N；
  • 范围：可以是 ID 范围也可以是时间范围；
  • 映射表：使用单独的一个数据库来存储映射关系。

5.4 Sharding 存在的问题

  • 事务问题：使用分布式事务来解决，比如 XA 接口。
  • 连接：可以将原来的连接分解成多个单表查询，然后在用户程序中进行连接。
  • ID 唯一性
    • 使用全局唯一 ID（GUID）
    • 为每个分片指定一个 ID 范围

6. 主备模式

6.1 读写分离

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

高性能的原因:
主从服务器负责各自的读和写，极大程度缓解了锁的争用；从服务器可以使用 MyISAM，提升查询性能以及节约系统开销；增加冗余，提高可用性。

mysql-write.png-63kB

6.2 主从复制

  • binlog 线程 ：负责将主服务器上的数据更改写入二进制日志（Binary log）中。
  • I/O 线程 ：负责从主服务器上读取二进制日志，并写入从服务器的重放日志（Replay log）中。
  • SQL 线程 ：负责读取重放日志并重放其中的 SQL 语句。

mysql-copy.png-85kB

7. InnoDB和MyISAM存储引擎的比较

7.1 InnoDB（读写方面）

读：主索引是聚簇索引，在索引中保存了数据，从而避免直接读取磁盘，因此对查询性能有很大的提升。内部做了很多优化，包括从磁盘读取数据时采用的可预测性读、能够加快读操作并且自动创建的自适应哈希索引。

写：能够加速插入操作的插入缓冲区等。

7.2 MyISAM（读写方面）

读：INNODB在做SELECT的时候，要维护的东西比MYISAM引擎多很多。innodb寻址要映射到块，再到行，MYISAM记录的直接是文件的OFFSET，定位比INNODB要快。INNODB还需要维护MVCC一致；虽然你的场景没有，但他还是需要去检查和维护

写：在每次修改执行完成时，不会立即将修改的索引数据写入磁盘，而是会写到内存中的键缓冲区，只有在清理键缓冲区或者关闭表的时候才会将对应的索引块写入磁盘。这种方式可以极大的提升写入性能，但是在数据库或者主机崩溃时会造成索引损坏，需要执行修复操作。

7.3 二者区别

  • 事务：InnoDB 是事务型的，可以使用 Commit 和 Rollback 语句。
  • 并发：MyISAM 只支持表级锁，而 InnoDB 还支持行级锁。
  • 底层索引结构不同（聚簇与非聚簇）
  • 崩溃恢复：MyISAM 崩溃后发生损坏的概率比 InnoDB 高很多，而且恢复的速度也更慢。（MyISAM的写入特点）
  • MyISAM的写入比InnoDB快（MyISAM的写入特点）
  • MyISAM查询速度比InnoDB快（MyISAM的查询特点）
  • 备份：InnoDB 支持在线热备份，MyISAM不支持
  • MyISAM 支持压缩表和空间数据索引。

7.4 应用场景

MyISAM管理非事务表。它提供高速存储和检索，以及全文搜索能力。如果应用中需要执行大量的SELECT查询，那么MyISAM是更好的选择。

InnoDB用于事务处理应用程序，具有众多特性，包括ACID事务支持。如果应用中需要执行大量的INSERT或UPDATE操作，则应该使用InnoDB，这样可以提高多用户并发操作的性能。

8. 参考资料

  • BaronScbwartz, PeterZaitsev, VadimTkacbenko, 等. 高性能 MySQL[M]. 电子工业出版社, 2013.
  • 姜承尧. MySQL 技术内幕: InnoDB 存储引擎 [M]. 机械工业出版社, 2011.
  • CyC的CS-Notes:数据库篇