【2.22】MySQL、Redis、动态规划

认识Redis

• Redis是一种基于内存的数据库，对数据的读写操作都是在内存中完成的，因此读写速度非常快，常用于缓存，消息队列，分布式锁等场景。

• Redis提供了多种数据类型来支持不同的业务场景，比如String(字符串)、Hash(哈希)、 List (列表)、Set(集合)、Zset(有序集合)，并且对数据类型的操作都是原子性的。

  • 原子性：因为Redis是单线程的，不存在并发竞争问题。

• 除此之外，Redis 还支持事务 、持久化、Lua 脚本、多种集群方案（主从复制模式、哨兵模式、切片机群模式）、发布/订阅模式，内存淘汰机制、过期删除机制等等。

Redis和Memcached有什么区别？

• 相同点

  • 都是基于内存的数据库，一般都用来当做缓存使用。
  • 都有过期策略
  • 两者的性能都非常高。

• 区别

  • Redis的数据结构更加丰富，Memcached只支持key-value数据类型；

  • Redis 支持数据的持久化，可以将内存中的数据保持在磁盘中，重启的时候可以再次加载进行使用，而 Memcached 没有持久化功能，数据全部存在内存之中，Memcached 重启或者挂掉后，数据就没了；

  • Redis 原生支持集群模式，Memcached 没有原生的集群模式，需要依靠客户端来实现往集群中分片写入数据；

  • Redis 支持发布订阅模型、Lua 脚本、事务等功能，而 Memcached 不支持；

为什么用Redis作为MySQL的缓存？

• 主要是因为Redis 具备「高性能」和「高并发」两种特性。

  • 假如用户第一次访问 MySQL 中的某些数据。这个过程会比较慢，因为是从硬盘上读取的。将该用户访问的数据缓存在 Redis 中，这样下一次再访问这些数据的时候就可以直接从缓存中获取了，操作 Redis 缓存就是直接操作内存，所以速度相当快。

  • 单台设备的 Redis 的 QPS（Query Per Second，每秒钟处理完请求的次数） 是 MySQL 的 10 倍，Redis 单机的 QPS 能轻松破 10w，而 MySQL 单机的 QPS 很难破 1w。直接访问 Redis 能够承受的请求是远远大于直接访问 MySQL 的，所以我们可以考虑把数据库中的部分数据转移到缓存中去，这样用户的一部分请求会直接到缓存这里而不用经过数据库。

从数据页的角度看B + 树

InnoDB是如何存储数据的？

• InnoDB的数据是按照数据页为单位来读写的，默认的大小是16KB。
• 数据页由以下七个部分组成：File Header文件头、Page Header页头、UserRecords用户空间 、Infimum + Supermum最大 + 最小记录、Free + Space空闲空间、PageDirectory页目录、File Trailer文件尾。
• 数据页中的文件头有两个指针，分别指向上一个和下一个数据页。连接起来的数据页相当于一个双向链表。实现逻辑上的连续存储。数据页中的记录按照主键的顺序组成单向链表。
• 数据页中的页目录起到记录的索引作用。页目录由多个槽组成，槽相当于分组记录的索引。我们通过槽查找记录时，可以使用二分法快速定位要查询的记录在哪个槽（哪个记录分组），定位到槽后，再遍历槽内的所有记录，找到对应的记录，槽对应的值都是这个组的主键最大的记录。
• 在页的 7 个组成部分中，我们自己存储的记录会按照我们指定的行格式存储到 User Records 部分。一开始生成页的时候，并没有 User Records 这个部分，每当我们插入一条记录，都会从 Free Space 部分申请一个记录大小的空间划分到 User Records 部分。当 Free Space 部分的空间全部被 User Records 部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了。

B + 树是如何进行查询的？

• B + 树的每个节点都是一个数据页。B + 树只有叶子节点才会存放数据，非叶子节点仅用来存放目录项作为索引。所有节点按照索引键大小排序，构成双向链表，便于范围查找。

• 定位记录所在哪一个页时，B + 树通过二分法快速定位到包含该记录的页。定位到该页后，又会在该页内进行二分法快速定位记录所在的分组（槽号），最后在分组内进行遍历查找。

• 索引又可以分成聚簇索引和非聚簇索引（二级索引），它们区别就在于叶子节点存放的是什么数据：

  • 聚簇索引的叶子节点存放的是实际数据，所有完整的用户记录都存放在聚簇索引的叶子节点；

    • 因为表的数据都是存放在聚簇索引的叶子节点里，所以 InnoDB 存储引擎一定会为表创建一个聚簇索引，且由于数据在物理上只会保存一份，所以聚簇索引只能有一个
    • InnoDB 在创建聚簇索引时，会根据不同的场景选择不同的列作为索引：
      • 如果有主键，默认会使用主键作为聚簇索引的索引键；
      • 如果没有主键，就选择第一个不包含 NULL 值的唯一列作为聚簇索引的索引键；
      • 在上面两个都没有的情况下，InnoDB 将自动生成一个隐式自增 id 列作为聚簇索引的索引键；

  • 二级索引的叶子节点存放的是主键值，而不是实际数据。

    • 一张表只能有一个聚簇索引，那为了实现非主键字段的快速搜索，就引出了二级索引（非聚簇索引/辅助索引），它也是利用了 B+ 树的数据结构，但是二级索引的叶子节点存放的是主键值，不是实际数据。

为什么MySQL采用B + 树作为索引？

怎样的索引的数据结构是好的？

• MySQL的数据是持久化的，保存在磁盘上。磁盘读写的最小单位是扇区，扇区只有512B大小，操作系统会读写多个扇区，最小的读取单位是块。Linux中块的大小为4KB，也就是8个扇区。由于数据库的索引是保存在磁盘上的，所以查询数据时，要先读取索引到内存，通过索引找到磁盘中的某行数据，然后读入到内存，I/O操作次数越多，所消耗的时间也越大。所以设计MySQL索引的数据结构时，要尽可能减少磁盘I/O次数，并且能够高效地查找某一个记录，也要能高效的范围查找。
• 为什么不用二分查找树？
  • 二叉查找树的特点是一个节点的左子树的所有节点都小于这个节点，右子树的所有节点都大于这个节点，搜索速度块，解决了插入新节点的问题，但是当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)。
  • 随着插入元素越多，树的高度也就越高，磁盘IO操作也就越多，查询性能严重下降。
• 为什么不用自平衡二叉树（AVL树）？
  • 自平衡二叉树在二叉查找树的基础上增加了一些条件约束：每个节点的左子树和右子树的高度差不能超过 1。但是随着插入的元素变多，会导致树的高度变高，磁盘IO操作次数就会变多，影响整体数据查询效率。
• 为什么不用B树？
  • B树解决了树的高度问题，但是B树的每个节点都包含数据（索引+记录），而用户记录的数据大小有可能远远超过索引数据，就要花费更多的IO来读取到有用的索引数据。
• B + 树
  • B + 树对B树进行了升级，与B树的区别主要是以下几点：
    • 叶子节点（最底部的节点）才会存放实际数据（索引+记录），非叶子节点只会存放索引；
    • 所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；
    • 非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。
    • 非叶子节点中有多少个子节点，就有多少个索引；
  • B树进行单个索引查询时，最快可以在O(1)的时间内就找到，平均时间会比B + 树快，但是B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比既存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少。
  • B+ 树有大量的冗余节点，这样使得删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点，这样删除非常快，B树没有冗余节点，在删除节点时，可能涉及到复杂的树的变化。
  • B+ 树所有叶子节点间还有一个链表进行连接，这种设计对范围查找非常有帮助

MySQL中的B + 树

• Innodb 使用的 B+ 树有一些特别的点，比如：
  • B+ 树的叶子节点之间是用「双向链表」进行连接，这样的好处是既能向右遍历，也能向左遍历。
  • B+ 树点节点内容是数据页，数据页里存放了用户的记录以及各种信息，每个数据页默认大小是 16 KB。
• Innodb 根据索引类型不同，分为聚集和二级索引。他们区别在于，聚集索引的叶子节点存放的是实际数据，所有完整的用户记录都存放在聚集索引的叶子节点，而二级索引的叶子节点存放的是主键值，而不是实际数据。

总结

• MySQL 默认的存储引擎 InnoDB 采用的是 B+ 树作为索引的数据结构，原因有：
  • B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少。
  • B+ 树有大量的冗余节点（所有非叶子节点都是冗余索引），这些冗余索引让 B+ 树在插入、删除的效率都更高，比如删除根节点的时候，不会像 B 树那样会发生复杂的树的变化；
  • B+ 树叶子节点之间用链表连接了起来，有利于范围查询，而 B 树要实现范围查询，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。

动态规划

LeetCode

• leetcode 518

  注意，该题是求组合数，所以用递推公式：dp[j] += dp[j - coins[i]]。

  在求装满背包有几种方案的时候，难点在于遍历顺序：

  如果求组合数就是外层for循环遍历物品，内层for遍历背包。（正常遍历顺序，组合数不分数字先后）

  如果求排列数就是外层for遍历背包，内层for循环遍历物品。

  class Solution {public int change(int amount, int[] coins) {int n = coins.length;int dp [] = new int [amount + 1];dp[0] = 1;for(int i = 0 ;i < n;i ++){for(int j = coins[i]; j <= amount; j ++){dp[j] += dp[j - coins[i]];}}return dp[amount];}   
  }
  

• leetcode377

  class Solution {public int combinationSum4(int[] nums, int target) {//dp[j]的含义：当总和为j时的组合数个数。//由于顺序不同的序列被视作不同的组合。所以先遍历容量，后遍历物品。int dp [] = new int [target + 1];dp[0] = 1;for(int j = 0; j <= target ; j++){for(int i = 0 ; i < nums.length ; i ++){if(j >= nums[i]){dp[j] += dp[j - nums[i]];}}}return dp[target];}
  }
  

• leetcode322

  class Solution {public int coinChange(int[] coins, int amount) {//每种硬币无限，完全背包问题。//coins[i]为物品，coins[i]同时也表示重量。//dp[j]： 凑整j的最少硬币个数。 对于dp[j]来说，每个硬币的价值为1。//先遍历物品，再遍历背包。int dp [] = new int [amount + 1];for(int i = 0 ; i < dp.length; i ++){dp[i] = Integer.MAX_VALUE;}dp[0] = 0;for(int i = 0; i < coins.length; i ++){for(int j = coins[i]; j <= amount ; j ++){if(dp[j - coins[i]] != Integer.MAX_VALUE)dp[j] = Math.min(dp[j] , dp[j - coins[i]] + 1);}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}
  }
  

• leetcode279

  完全平方数的大小不可能超过n，所以i* i <= n。同理，背包的容量也不会超过n。

  class Solution {public int numSquares(int n) {//完全平方数就是i * i。int dp [] = new int [n + 1];int max = Integer.MAX_VALUE;for(int i = 0 ; i < dp.length ; i++){dp[i] = max;}dp[0] = 0;for(int i = 1; i * i <= n ; i ++){ //先遍历物品for(int j = i * i ; j <= n ; j ++){     //再遍历背包 dp[j] = Math.min(dp[j] , dp[j - i * i] + 1);}}return dp[n];}
  }