存储结构
Hash 索引
- 维护一个kv map，v可以是数据，也可以是数据在磁盘上的位置。
- 一般使用日志文件的偏移量，这样文件的写入就只需要append操作，文件变大后合并。
- 实现简单。
- 必须全部放入内存，在磁盘上维护速度会很慢；区间查询效率不高。
SSTable
- 对哈希日志文件的改进，要求每个文件中的key是有序的。
- 优点：
- 合并更加高效，桶排序可以在文件大于内存的时候正常工作；
- 不需要内存中保存所有key的值，保存部分区间就可以了；
- 可以根据key的前缀对一批key做压缩，节省磁盘空间，I/O带宽变小。
- 相关实现：Cassandra、HBase、Lucene。
- 当写入时，将其添加到内存中的平衡数据结构中（例如红黑树）。
- 当内存大于某个阈值（通常为几兆字节）时，将其作为SSTable文件写入磁盘。
- 为了处理读请求，首先尝试在内存表中查找键，然后是最新的磁盘段文件，接下来是次新的磁盘段文件，以此类推，直到找到目标（或为空）。
- 后台进程周期性地执行段合并与压缩过程，以合并多个段文件，并丢弃那些已被覆盖或删除的值。
B-tree
- B-tree保留按键排序的key-value对，将数据库分解成固定大小的页面，不同页面之间可以互相引用，每个页面对应一个连续的范围，包含若干键和对子页的引用。
- 优点：
- 稳定的性能表现；
- 日志系统的一个key可能在多处出现，而B-tree可以更好地支持事务。
- 几乎所有关系数据库中的标准索引实现，许多非关系型数据库也经常使用。
B+ 树和 B 树的区别：B+ 树把所有数据都存储在叶节点中，而 B 树在非叶子结点也会存储数据。
InnoDB 使用的是 B+ 树，因为 B+ 树对范围查询更高效。
InnoDB 使用 B+ 树：
- 范围查询、顺序读取支持更好，锁的范围更可控。
- 相同数据 B+ 树更矮，IO 更少。
- 方便缓存。
跳表
- 稳定性
- B+ tree的结构、查询和插入过程是稳定的
- 跳表插入时是否要把数放在上一层由随机函数出现
- IO读写
- B+ tree通常用在数据库，B+ tree的树高很低，所以磁盘IO次数会很小
- 跳表用在内存里，没有IO的问题，当然跳表的高度较高，如果放在磁盘中，IO次数会增加。
- 读写操作
- B+ tree适合读多的场景，插入过程较麻烦，但是查找很快。
- 跳表查询时走的层次多，但是插入更快，不需要去平衡数据结构。
- 代码实现
- B+ tree需要考虑很多操作、节点的拆分，合并
- 跳表纯随机，靠概率保证性能，实现起来就不需要考虑很多因素。
InnoDB
MySQL一个table中数据在磁盘上的排列是以clustered index为序的，在没有特殊设置的情况下，clustered index为primary key，如果没有primary key，就会找第一个不允许空值的unique key作为clustered index，还没有的话，db会自己生成一个index。
锁
- Shared and exclusive locks
- 只是锁的类别，没有具体语句。
- Intention locks
- 表级别锁，用来表示一个事务之后会对某些行上什么类别的锁。
- 一个事务获得行锁的必要条件是先获得对应表的，相同或更高等级的意向锁。
- SELECT ... FOR SHARE
- SELECT ... FOR UPDATE
- Record locks
- SELECT c1 FROM t WHERE c1 = 10 FOR UPDATE
- Gap locks
- 在index records之间的gap，或第一个index records之前，第二个index records之后的锁。
- 当搜索条件不是unique index的时候就会用到gap lock。
- SELECT c1 FROM t WHERE c1 BETWEEN 10 and 20 FOR UPDATE;
- Next-key locks
- index-record lock + gap lock preceding the index record.
- Insert intention locks
- insert时施加的gap锁，只要最终操作的index不同就不会互相block。
- AUTO-INC locks
- 特殊的table lock。
- Predicate locks for spatial indexes
- 用在spatial data上，锁的是minimum bounding rectangle values。
索引
- 主键
- 唯一索引，在关系型数据库中给数据施加更多的约束。
- 二级索引，和前两者也类似，但不需要每条记录都有唯一的键。
- 聚集索引，存储数据的具体位置，方便其他索引引用，InnoDB把主键作为聚集索引。
一些逻辑上的索引
- 覆盖索引，索引包含了查询需要的所有字段，这样查到相关数据后，索引值就是结果，不需要回表去查找更多的数据。
MVCC
每行记录包含了两个隐藏字段，事务id trx_id 和回滚指针 roll_pointer。
其中回滚指针指向对应undo log的地址，undo log在每次变动前被创建，相关的记录连在一起就变成了一个版本链。
如果一个事务不应该读取当前的版本，那么这个事务就会通过roll_pointer找到之前的版本。
Index Merge
当一个查询涉及多个索引的时候，优化器会在这两种策略中选择一种去执行
- 根据索引的顺序，先查到第一个索引对应的记录，然后用剩下的索引条件做filter。
- 对多个索引并行对应的主键，merge结果，找到符合要求的记录。
此时多个索引都会加入到锁机制中，很有可能不同类型的索引对应的区间有交叉，这就会带来死锁。
binlog
https://dev.mysql.com/doc/internals/en/binary-log-overview.html
有关数据修改的操作记录，记录了有可能导致数据更新的操作，以及一些相关的metadata。
两种实现方式：
- statement-based
- row-based
用于：
- 主从复制
- 数据恢复
redo log
如果每次事务结束的时候都要去把数据写入磁盘，会非常耗时，而且InnoDB修改的是页，等于是把页块随机IO进磁盘。因此引入了redo log，修改数据前先把修改的具体数据信息追加到log尾部，以减少数据页写入磁盘的频次。
redo log是环形的，一旦写满就要求数据页写入磁盘，然后释放相应的log空间。
如果发生了故障，redo log可以用来追加未写入磁盘的改动。
undo log
记录用来回滚事务需要的信息，MVCC的版本信息也依赖此实现。
事务的级别
- READ UNCOMMITTED，没有事务，或者说事务的中间状态会被其他事务看见。 更新丢失 -> 上锁，CAS 版本号，冲突检测
- READ COMMITTED，事务的中间状态不会被其他事务看见，但是已执行事务的结果会被其他事务看见。 脏读 + 脏写 -> 读提交 -> 读锁 / 直接MMVC。数据的读取在这个隔离级别下是不加锁的。
- REPEATABLE READ，一个事务只会看到结束时间在其开始时间之前的事务操作结果。 不可重复读 / 读倾斜 -> 可重复读 -> MMVC
- SERIALIZABLE 幻读 / 写倾斜 -> 可重复读 or 线性化 -> MMVC & next-key lock + 2PC(开始前拿锁，结束后释放锁) or 线性化
MySQL
为什么选择 MySQL？因为这是个万金油数据库，方便系统迁移，方便私有化部署等。
基础规范
- 一般场景下尽量使用InnoDB存储引擎。
- 新库字符集选择上使用utf8mb4字符集。
- 线上数据库禁止使用存储过程、视图、触发器、Event，在高并发的场景下我们需要去解放DB的CPU，把一些可以上移的计算上移。
使用规范
- 不要使用负向查询（不等于、not in、not like等）以及%开头的模糊查询；这些都会导致索引失效。
- 不要在WHERE条件的字段上直接使用函数或者表达式；比如 from_unixtime(start_day) > '...' 这样也会导致索引失效。
- 不要在WHERE条件的字段使用隐式转换；比如用int value去查询varchar的属性，这也会导致全表扫描。
- 最好不要SELETE *，只获取必要的字段，显示说明列属性。
- 这会增加CPU、IO、net消耗。
- 如果有覆盖索引的情况下，会导致无法有效利用覆盖索引。
- 可能会让字段的改变引发bug。
- 分片库使用场景下，要求在线查询必须带分片键。
优化思路
- 减少数据访问
- Design：减少数据的访问，要从设计阶段就开始思考如何设计紧凑而高效的数据模型，表结构、字段类型、一机构字符编码等细节。
- Index：包含如何建立合理索引和高效地使用索引，理解清楚表的结构以及不同存储引擎的特性。
- SQL Plan：主要是如何写出高效的 SQL 语句，尤其是涉及到复杂的 join 和 sorting。通常可以通过 explain 来查看 SQL 的执行计划和反馈的数据指标，找到优化的切入点。
- Compression：压缩也是用于减少数据访问的常见手段，但通常压缩会引入 CPU 的消耗，具体要看业务场景来取舍。
- 减少数据访问 / 数据传输
- Pagination：绝大多数 OLTP 场景，查询大量数据的时候都可以采用 pagination 手段， MySQL 中常见的就是 Limit + Offset。Pagination 之后，网络传输和 MySQL Server 上从磁盘读数据的多个环节，就可以形成一个 pipeline，有利于更合理地利用磁盘 IOPS 和网络带宽。同时又避免了 MySQL Server 端和应用程序端的大量内存被占用。当然，有时 where 条件就可以很好地进行 pagination，这种情况优先采用 where 条件进行 pagination。
- Result Size：不要查询和传输不必要的数据，比如只查询需要的字段。
- 减少网络传输
- Batch：发送到数据库的每个数据块中的最大值数。建议对访问延迟较大（client 和 MySQL 之间网络 RTT 大）的数据库使用较高的值，当用户数量较多时使用较低的值。
- FetchSize：从数据库中检索的每个数据块中的最大值数。优化建议同上。
- 减少 CPU 运算和内存占用（感觉这个也是可以前期考虑的
- Sort：SQL 中排序是一个耗 CPU 的操作，一方面尽量避免 sort，比如利用索引就是一种避免 sort 的方法。如果索引不奏效，就需要依赖 filesort，二 filesort 的性能又和 sort_buffer_size 参数有关，内存中无法完成 filesort 时还会借助临时文件来完成 sort，临时文件的读写性能又和 tmpdir 参数设置有关。其次要尽量让参与 sort 的数据量比较小。
- Bind Var：不要在 where 里面执行计算，提前把 where 的参数计算好。
- 增加资源
- Parallel：通过增加资源提升并行度，比如向集群中加入更多的服务器，然后迁移部分数据分片到新服务器；如果计算能力足够但 IOPS 不够的情况，给服务器多家一个磁盘控制器，多挂一块磁盘是提升 iOPS 最经济的方式。
- Scale up：比如把 MySQL 迁移到一个 CPU Core 更多的服务器以加强 CPU 计算能力，把 MySQL 从 SAS 磁盘迁移到 NVME-SSD 磁盘等。