电子商务如何做网站销售,下载的网站模板怎么修改,数商云怎么样,开网店的流程和费用认识Redis Redis是一种基于内存的数据库#xff0c;对数据的读写操作都是在内存中完成的#xff0c;因此读写速度非常快#xff0c;常用于缓存#xff0c;消息队列#xff0c;分布式锁等场景。 Redis提供了多种数据类型来支持不同的业务场景#xff0c;比如String(字符串…认识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 的 QPSQuery 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];}
}
