Shellbye.github.io
Shellbye.github.io copied to clipboard
Shellbye
my blog --> see https://github.com/Shellbye/Shellbye.github.io/issues for recent update
### 基本概念 #### 1.树 Tree 树是一种非线性的存储结构，它可以存储一对多的带有结构的数据信息，最简单的树的定义可以理解为一个自顶向下的，由一个根结点（`root`）生长出来的，每一个父结点可能有多个分支（或者没有分支）的树。下图就是一个树，顶部的`A`是这颗树的根结点，没有子结点的结点称为叶子结点，比如下图中的`K`、`L`、`F`、`G`、`M`、`I`和`J`。  上图中的树有四层。 #### 2.二叉树 Binary Tree 二叉树是一种特殊的树，它在树的原始定义的基础上，添加了一个条件，就每一个父节点，最多只能有两个分叉，如下图，是一个二叉树  其中所有的结点，其子结点都不超过两个。 #### 3.二叉查找树（二叉搜索树） [Binary Search Tree(BST)](https://en.wikipedia.org/wiki/Binary_search_tree) 二叉查找树在二叉树的基础之上，又添加了一个条件，即它的结点是有序的，如下图  其中所有的结点，都大于其左子树中的所有结点，且小于其右子树中的所有结点。二叉查找树的这个特点，让在树中查找某一个元素时不需要盲目的遍历整个树，而且可以根据当前结点的大小，来有方向的选择分支。 #### 4.平衡二叉树 [Self-Balancing Binary Search Tree](https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree) 虽然二叉查找树（二叉搜索树）在查找时不需要遍历整个树，但是从上面的图片我们可以看出来当遇到一个特变倾斜的二叉查找树时，这个搜索的效率还是不够高，于是就有了平衡二叉树，其实可以叫做平衡二叉查找树，这个平衡，就体现在它的任意结点的左右子树，其高度差都不超过一，如下图，就是上面的非平衡二叉树经过平衡之后得出的平衡二叉树...
## 概念解释 ### 1.Page（页） [`Page`](https://dev.mysql.com/doc/refman/5.7/en/glossary.html#glos_page)是`MySQL`里面磁盘（` data files`）和内存（`buffer pool`）交换数据的基本单位，一个`Page`可以包含一行或多行数据。`MySQL`里面的`Page`默认大小是`16K`，而很多操作系统磁盘操作的基本单位是`4K`，所以`MySQL`里面的`Page`在写入磁盘时需要多次磁盘`IO`，因此就会可能会出现一个问题叫`Partial page write`。 ### 2.Partial page write（部分写失效） `Partial page write`出现的根本原因就是操作系统的磁盘`IO`操作的基本单位和`MySQL`的磁盘操作基本单位不一致，导致`MySQL`里面的`Page`在写入磁盘时需要多次磁盘`IO`，而当在多次`IO`之间系统发生宕机（比如断电），就产生了数据不一致的问题，即磁盘里只存储了部分数据（比如前`4K`），即`Partial page write`。 ## `Doublewrite`（两次写） 为了避免出现`Partial page write`，`MySQL`引入[`Doublewrite Buffer`](https://dev.mysql.com/doc/refman/5.7/en/innodb-doublewrite-buffer.html)，`Doublewrite`的过程可以用下面的图进行简单的说明  当有`Page`需要刷新到磁盘时（图中左上方两个`Page`），先使用`memcopy`把数据复制到内存中的`Doublewrite Buffer`，然后从`Doublewrite Buffer`以顺序的读写方式分两次刷新到[共享表空间](https://stackoverflow.com/questions/37805316/what-is-a-tablespace-and-why-is-it-used)（位于磁盘）上，然后在进行真正的磁盘刷新操作，刷新到磁盘文件中。 ##...
最近开始读[《MySQL技术内幕-InnoDB存储引擎》](https://book.douban.com/subject/24708143/)，感觉还是有很大的收获，读到 [`Insert Buffer`](https://dev.mysql.com/doc/refman/5.7/en/innodb-change-buffer.html)（注:[2015](https://mysqlserverteam.com/the-innodb-change-buffer/)年已改为`Change Buffer`，书籍出版时间是2013）的时候，感觉收获挺大，在网上找了一些资料，这里做一点笔记。 ## 概念解释 ### 1.索引（[Index](https://dev.mysql.com/doc/refman/5.7/en/glossary.html#glos_index)） 索引是数据库中非常关键的一个概念和技术，它在加速查询方面起着【至关重要】的作用。`InnoDB`中，所有的主键默认带有索引。主键的索引有一个别名叫聚集索引，非主键的其他列的索引叫辅助索引（secondary index）。 ### 2.聚集索引（[clustered index](https://dev.mysql.com/doc/refman/5.7/en/glossary.html#glos_clustered_index)） 如上所述，主键的索引一般叫聚集索引，为什么要用“聚集”这个词呢，我的理解是，因为主键往往的自增的，这就带来一个线下就是，索引在一个页的那些行，它们对应的行内容在磁盘也是在一个页的。这就比较类似书的目录和内容的关系，在目录上比较接近的部分，它们所指向的内容，也往往是比较接近的。比如第N章和第N+1章常常都是挨着的。这样的结构带来的一个好处就是在批量插入时，比如一次插入1000行数据，那么这1000行数据的主键肯定是连着的，那么它们的索引也很可能在一个页，最终它们的存储也恰好是在一个页，这样就可以用两次（一次写索引，一次写内容）磁盘`IO`（耗时）操作来完成，因为它们是连续的嘛。对于不连续的呢，就比较麻烦了。 ### 3.辅助索引（[secondary index](https://dev.mysql.com/doc/refman/5.7/en/glossary.html#glos_secondary_index)） 既然有聚集索引，那么对应的就有非聚集索引——辅助索引。辅助索引为什么不聚集呢，因为它们所对应的列很有可能并没有什么关系。就是说两个索引可能距离比较近，但是这和它们的内容所在位置是没有任何关系，这就类似汉语字典里面的用偏旁部首查字音一样，【打】和【答】可能在内容上比较近，但是它们对应的目录，也就是偏旁部首却距离很远，一个在提手旁“扌”对应的内容里，一个在竹字头“竹”对应的内容里，可以说是十万八千里了。在这种情况下，要批量插入1000行数据时，内容因为主键自增的关系，可能仍然可以通过一次磁盘`IO`就完成，但是我们的索引，却没有这么【聚集】，可能零零散散分布在若干个不同的页中，可能需要多次随机磁盘`IO`，这效率就低很多了，几乎是无法接收了，于是`Change Buffer`就出场了。 ## Change Buffer ### 1.`Change Buffer`的含义 为了避免上文描述的因为索引零散分布造成的多次随机磁盘`IO`，`MySQL InnoDB` 引入了 `Change Buffer`，对于辅助索引的相关操作，并不会直接操作索引的页，而是先放到`Change...
``` redis设计与实现 第2章 简单动态字符串 2.1 SDS的定义 SDS(Simple Dynamic String) 无法修改的才用C string，所有可能修改的地方，都用的SDS struct sdshdr { int len; // SDS中已使用的字符串长度 int free; // 可用 char buf[]; // 保存字符串，遵循C字符串结尾'\0'不计入len } 2.2 SDS与C字符串的区别 2.2.1...
在`JPA`和`Hibernate`的帮助下，`Spring`用起来也和`Django`很像，可以自动的从`model`生成数据库表。我最近在项目中遇到一个需要给所有的表都加一个`tb_`的前缀，从网上找了找，果然可以做到，下面简单记录一下。 本项目的整个工程链接在[Github](https://github.com/Shellbye/jpa_table_prefix_demo)，下面是最核心的文件`PrefixTbNamingStrategy.class` ```java package com.example.demo; import org.hibernate.boot.model.naming.Identifier; import org.hibernate.boot.model.naming.PhysicalNamingStrategy; import org.hibernate.engine.jdbc.env.spi.JdbcEnvironment; import org.springframework.context.annotation.Configuration; import java.util.Locale; @Configuration public class PrefixTbNamingStrategy implements PhysicalNamingStrategy { @Override public Identifier toPhysicalCatalogName(Identifier name, JdbcEnvironment jdbcEnvironment) {...
日常工作中，我们可能会遇到不少业务场景，他们的整体结构都是一样的，只是有一小部分有差别。我们把这样的场景抽象成以下的代码段 ```java long s1 = 0; // 1 + 2*2 + 3*3*3 + 4*4 + 5*5*5 + 6*6 + 7*7*7 + 8*8 + 9*9*9 for (Integer integer : integerList) {...
在尝到过自动化测试的甜头之后，我基本所有的项目都会有配套的自动化测试，之所这里没有说测试驱动开发（`Test Driven Development`），因为我目前确实还没做到`TDD`，我目前还是先`Develop`，然后才写`Test`，当然我还是希望以后真的能切实做到`TDD`，因为我一直相信前人经过很多弯路之后留下了的一些经验。 之前我的项目没太多的对第三方服务的依赖，所以写测试的时候，也没有太操心和第三方接口的一些问题，但是这次一个新项目对第三方服务严重依赖，因为基本所有的内容都来自三方服务，但是因为第三方服务也在开发中，就导致他们的接口很不稳定，这也让我的测试用例时通时不通，于是经过一些调研，找到了一些合适的`Spring Boot`下面基于`MockRestServiceServer`的模拟第三方服务接口的方法。本项目所有代码都在[这里](https://github.com/Shellbye/MockRestServiceServer-demo)。 ### 业务代码 ```java package com.example.demo; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.context.annotation.Bean; import org.springframework.web.client.RestTemplate; @SpringBootApplication public class DemoApplication { public static void main(String[] args) { SpringApplication.run(DemoApplication.class,...
在上一篇文章 #46 中，介绍了一种当必填参数没有传入时的比较友好的提示方式，今天在顺着同样的思路，介绍另外一种情况：参数类型错误时的处理情况。 ### 问题描述 当你使用`Spring Boot`时，如果接口的输入参数有误，后端的默认提示是这个样子的： 是不是一种不知所措的感觉呢？相比与上一篇的默认提示，这个提示简直就是太不友好了，我们想要的其实是这个样子的： ### 解决方案 与上一篇的思路简直是如出一辙，依然是找到那个正确的异常（`TypeMismatchException`），然后对它进行一些相应的处理就好。 项目目录结构 关键代码 `Controller.java` ```java package com.example.demo; import org.springframework.web.bind.annotation.*; @RestController public class Controller { @RequestMapping(value = "/demo", method = RequestMethod.GET)...
在多年不接触`Java`系，尤其是`Spring`之后，最近因为转岗需要用到`Spring Boot`，才突然发现原来`Java`系的Web开发现在也这么友好了，终于不用在配置各种个样的`xml`文件和各种`XXO.java`文件了。但是因为对`Spring Boot`不是很熟，所以有些东西还是需要记录一下。 ### 问题描述 比如最近遇到的一个小问题，就是当`GET`请求时，如果有一些`url`参数是必填而用户忘记填写的话，`Spring Boot`默认的返回是直接`400 Bad Request`（如下图）  这个原则上来说是没有问题的，但是当你写的是`restful`格式的接口时，这个提示就不是很友好了，需要改成比如这个样式的： `{"code":"400200","data":{},"message":"parameter p1 is required"}` ### 解决方案 其实从上面的图中可以发现，`Spring Boot`其实做完了我们需要的工作，只是它的展示样式不是我们需要的，那么我们需要做的，其实就是把`Spring Boot`的工作封装一下就好了。具体的思路就是找到参数缺失的异常（[`MissingServletRequestParameterException`](https://docs.spring.io/spring/docs/current/javadoc-api/org/springframework/web/bind/MissingServletRequestParameterException.html)），然后自己捕捉到它就好了。 项目目录结构  关键代码 `Controller.java` ```java package com.example.demo; import org.springframework.web.bind.annotation.*;...
这次的这个动态规划题目，我打算先自己来，把自己的思考过程记录下来。 ## 题目 >帮派里有 G 名成员，他们可能犯下各种各样的罪行。 第 i 种犯罪会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。 让我们把这些犯罪的任何子集称为盈利计划，该计划至少产生 P 的利润。 有多少种方案可以选择？因为答案很大，所以返回它模 10^9 + 7 的值。 >示例 1： >>输入：G = 5, P = 3, group...