Posts

Dynamic Programming 算法-动态规划 Dynamic Programming–从菜鸟到老鸟-CSDN博客 拆分子问题，记住过往，减少重复计算 1.最优子结构 如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。 2.重叠子问题 在斐波拉契数列和钢条切割结构图中，可以看到大量的重叠子问题，比如说在求fib（6）的时候，fib（2）被调用了5次，在求cut（4）的时候cut（0）被调用了4次。如果使用递归算法的时候会反复的求解相同的子问题，不停的调用函数，而不是生成新的子问题。如果递归算法反复求解相同的子问题，就称为具有重叠子问题（overlapping subproblems）性质。在动态规划算法中使用数组来保存子问题的解，这样子问题多次求解的时候可以直接查表不用调用函数递归。 自顶向下备忘录 自底向上动态规划 public int minPathCost(int[][] grid, int[][] moveCost) { int[] cost = new int[grid[0].length]; int min_cost = 0x7fffffff; for(int i=0;i<cost.length;i++){ cost[i] = grid[grid.length-1][i]; } // hop loop for(int i=grid.length-2;i>=0;i--){ // update cost loop for(int j=0;j<cost.length;j++){ min_cost = 0x7fffffff; for(int k=0;k<moveCost[grid[i][j]].length;k++){ min_cost = Math.min(moveCost[grid[i][j]][k]+grid[i][j], min_cost); } cost[j] = min_cost; } } for(int i=0;i<cost.length;i++){ min_cost = Math.min(min_cost, cost[i]); } return min_cost; }

Git 1 使用 1.1 初始化仓库 git init git clone [url] directoryName 1.2 记录每次更新 检测文件状态：git status 将文件加入到暂存区：git add filename 忽略文件：.gitignore 提交更新：git commot -m ”message” 跳过使用暂存区域更新方式：git commit -a -m “message” 从暂存区移除文件：git rm filename 对文件重命名：git mv README.md README（相当于 mv README.md README, git rm README.md, git add README） 1.3 推送改动到远程仓库 链接远程服务器：git remote add origin 提交改动 git push origin master 1.4 远程仓库的移除与重命名 git remote rename test test1 git remote rm test1 1.5 查看提交历史 git log –author=name...

MongoDB MongoDB 是一个基于 分布式文件存储 的开源 NoSQL 数据库系统，由 C++ 编写的。MongoDB 提供了 面向文档 的存储方式，操作起来比较简单和容易，支持“无模式”的数据建模，可以存储比较复杂的数据类型，是一款非常流行的 文档类型数据库 。 在高负载的情况下，MongoDB 天然支持水平扩展和高可用，可以很方便地添加更多的节点/实例，以保证服务性能和可用性。在许多场景下，MongoDB 可以用于代替传统的关系型数据库或键/值存储方式，皆在为 Web 应用提供可扩展的高可用高性能数据存储解决方案。 1 MongoDB基础 1.1 MongoDB存储结构 MongoDB 的存储结构区别于传统的关系型数据库，主要由如下三个单元组成： 文档（Document）：MongoDB 中最基本的单元，由 BSON 键值对（key-value）组成，类似于关系型数据库中的行（Row）。 集合（Collection）：一个集合可以包含多个文档，类似于关系型数据库中的表（Table）。 数据库（Database）：一个数据库中可以包含多个集合，可以在 MongoDB 中创建多个数据库，类似于关系型数据库中的数据库（Database）。 也就是说，MongoDB 将数据记录存储为文档 （更具体来说是BSON 文档open in new window），这些文档在集合中聚集在一起，数据库中存储一个或多个文档集合。 与SQL的术语对比 SQL MongoDB Table（表） Collection（集合） Row（行） Document（文档） Col（列） Field（字段） Primary Key（主键） Object ID （对象ID） Index（索引） Index（索引） Embedded Table（嵌套表） Embedded Document（嵌入式文档） Array（数组） Array（数组） 1.2 MongoDB特点 数据记录被存储为文档：MongoDB 中的记录就是一个 BSON 文档，它是由键值对组成的数据结构，类似于 JSON 对象，是 MongoDB 中的基本数据单元。 模式自由：集合的概念类似 MySQL 里的表，但它不需要定义任何模式，能够用更少的数据对象表现复杂的领域模型对象。 支持多种查询方式：MongoDB 查询 API 支持读写操作 (CRUD)以及数据聚合、文本搜索和地理空间查询。 支持 ACID 事务：NoSQL 数据库通常不支持事务，为了可扩展和高性能进行了权衡。不过，也有例外，MongoDB 就支持事务。与关系型数据库一样，MongoDB 事务同样具有 ACID 特性。MongoDB 单文档原生支持原子性，也具备事务的特性。MongoDB 4....

MySQL 0 参考资料 黑马程序员 MySQL数据库入门到精通 图解MySQL介绍 MySQL | CS-Notes 面试笔记 MySQL面试题 MySQL常见面试题总结 SQL语句 通用语法 分号结尾，可多行书写 不区分大小写 注释采用–、#、/**/ 分类 DDL(Data Defination Language): 数据定义语言，用来定义数据库对象（数据库，表，字段）。 DML(Data Manipulation Language): 数据操作语言，用来对数据库表中数据进行增删改 DQL(Data Query Language): 数据查询语言，用来查询数据库中表的记录。 DCL(Data Control Language): 数据控制语言，用来创建数据库用户、控制数据库访问权限。 1 存储引擎 1.1 MySQL体系结构 连接层：负责连接处理、授权认证，以及相关的安全服务。 服务层：提供SQL借口，完成缓存查询，SQL的分析和优化，部分内置函数的执行，跨存储引擎功能的实现（过程、函数等）。 引擎层：负责数据的存储和提取，服务层通过API和存储引擎通话，不同存储引擎有不同功能。 存储层：将数据存储在文件系统上，完成于存储引擎的交互。 1.2 存储引擎特点 InnoDB：支持事务、支持行级锁、支持外键。 MyISAM：不支持事务，支持表级锁，访问速度快。 Memory：数据存放在内存，访问速度快，支持Hash索引。 2 索引 索引是帮助MySql高效获取数据的数据结构。 2.1 索引结构 索引是在存储引擎层实现的，不同存储引擎有不同的结构 索引结构 描述 B+Tree索引 大部分存储引擎都支持 Hash索引 底层使用Hash表实现，针对精确匹配有效，不支持范围查询 R-Tree索引（空间索引） MyISAM引擎拥有的特殊索引，用于地理空间数据类型 Full-Text索引 倒排索引，类似于Lucene、ES InnoDB和MyISAM都支持B+Tree索引和全文索引。 2.1.1 B+Tree索引 为什么不用二叉搜索树？ 顺序插入会退化成链表，查询效率降低，并且层数较深。 为什么不用红黑树？ 大数据量的情况下，层级较深。...

MySQL补充 1 InnoDB中数据如何存放 InnoDB引擎中，一张表的数据是存放在“tableName.idb”表空间文件中的。 表空间由段（segment）、区（extent）、页（page）、行（row）组成。 行：记录按行存放 页：记录的读取写入是以页为单位，页是InnoDB存储引擎磁盘管理的最小单元。页的类型有数据页、undo log页、溢出页等。16KB。 区：表中数据量大的时候，为某个索引分配空间不再按照页为单位划分，而是以区为单位进行分配。1M。 段：表空间有索引段（B+Tree非叶子节点）、数据段（B+Tree叶子节点）、回滚段（MVCC）。 Compact行格式中，一条完整的记录分为「记录的额外信息」和「记录的真实数据」两个部分。 记录的额外信息： 变长字段长度列表：存储变长字段的数据占用的大小，当数据表没有变长字段的时候，表里的行格式就不会有「变长字段长度列表」。 NULL值列表：表中的某些列可能会存储 NULL 值，如果把这些 NULL 值都放到记录的真实数据中会比较浪费空间，所以 Compact 行格式把这些值为 NULL 的列存储到 NULL值列表中。如果存在允许 NULL 值的列，则每个列对应一个二进制位（bit），二进制位按照列的顺序逆序排列。（1标识该列为NULL，0标识不为NULL）。当数据表的字段都定义成 NOT NULL 的时，表里的行格式就不会有 NULL 值列表。 记录头信息： delete_mask ：标识此条数据是否被删除。 next_record：下一条记录的位置。 record_type：表示当前记录的类型，0表示普通记录，1表示B+树非叶子节点记录，2表示最小记录，3表示最大记录。 记录的真实数据： 记录真实数据部分除了我们定义的字段，还有三个隐藏字段，分别为：row_id、trx_id、roll_pointer。 row_id：如果我们建表的时候指定了主键或者唯一约束列，那么就没有 row_id 隐藏字段了。如果既没有指定主键，又没有唯一约束，那么 InnoDB 就会为记录添加 row_id 隐藏字段。row_id不是必需的，占用 6 个字节。 trx_id：事务id，表示这个数据是由哪个事务生成的。 trx_id是必需的，占用 6 个字节。 roll_pointer：这条记录上一个版本的指针。roll_pointer 是必需的，占用 7 个字节。 2 两阶段提交 事务提交后，redolog和binlog都要持久化到磁盘，但是这两个日志是独立的逻辑，可能会出现半成功的情况，也就是两个日志逻辑不一致： 如果在将 redo log 刷入到磁盘之后， MySQL 突然宕机了，而 binlog 还没有来得及写入。 导致从库的值是旧值，主库的是新值。 如果在将 binlog 刷入到磁盘之后， MySQL 突然宕机了，而 redo log 还没有来得及写入。 导致从库的值是新值，主库的是旧值。 MySQL 为了避免出现两份日志之间的逻辑不一致的问题，使用了「两阶段提交」来解决，两阶段提交其实是分布式事务一致性协议，它可以保证多个逻辑操作要不全部成功，要不全部失败，不会出现半成功的状态。...

MySQL面试 1 基础 MySQL执行一条Select语句期间发生了什么？ 通过连接器建立连接，管理链接、校验用户身份。 查询缓存：命中直接返回。 解析SQL，解析器对SQL查询语句进行词法语法分析。 执行SQL： 预处理：检查表或者字段是否存在； 优化：选择查询成本最小的执行计划； 执行：根据查询计划执行SQL语句，从存储引擎读取数据，返回给客户端。 MySQL 的 NULL 值是怎么存放的？ MySQL 的 Compact 行格式中会用「NULL值列表」来标记值为 NULL 的列，NULL 值并不会存储在行格式中的真实数据部分。 NULL值列表会占用 1 字节空间，当表中所有字段都定义成 NOT NULL，行格式中就不会有 NULL值列表，这样可节省 1 字节的空间。 MySQL 怎么知道 varchar(n) 实际占用数据的大小？ MySQL 的 Compact 行格式中会用「变长字段长度列表」存储变长字段实际占用的数据大小。 varchar(n) 中 n 最大取值为多少？ 一行记录最大能存储 65535 字节的数据，但是这个是包含「变长字段字节数列表所占用的字节数」和「NULL值列表所占用的字节数」。所以， 我们在算 varchar(n) 中 n 最大值时，需要减去这两个列表所占用的字节数。 行溢出后，MySQL 是怎么处理的？ 如果一个数据页存不了一条记录，InnoDB 存储引擎会自动将溢出的数据存放到「溢出页」中。 Compact 行格式针对行溢出的处理是这样的：当发生行溢出时，在记录的真实数据处只会保存该列的一部分数据，而把剩余的数据放在「溢出页」中，然后真实数据处用 20 字节存储指向溢出页的地址，从而可以找到剩余数据所在的页。 Compressed 和 Dynamic 这两种格式采用完全的行溢出方式，记录的真实数据处不会存储该列的一部分数据，只存储 20 个字节的指针来指向溢出页。而实际的数据都存储在溢出页中。 2 索引 索引的分类 按数据结构分类：B+tree索引、Hash索引、Full-text索引 按物理存储分类：聚簇索引、非聚簇索引 按字段特性分类：主键索引、唯一索引、普通索引、前缀索引...

NoSQL NoSQL（Not Only SQL 的缩写）泛指非关系型的数据库，主要针对的是键值、文档以及图形类型数据存储。并且，NoSQL 数据库天生支持分布式，数据冗余和数据分片等特性，旨在提供可扩展的高可用高性能数据存储解决方案。 一个常见的误解是 NoSQL 数据库或非关系型数据库不能很好地存储关系型数据。NoSQL 数据库可以存储关系型数据—它们与关系型数据库的存储方式不同。 NoSQL 数据库代表：HBase、Cassandra、MongoDB、Redis。 SQL与NoSQL区别 SQL NoSQL 数据存储模型 结构化存储，具有固定的行和列的表格 非结构化存储。文档（JSON）、键值对、宽列、图 代表 Oracle、MySQL、SQL Sever MongoDB、Redis、Cassandra、HBase、Neo4j ACID 支持 通常不支持 性能 取决于磁盘子系统 取决于集群大小、网络延迟等 扩展 垂直扩展（升级机器）、读写分离、分库分表 横向（增加服务器，基于分片机制） 用途 普通企业项目数据存储 图数据库支持分析和遍历连接数据之间的关系、键值数据库可以处理大量数据扩展和极高的状态变化 查询语法 结构化查询语言 数据访问语法可能因数据库而异 NoSQL数据库优势 NoSQL 数据库非常适合许多现代应用程序，例如移动、Web 和游戏等应用程序，它们需要灵活、可扩展、高性能和功能强大的数据库以提供卓越的用户体验。 灵活性： NoSQL 数据库通常提供灵活的架构，以实现更快速、更多的迭代开发。灵活的数据模型使 NoSQL 数据库成为半结构化和非结构化数据的理想之选。 可扩展性： NoSQL 数据库通常被设计为通过使用分布式硬件集群来横向扩展，而不是通过添加昂贵和强大的服务器来纵向扩展。 高性能： NoSQL 数据库针对特定的数据模型和访问模式进行了优化，这与尝试使用关系数据库完成类似功能相比可实现更高的性能。 强大的功能： NoSQL 数据库提供功能强大的 API 和数据类型，专门针对其各自的数据模型而构建。 NoSQL数据库类型 NoSQL 数据库主要可以分为下面四种类型： 键值：键值数据库是一种较简单的数据库，其中每个项目都包含键和值。这是极为灵活的 NoSQL 数据库类型，因为应用可以完全控制 value 字段中存储的内容，没有任何限制。Redis 和 DynanoDB 是两款非常流行的键值数据库。 文档：文档数据库中的数据被存储在类似于 JSON（JavaScript 对象表示法）对象的文档中，非常清晰直观。每个文档包含成对的字段和值。这些值通常可以是各种类型，包括字符串、数字、布尔值、数组或对象等，并且它们的结构通常与开发者在代码中使用的对象保持一致。MongoDB 就是一款非常流行的文档数据库。 图形：图形数据库旨在轻松构建和运行与高度连接的数据集一起使用的应用程序。图形数据库的典型使用案例包括社交网络、推荐引擎、欺诈检测和知识图形。Neo4j 和 Giraph 是两款非常流行的图形数据库。 宽列：宽列存储数据库非常适合需要存储大量的数据。Cassandra 和 HBase 是两款非常流行的宽列存储数据库。

Redis 黑马程序员Redis入门到实战教程 1 基本概念 1.1 Redis（::Re::mote ::Di::ctionary ::S::erver） 键值型存储，value支持多种不同数据结构。 单线程，每个命令具备原子性。（6.0之后的多线程仅是在网络处理部分，核心命令执行还是单线程） 低延迟，速度快（基于内存、IO多路复用、良好的编码）。 支持数据持久化。 支持主从集群和分片集群。 支持多语言客户端。 1.2 SQL和NoSQL SQL（Structured Query Language）：结构化的、关联的、SQL查询（语法固定）、事务（ACID） NoSQL（Not only SQL）：非结构的、非关联的、非SQL的（语法不固定，不统一）、不一定满足事务全部要求（BASE） 键值对：Redis 文档：MongoDB 图：Neo4j 列：HBase 1.3 Redis通用命令 // 1. 列出所有符合条件的key : KEYS [pattern] KEYS * KEYS a* // 2. 删除所有指定的key : DEL key [key ...] // 3. 判断key是否存在 : EXISTS key [key ...] // 4. 给一个key设置有效期，过期自动删除 : EXPIRE key seconds // 5. 查看命令具体用法 : help [command] // 6. 查看一个key的有效期 : TTL key 2 底层数据结构 Redis是一个key-value数据库，key一般是String类型，不过value的类型有很多：...

Redis补充 1 Redis网络模型 Redis的核心业务部分（命令处理）是单线程，但是整个Redis是多线程的。 v4.0：引入多线程异步处理一些耗时较长的任务，例如异步删除命令unlink。 v6.0：在核心网络模型中引入多线程，进一步提高对于多核CPU的利用率，但是核心部分依然是单线程。 为什么选择单线程？ 性能瓶颈是网络延迟，不是执行速度，多线程并不会带来巨大性能提升。 多线程会导致过多的上下文切换，带来不必要的开销。 引入多线程可能会面临线程安全问题，必须引入线程锁这样的安全手段，实现复杂度增高，性能也大打折扣。 原理篇-27.Redis网络模型-Redis单线程及多线程网络模型变更_哔哩哔哩_bilibili 2 Redis通信协议 RESP协议 原理篇-28.Redis通信协议-RESP协议_哔哩哔哩_bilibili 3 Redis事务 Redis事务的三个阶段 MULTI %事务开始 ... %命令入队 EXEC %事务执行 Redis事务特点 redis不支持回滚，事务失败，继续执行余下的命令 事物内部命令错误，所有命令都不会执行 事物内部出现运行错误，正确的命令会被执行 Redis事务没有原子性，持久性仅在开启AOF的always模式下支持。 Redis事务总是有隔离性（单线程）和一致性。 Redis事务相关命令 WATCH：乐观锁，给事务提供CAS机制，可以监控一个或者多个键，一旦其中有一个被修改，之后的事务就不会执行，监控一直持续到EXEC或者UNWATCH。 MULTI：用于开启事务，开启后可以继续送入命令，当EXEC被调用时，才被执行。 EXEC：执行事务块内所有命令，返回所有命令的返回值，按照命令先后排序。 DISCARD：清空事务队列，放弃执行事务。 UNWATCH：取消watch对所有key的监控。 4 缓存和数据库的一致性 设置有效期：给缓存设置有效期，到期自动删除，再次查询时更新 优势：简单方便 缺点：时效性差，缓存过期之前可能不一致 场景：更新频率较低，时效性要求较低的业务 同步双写：在修改数据库的同时，直接修改缓存 优势：时效性强，缓存与数据库强一致 缺点：有代码侵入，耦合度高 场景：对一致性，时效性要求较高的缓存数据 异步通知：在修改数据库时发送事件通知，相关服务监听到通知后修改缓存数据 优势：低耦合，可以同时通知多个缓存服务 缺点：时效性一般，可能存在中间不一致状态 场景：时效性要求一般，有多个服务需要同步 基于MQ的异步通知，对业务代码仍然有一定侵入性 基于Cannal的异步通知，可以做到几乎0侵入 4.1 缓存更新策略 删除缓存而不是更新缓存 先删数据，后删缓存 4.2 缓存不一致处理 使用消息队列，把要删除和删除失败的key放入消息队列，利用重试机制，删除对应的key 对代码有侵入性 数据库订阅+消息队列保证key被删除 利用canal或其他服务监听binlog 复杂度提升 延时双删防止脏数据 延迟时间需要具体的考量和测试 设置过期时间兜底 5 热key重建 使用互斥锁，保证只有一个线程重建，其他线程等待该线程重建完后，获取缓存数据即可。 不显示设置过期时间，而是设置逻辑过期字段，发现逻辑过期后，采用单独的线程构建缓存。 6 大key问题 单个简单key存储的value过大，hash、set、zset、list中存储过多元素。...

创建型模式 在创建对象的同时，隐藏创建逻辑，不使用new直接实例化对象，程序判断需要创建哪些对象时更加灵活。 1 单例模式 一个单例类在任何情况下只存在一个实例，构造方法私有，由自己创建一个静态变量存储实例，对外提供一个静态共有方法获取实例。 只有一个实例，避免了开销 没有抽象层，难以拓展，与单一职责原则冲突。 1.1 常见写法 1.1.1 饿汉式，线程安全 类一加载就创建对象，比较常用，但是容易产生垃圾对象。 线程安全，不加锁，执行效率高 缺点：不是懒加载，浪费内存空间 public class Singleton{ private Singleton(){} private final static Singleton instance = new Singleton(); public static Singleton getInstance(){ return instance; } } 使用反射破坏单例 public class Main{ public static void main(String[] args) throws Exception{ Constructor<Singleton> declaredConstructor = Singleton.class.getDeclaredConstructor(null); declaredConstructor.setAccessible(true); Singleton singleton = declaredConstructor.newInstance(); } } 1.1.2 懒汉式，线程不安全 public class Singleton{ private Singleton(){} private static Singleton instance; public static Singleton getInstance(){ if ( instance == null ) { instance = new Singleton(); } return instance; } } 多线程破坏单例 public class Main(){ public static void main(String[] args){ for(int i=0;i<3;i++){ new Thread(() -> { System....