2024年10月

Graphql是什么?先来一段AI给的回答:
GraphQL是一种为API设计的查询语言,与REST相比,它提供了更高效、强大和灵活的方法来与数据交互。GraphQL由Facebook于2012年开发,并于2015年开源。其主要的优势在于能够允许客户端精确地指定他们需要的数据,从而避免了过度获取或数据不足的问题。
主要特性
  1. 精确获取需要的数据:
  1. 单一端点:
  1. 类型系统:
  1. 查询与修改:
  1. 实时数据(Subscription):
优势和局限
优势:
  • 减少数据传输:只返回客户端请求的数据。
  • 减少请求数:多个数据需求可以在单一查询中解决。
  • 灵活性高:客户端可以自由构造查询,无需服务器频繁更新API。
局限:
  • 复杂查询性能问题:如果不加限制地进行深度查询或大规模的数据嵌套,可能会对服务器性能造成影响。
  • 缓存策略:相比于REST的URL级别缓存,GraphQL需要更复杂的缓存策略来优化性能。
  • 学习曲线:对于开发者来说,需要学习新的查询语法及其底层实现。
其他内容就不过多介绍了,大家感兴趣可以自行去搜索有关理论或说明。接下来我直接提供实战入门演示。
以下开始正式演示正文:
先创建一个webapi项目作为服务端和一个控制台项目作为客户端,用来测试使用。以及对应的引用包,如下图所示:
0
新建Quries文件夹,用来存放查询使用的类和方法。以及新增一个测试用的类和string类型返回值的方法 Hello()
0
在启动项或Program里面,添加Graphql服务,并添加Query的类型注册:
0
最后还要记得映射端点:
0
然后运行程序,例如我默认运行起来端口是5264,则打开url(根据自己情况更改url地址):
http://localhost:5264/graphql/
然后输入查询语句:query:{hello}就可以查出对应的返回内容。
0
客户端里面,创建graphql的客户端请求,并输入查询的方法为hello的query语句,以及输出的结果,如下图所示。结果和上面的一样,只是我只输出data里面的数据,data里面的数据就是我们需要的结果。
0
接着做个拓展演示,创建一个嵌套实体类,用来模拟多种情况:
0
创建一个测试使用的服务,模拟具体查询业务使用。
0
注册服务和接口以后,运行程序,并在graphql里面进行运行测试。当前测试的是输出所有字段。
0
现在,例如我把子集合去掉不要,那查询出来也就不会带有子集合的任何内容:
0
或者只需要指定的其他字段,删掉了描述、子集合的城市字段:
0
同样的,把查询语句丢到客户端程序里面进行查询,也可以查出指定字段的内容:
0
上面演示的是查询效果,也可以做增删改等其他操作。
在测试服务类新增一个业务操作,模拟接收到参数以后进行了业务操作,最终返回一个代表成功的数据。例如:
0
新建一个Mutations文件夹,用来存放增删改操作的类等。例如此处的测试使用的TestMutation.然后创建一个模拟传入参数进行操作的方法,该方法返回上面服务类里面的测试方法。
0
需要添加对修改有关操作的注册:
0
然后启动,做个测试。使用mutation语句进行操作,操作指定方法,方法里面指定参数和字段数据。可以看到服务端进入了前面预设的业务方法内,并且返回的true被客户端成功接收。
0
在控制台客户端,也执行一下mutation操作,也能够成功调用:
0
以上是查询和修改操作的例子,graphql还可以做数据推送和订阅,用于实现websocket的效果。
新建一个subscriptions文件夹,用来存放所有的消息推送和订阅有关的定义类。例如TestSub,里面定义了一个推送方法OnTestPublish
0
在前面的测试服务里面,新增ITopicEventSender事件接口的注入,以及新增一个方法,用来触发推送功能。并且推送的主题,使用刚才定义的OnTestPublish
0
然后需要提供对推送服务的注册,以及持久化选择。
0
使用默认的持久化,该持久化选择不建议上生产。具体原因,我去AI一下:
  1. 可扩展性问题:AddInMemorySubscriptions 存储订阅信息是在内存中进行的。这意味着订阅数据仅存在于单个进程中。如果你的应用程序需要在多个服务器实例之间进行扩展,每个实例的内存中都会有独立的订阅状态,从而导致状态不一致。因此,在大型应用或高负载环境中,这种方法不能很好地扩展。
  2. 持久性缺失:使用内存存储的另一个主要问题是数据的持久性。服务器重启或发生故障时,所有在内存中的订阅数据将丢失。这对于生产环境来说是不可接受的,因为需要保证服务的稳定性和数据的持久性。
  3. 资源使用效率:随着订阅数量的增加,内存的使用量也会随之上升。在内存资源有限的环境中,这可能会影响应用程序的整体性能和响应速度。
  4. 故障恢复:在内存中的订阅管理缺乏有效的故障恢复机制。如果系统崩溃或需要进行维护,恢复订阅状态将非常困难,可能需要从客户端重新建立订阅。
为了解决这些问题,生产环境中通常建议使用持久化和可扩展的订阅存储方案,比如基于 Redis 的 AddRedisSubscriptions 方法。大佬们感兴趣可以自己去拓展下。
现在缺少一个触发条件,由于咱们创建的是webapi项目,自带控制器,那我把控制器做个改造,通过swagger来调用进行触发数据推送,直接在请求里面,调用推送方法:
0
最后,由于推送使用了websocket,所以也需要添加对websocket的注册:
0
然后启动程序,使用subscription进行订阅onTestPublish主题消息。运行以后,会一直监听,除非我们取消监听。
0
打开swagger,直接调用并测试,可以看到面板接收到了测试推送的数据。
0
客户端要实现订阅,需要做一些改动。订阅的事件是字符串类型,所以需要创建一个字符串类型的属性,用来接收数据:
0
然后客户端创建时候,需要使用websocket端点。然后再创建订阅语句
0
接下来是订阅的具体实现演示:
0
允许,并通过swagger调用两次测试,都可以被监听到。
0
同时,之前打开的graphql演示面板,也可以看到能够收到后续消息,说明支持多客户端接收,符合websocket的推送效果。
0
有关实现的核心代码。服务端注册有关:
//添加GraphQL服务
builder.Services
.AddGraphQLServer()
.AddQueryType
<TestQuery>()
.AddMutationType
<TestMutation>()
.AddSubscriptionType
<TestSub>()
.AddInMemorySubscriptions();
//默认消息持久化(生产情况建议更换)

var app =builder.Build();

app.UseWebSockets();
//映射GraphQL端点
app.MapGraphQL();

客户端实现:
var option = newGraphQLHttpClientOptions
{
EndPoint
= new Uri("http://localhost:5264/graphql"),//设置 WebSocket 端点以支持订阅
WebSocketEndPoint = new Uri("ws://localhost:5264/graphql")
};
using var client = new GraphQLHttpClient(/*"http://localhost:5264/graphql"*/ option , newNewtonsoftJsonSerializer());//var request = new GraphQLRequest//{//Query = @"mutation{//otherOperation(info:{address:""龙岗区宝龙街道"",city:""大大大深圳"",phone:""10100011""})//}"//};//var response = await client.SendQueryAsync<object>(request);//Console.WriteLine(response.Data);//定义订阅请求
var subscriptionRequest = newGraphQLRequest
{
Query
= @"subscription {
onTestPublish
}
"};//创建订阅流
var subscriptionStream = client.CreateSubscriptionStream<OnTestPublishResponse>(subscriptionRequest);//订阅消息流
var subscription =subscriptionStream.Subscribe(
response
=>{if (response.Errors != null)
{
Console.WriteLine(
"Error occurred:" +response.Errors);
}
else{
Console.WriteLine($
"Received message: {response.Data.OnTestPublish}");
}
},
error
=> Console.WriteLine($"Subscription error: {error.Message}"),
()
=> Console.WriteLine("Subscription completed."));//模拟其他逻辑(例如,在某个时刻取消订阅,这儿通过输入任意按键触发取消和释放)
Console.WriteLine("Press any key to exit...");
Console.ReadKey();
//取消订阅并关闭 WebSocket 连接
subscription.Dispose();
client.Dispose();

如果需要我本地演示的代码项目,可以在本人公众号【
Dotnet Dancer
】回复:
代码演示
即可获取开源项目地址。如果需要其他咨询或合作,可V:WeskyNet001

如果以上内容对你有帮助,欢迎大佬们点赞、关注公众号或转发。谢谢大家!

最近公司有一个业务,由于多年使用七牛云存储数据【一些图片,文件】,导致占用了好几个T的空间, 其实有好几年之前的大量数据是现在不再使用的, 于是需要删除这批数据。
需要注意的是好几年之前的数据和现在的业务生成的数据都是用的一个储存空间, 想要删除就必须要根据时间来进行筛选,
例如2022年之前的数据全部删除:
思路:数据备份,虽然数据不再使用,但还是小心为上,现将数据备份在进行删除, 查看七牛云官方文档,删除数据是没有根据时间筛选这个功能的,但有趣的是可以根据一个文档内记录的数据名称来进行筛选, 所以,我们把想要删除的数据名称给存储到一个文档中就可以实现想要删除的无用数据的功能了:

点击查看代码
查询语句:qshell stat 空间名称 文件名称
将需要查询的文件导入txt文件中: qhsell listbucket2 空间名称 --stat 2022-01-01 --end 2024-01-01 --show-fields Key > filename.txt
删除txt文件中记录的数据名称:qshell batchdelete 空间名称 -i filename.txt --force

再来说一个如何进行数据备份:
数据备份无法进行筛选,只能将某个库中的数据全部进行备份,所以备份之前要先查看七牛云库中的数据量有多大,在准备一个硬盘或者U盘, 容量大雨数据量就可以了,下边事备份语句:

点击查看代码
空间中的文件备份:[需要配置文件自己配置]\r\n
{
"dest_dir"    :    "D:\qshell-v2.13.0-windows-amd64\qiniuyunfile",
"bucket"    :    "xxxxxxx"
}
备份语句:a.qshell qdownload -c 10 xxxx.conf  【-c后边表示线程数   xxx.conf是上边的配置文件】

需要注意:先备份在删除操作,家人们。。。 至于qshell的下载工具, 兄弟们去网上搜一下qshell关键字就可以找到了。

flink同步MySQL数据的时候出现内存溢出

背景:需要将1000w的某类型数据同步到别的数据源里面,使用公司的大数据平台可以很快处理完毕,而且使用的内存只有很少很少量(公司的大数据平台的底层是flink,但是连接器使用的是chunjun开源产品),由于我个人想使用flink原生的连接器来尝试一下,所以就模拟了1000w的数据,然后启动了flink单节点,通过flinksql的方式提交了同步任务,最终结果内存溢出!!!

下面的问题是在使用MySQL数据源的时候出现的,别的数据源可能不会有这个问题

下面是在main方法里面写的flink代码

import ch.qos.logback.classic.Level;
import ch.qos.logback.classic.Logger;
import ch.qos.logback.classic.LoggerContext;
import org.apache.flink.configuration.Configuration;
import org.apache.flink.streaming.api.environment.StreamExecutionEnvironment;
import org.apache.flink.table.api.bridge.java.StreamTableEnvironment;
import org.slf4j.LoggerFactory;

import java.util.List;

public class Main2 {

    static {
        LoggerContext loggerContext = (LoggerContext) LoggerFactory.getILoggerFactory();
        List<Logger> loggerList = loggerContext.getLoggerList();
        loggerList.forEach(logger -> {
            logger.setLevel(Level.INFO);
        });
    }

    public static void main(String[] args) throws Exception {


        Configuration configuration = new Configuration();

        StreamExecutionEnvironment streamExecutionEnvironment = StreamExecutionEnvironment.getExecutionEnvironment(configuration);
        streamExecutionEnvironment.setParallelism(1);

        StreamTableEnvironment streamTableEnvironment = StreamTableEnvironment.create(streamExecutionEnvironment);

        // 定义目标表
        streamTableEnvironment.executeSql("CREATE TABLE `gsq_hsjcxx_pre_copy1` (\n" +
                "  `reportid` BIGINT COMMENT 'reportid',\n" +
                "  `sfzh` VARCHAR COMMENT 'sfzh',\n" +
                "  `cjddh` VARCHAR COMMENT 'cjddh',\n" +
                "  `cjsj` VARCHAR COMMENT 'cjsj',\n" +
                "  PRIMARY KEY (`reportid`) NOT ENFORCED\n" +
                ") WITH (\n" +
                "  'connector' = 'jdbc',\n" +
                "  'url' = 'jdbc:mysql://127.0.0.1:3306/xxx?useSSL=false&useInformationSchema=true&nullCatalogMeansCurrent=true&characterEncoding=UTF-8&serverTimezone=Asia/Shanghai&',\n" +
                "  'table-name' = 'xxx',\n" +
                "  'username' = 'xxx',\n" +
                "  'password' = 'xxx',\n" +
                "  'sink.buffer-flush.max-rows' = '1024'\n" +
                ")");

        // 定义源表
        streamTableEnvironment.executeSql("CREATE TABLE `gsq_hsjcxx_pre` (\n" +
                "  `reportid` BIGINT COMMENT 'reportid',\n" +
                "  `sfzh` VARCHAR COMMENT 'sfzh',\n" +
                "  `cjddh` VARCHAR COMMENT 'cjddh',\n" +
                "  `cjsj` VARCHAR COMMENT 'cjsj'\n" +
                ") WITH (\n" +
                "  'connector' = 'jdbc',\n" +
                "  'url' = 'jdbc:mysql://127.0.0.1:3306/xxx?useSSL=false&useInformationSchema=true&nullCatalogMeansCurrent=true&characterEncoding=UTF-8&serverTimezone=Asia/Shanghai',\n" +
                "  'table-name' = 'xxx',\n" +
                "  'username' = 'xxx',\n" +
                "  'password' = 'xxx',\n" +
                "  'scan.fetch-size' = '1024'\n" +
                ")");

        // 将源表数据插入到目标表里面
        streamTableEnvironment.executeSql("INSERT INTO `gsq_hsjcxx_pre_copy1` (`reportid`,\n" +
                "    `sfzh`,\n" +
                "    `cjddh`,\n" +
                "    `cjsj`)\n" +
                "(SELECT `reportid`,\n" +
                "    `sfzh`,\n" +
                "    `cjddh`,\n" +
                "    `cjsj`\n" +
                "  FROM `gsq_hsjcxx_pre`)");


        streamExecutionEnvironment.execute();
    }
}

以上是一个简单的示例,定义了三个sql语句,首先是定义两个数据源,然后再进行查询插入操作,运行之后就会开始执行flinksql。
如果在启动的时候指定jvm的内存大小为 -Xms512m -Xmx1g,会发现压根启动不起来,直接就oom了。
如果不指定jvm内存的话,则程序能启动,内存的使用量会慢慢的升高,甚至要使用将近4G内存,如果在flink集群上运行的话,直接会oom的。
先说flink读取数据的流程,flink读取数据的时候是分批读取的,不可能一次性把数据全部读出来的,但是通过现象来看是flink读取数据的时候,所有数据都在内存里面的,这个现象是不合理的。

分析源码

通过调试模式分析代码是怎么走的,经过一番调试之后发现了一下代码

public void openInputFormat() {
        try {
            Connection dbConn = this.connectionProvider.getOrEstablishConnection();
            if (this.autoCommit != null) {
                dbConn.setAutoCommit(this.autoCommit);
            }

            this.statement = dbConn.prepareStatement(this.queryTemplate, this.resultSetType, this.resultSetConcurrency);
            if (this.fetchSize == -2147483648 || this.fetchSize > 0) {
                this.statement.setFetchSize(this.fetchSize);
            }

        } catch (SQLException var2) {
            throw new IllegalArgumentException("open() failed." + var2.getMessage(), var2);
        } catch (ClassNotFoundException var3) {
            throw new IllegalArgumentException("JDBC-Class not found. - " + var3.getMessage(), var3);
        }
    }

先说下flink是怎么是如果分批拉取数据的,flink是使用的游标来分批拉取数据,那么这个时候就要确定是否真正使用了游标。

于是乎,我写了一个原生的JDBC程序读取数据的程序(没有限制jvm内存)

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.ResultSet;

public class Main3 {
    public static void main(String[] args) {
        Connection connection = null;
        Runtime runtime = Runtime.getRuntime();
        System.out.printf("启动前总内存>%s 使用前的空闲内存>%s 使用前最大内存%s%n", runtime.totalMemory() / 1024 / 1024, runtime.freeMemory() / 1024 / 1024, runtime.maxMemory() / 1024 / 1024);

        try {
            int i = 0;
            connection = DriverManager.getConnection("jdbc:mysql://127.0.0.1:3306/xxx?useSSL=false&useInformationSchema=true&nullCatalogMeansCurrent=true&characterEncoding=UTF-8&serverTimezone=Asia/Shanghai&useCursorFetch=true", "xxx", "xxx");
            connection.setAutoCommit(false);
            PreparedStatement preparedStatement = connection.prepareStatement("SELECT `reportid`,\n" +
                    "    `sfzh`,\n" +
                    "    `cjddh`,\n" +
                    "    `cjsj`\n" +
                    "  FROM `gsq_hsjcxx_pre`", ResultSet.TYPE_FORWARD_ONLY, ResultSet.CONCUR_READ_ONLY);
            // 每批拉取的数据量
            preparedStatement.setFetchSize(1024);
            ResultSet resultSet = preparedStatement.executeQuery();
            while (resultSet.next()) {
                i++;
            }
            System.out.printf("启动前总内存>%s 使用前的空闲内存>%s 使用前最大内存%s%n", runtime.totalMemory() / 1024 / 1024, runtime.freeMemory() / 1024 / 1024, runtime.maxMemory() / 1024 / 1024);
            System.out.println("数据量> " + i);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            if (connection != null) {
                try {
                    connection.close();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

最终打印的结果是

很显然,数据是全部读取出来的,这个时候需要确认的程序是不是真正使用了游标,经过一番查看后发现,需要在jdbc的参数里面加上&useCursorFetch=true,才能使游标生效
修改完jdbc参数之后,问题就得到了完全的结局

除此之外我用过apahce的seatunnel,这个同步数据的时候是真的快,快的离谱。不过使用的时候可能会漏掉一些jdbc相关的参数(MySQL为例)
"rewriteBatchedStatements" : "true" 这个批量的参数 apache seatunnel也不会自动添加的,需要手动加,不然数据就是一条一条插入的,这个坑我也踩了

还记得上一篇中我们遗留的问题吗?我们再简要回顾一下,现在有一颗空的二叉查找树,我们分别插入1,2,3,4,5,五个节点,那么得到的树是什么样子呢?这个不难想象,二叉树如下:

树的高度是4,并且数据结构上和链表没有区别,查找性能也和链表一致。如果我们将树的结构改变一下呢?比如改成下面的树结构,

那么树的高度变成了3,并且它也是一棵二叉查找树,树的高度越低,查找性能就越高,这是我们理想中的数据结构。如果想要树的高度尽可能的低,那么左右子树的高度差就不能相差太多。这就引出了我们今天的主题
AVL平衡二叉树
,AVL平衡二叉树的定义为任意节点的左右子树的高度差不能超过1。这样就可以保证我们的这棵树的高度保持在一个最低的状态,这样我们的查找性能也是最优的。那么我们如何在树的变化时(也就是增加节点或删除节点时),保证AVL平衡二叉树的性质呢?下面我们就针对每一种情况进行分析。

左左单旋转

我们先看看下面的例子,以下每一个例子都是最复杂的情况,完全覆盖简单的情况,所以我们把最复杂情况用代码实现了,那么简单的情况也会涵盖在内。看下图

上图中,原本以k1为根节点的树是一个AVL平衡二叉树,这时,我们向树中插入节点2,根据二叉查找树的性质,最后节点2插入的位置如上图。插入节点后,我们每个节点分析一下,看看节点是否还符合AVL平衡二叉树的性质。我们先看看节点3,插入节点2后,节点3的左子树的高度是0,因为只有一个节点2。再看节点3的右子树,右子树为空,那么高度为-1,
这里我们统一规定,如果节点为空,那么高度为-1
。节点3的左右子树高度为1,符合AVL平衡二叉树的性质,同理我们再看节点k2,左子树高度为1,右子树高度为0,高度差为1,也符合AVL平衡二叉树。再看节点k1,左子树k2的高度为2,右子树的高度为0,相差为2,所以在节点k1处不满足AVL平衡二叉树的性质,我们要进行调整,使得以k1为根节点的树变为一个AVL平衡二叉树,我们要怎么做呢?

由于左子树的高度比较高,所以我们要将树旋转一下,用k2作根节点,k1作为k2的右子节点,旋转后如图所示:

旋转后,以k2为根节点的新树,是一棵AVL平衡二叉树。这里我们要
特别注意一下节点5的位置
,它的原始位置是k2的右子树,而k2又是k1的左子树,根据二叉查找树的性质,k2的右子树中的值是大于k2,小于k1的。旋转后,k2变成了根节点,k1变成k2的右子树,那么原k2的右子树(节点5),变为k1的左子树。那么这棵树根据二叉查找树的性质,还是大于k2,小于k1的,没有变动,这是符合我们的预期的。通过上述的旋转,我们得到的新树是一棵AVL平衡二叉树。

我们总结一下重要的点,为编码做准备:

  1. 发现k1的左子树比右子树高度大于1;
  2. 发现k1的左子树k2的左子树高度大于k2的右子树高度,这种称作
    左-左情形
    。要做左侧单旋转。
  3. 将k2作为新树的节点,k2的右子树改为k1,k1的左子树改为k2的右子树。
  4. 更新k1和k2的高度。

完成上面的操作,我们得到一个新的AVL平衡二叉树。下面我们进入具体编码。

/**
 * 二叉树节点
 * @param <T>
 */
public class BinaryNode<T extends Comparable<T>> {

    //节点数据
    @Setter@Getter
    private T element;
    //左子节点
    @Setter@Getter
    private BinaryNode<T> left;
    //右子节点
    @Setter@Getter
    private BinaryNode<T> right;
    //节点高度
    @Setter@Getter
    private Integer height;

    //构造函数
    public BinaryNode(T element) {
        if (element == null) {
            throw new RuntimeException("二叉树节点元素不能为空");
        }
        this.element = element;
        this.height = 0;
    }
}

我们现在改造
BinaryNode
类,并在类中增加高度属性,高度默认为0。

/**
 * 二叉查找树
 */
public class BinarySearchTree<T extends Comparable<T>> {
    ……
    /**
     * 插入元素
     *
     * @param element
     */
    public void insert(T element) {
        root = insert(root, element);
    }

    private BinaryNode<T> insert(BinaryNode<T> tree, T element) {
        if (tree == null) {
            tree = new BinaryNode<>(element);
        } else {
            int compareResult = element.compareTo(tree.getElement());
            if (compareResult > 0) {
                tree.setRight(insert(tree.getRight(), element));
            }

            if (compareResult < 0) {
                tree.setLeft(insert(tree.getLeft(), element));
            }
        }

        return balance(tree);
    }
    
    /**
     * 平衡节点
     * @param tree
     */
    private BinaryNode<T> balance(BinaryNode<T> tree) {
        if (tree == null) {
            return null;
        }
        Integer leftHeight = height(tree.getLeft());
        Integer rightHeight = height(tree.getRight());
        if (leftHeight - rightHeight > 1) {
            //左-左情形,单旋转
            if (height(tree.getLeft().getLeft()) >= height(tree.getLeft().getRight())) {
                tree = rotateWithLeftChild(tree);
            }
        } 

        //当前节点的高度 = 最高的子节点 + 1
        tree.setHeight(Math.max(leftHeight,rightHeight) + 1);
        return tree;
    }
        
	/**
     * 节点的高度
     * @param node
     * @return
     */
    public Integer height(BinaryNode node) {
        return node == null?-1:node.getHeight();
    }   
    
    /**
     * 左侧单旋转
     * @param k1
     */
    private BinaryNode<T> rotateWithLeftChild(BinaryNode<T> k1) {
        BinaryNode<T> k2 = k1.getLeft();
        k1.setLeft(k2.getRight());
        k2.setRight(k1);
        k1.setHeight(Math.max(height(k1.getLeft()),height(k1.getRight()))+1);
        k2.setHeight(Math.max(height(k2.getLeft()),height(k2.getRight()))+1);
        return k2;
    }
    ……
}

我们再在
BinarySearchTree
类中增加height方法,获取节点的高度,如果节点为空,返回-1。由于
insert
后,树可能会发生旋转,节点会发生变化,所以这里,
insert
方法改造为会有返回值。在第一个
insert
方法中,调用第二个
insert
方法,并用root去接第二个insert方法的返回值,说明整棵树的根节点可能会发生旋转变化。同样在第二个insert方法中,递归调用时,根据不同的条件,将返回值给到当前节点的左或右子节点。节点插入完成后,我们统一调用
balance
方法,如果节点不满足平衡条件,我们要进行相应的旋转,最后把相关的节点的高度进行更新,这个
balance
方法是我们今天重点的方法。

进入balance方法后,我们分别获取左右子树的高度,如果左子树的高度比右子树高度大于1,说明不满足平衡条件,需要进行旋转。然后再判断左子树的左子树与左子树的右子树的高度,如果大于,说明是
左-左情形
,需要左侧单旋转。这里比较绕,大家多看几篇,加深理解。我们把以当前节点为根节点的子树传入
rotateWithLeftChild
方法中,为了和上面的图对应起来,变量的名称叫做k1。那么对应的k2就是k1的左子树,然后进行旋转,k1的左子树设置为k2的右子树,k2的右子树设置为k1,然后再重新计算k1和k2的高度,最后将k2作为新子树的根节点返回。这样
左-左情形
的单旋转就实现了。我们可以多看几遍代码加深一下理解。

右右单旋转

与左左相对称的是
右-右情形
,我们看下图:

我们插入节点6后,导致以k1为根节点的子树不平衡,需要进行旋转,旋转的动作与左左情形完全对称,总结操作如下:

  1. 发现k1的右子树比左子树的高度大于1;
  2. 发现k1的右子树k2的右子树高度大于k2的左子树高度,这种称作
    右-右情形
    。要做右侧单旋转。
  3. 将k2作为新树的节点,k2的左子树改为k1,k1的右子树改为k2的左子树。
  4. 更新k1和k2的高度。

旋转后,如下图:

我们按照上面的操作进行编码,

/**
 * 平衡节点
 * @param tree
 */
private BinaryNode<T> balance(BinaryNode<T> tree) {
    if (tree == null) {
        return null;
    }
    Integer leftHeight = height(tree.getLeft());
    Integer rightHeight = height(tree.getRight());
    if (leftHeight - rightHeight > 1) {
        //左-左情形,单旋转
        if (height(tree.getLeft().getLeft()) >= height(tree.getLeft().getRight())) {
            tree = rotateWithLeftChild(tree);
        }
    } else if (rightHeight - leftHeight > 1){
        //右-右情形,单旋转
        if (height(tree.getRight().getRight()) >= height(tree.getRight().getLeft())) {
            tree = rotateWithRightChild(tree);
        }
    }

    //当前节点的高度 = 最高的子节点 + 1
    tree.setHeight(Math.max(leftHeight,rightHeight) + 1);
    return tree;
}

/**
 * 右侧单旋转
 * @param k1
 * @return
 */
private BinaryNode<T> rotateWithRightChild(BinaryNode<T> k1) {
    BinaryNode<T> k2 = k1.getRight();
    k1.setRight(k2.getLeft());
    k2.setLeft(k1);
    k1.setHeight(Math.max(height(k1.getLeft()),height(k1.getRight()))+1);
    k2.setHeight(Math.max(height(k2.getLeft()),height(k2.getRight()))+1);

    return k2;
}

在balance方法中,我们增加了
右-右情形
的判断,然后调用
rotateWithRightChild
方法,在这个方法中,为了和上图对应,变量的名字我们依然叫做k1和k2。k1的右节点设置为k2的左节点,k2的左节点设置为k1,然后更新高度,最后把新的根节点k2返回。

左右双旋转

下面我们再看双旋转的情形,如下图所示:

我们新插入节点3后,导致以k1为根节点的子树不满足平衡条件,我们先用之前的左侧单旋转,看看能不能满足,如下图所示:

旋转后,以k2为根节点的新树,右子树比左子树的高度大于1,
也不满足平衡条件,所以这种方案是不行的
。那我们要怎么做呢?我们只有将k3作为新的根节点才能满足平衡条件,将k3移动到根节点我们需要旋转两次,第一次先在k2节点进行右旋转,将k3旋转到k1的左子节点的位置,如图:

然后再在k1位置进行左旋转,将k3移动到根节点,如图:

这样就满足了平衡条件,细心的小伙伴可能注意到了,原k3的做节点挂到了k2的右节点上,原k3的右节点刮到了k1的左节点上。这些细节并不需要我们特殊的处理,因为在左旋转右旋转的方法中已经处理过了,我们再总结一下具体的细节:

  1. 插入节点后,发现k1的左子树比右子树高度大于1;
  2. 发现k1的左子树k2,k2的右子树比k2的左子树高,这是
    左-右情形
    ,需要双旋转。
  3. 将k1的左子树k2进行右旋转;
  4. 将k1进行左旋转;

我们编码实现

/**
 * 平衡节点
 * @param tree
 */
private BinaryNode<T> balance(BinaryNode<T> tree) {
    if (tree == null) {
        return null;
    }
    Integer leftHeight = height(tree.getLeft());
    Integer rightHeight = height(tree.getRight());
    if (leftHeight - rightHeight > 1) {
        //左-左情形,单旋转
        if (height(tree.getLeft().getLeft()) >= height(tree.getLeft().getRight())) {
            tree = rotateWithLeftChild(tree);
        } else {// 左-右情形,双旋转
            tree = doubleWithLeftChild(tree);
        }
    } else if (rightHeight - leftHeight > 1){
        //右-右情形,单旋转
        if (height(tree.getRight().getRight()) >= height(tree.getRight().getLeft())) {
            tree = rotateWithRightChild(tree);
        }
    }

    //当前节点的高度 = 最高的子节点 + 1
    tree.setHeight(Math.max(leftHeight,rightHeight) + 1);
    return tree;
}

/**
 * 左侧双旋转
 * @param k1
 * @return
 */
private BinaryNode<T> doubleWithLeftChild(BinaryNode<T> k1) {
    k1.setLeft(rotateWithRightChild(k1.getLeft()));
    return rotateWithLeftChild(k1);
}

我们在balance方法中,增加
左-右情形
的判断,然后调用
doubleWithLeftChild
方法,在这个方法中,我们按照之前总结的步骤,先将k1的左节点进行一次右旋转,然后再将k1进行左旋转,最后将新的根节点返回,旋转后达到了平衡的条件。

右左双旋转

最后我们再来看与左右情形对称的
右-左情形
,树的初始结构如下图:

插入节点8后,导致k1节点的右子树高度比左子树高度大于1,同时k2的左子树比右子树高,这就是
右-左情形
。这时,我们需要先在k2节点做一次左旋转,旋转后如图:

然后再在k1节点做一次右旋转,旋转后如图:

我们参照上面的左右情形,总结一下右左情形的操作:

  1. 插入节点后,发现k1的右子树比左子树高度大于1;
  2. 发现k1的右子树k2,k2的左子树比k2的右子树高,这是
    右-左情形
    ,需要双旋转。
  3. 将k1的右子树k2进行左旋转;
  4. 将k1进行右旋转;

然后我们编码实现:

/**
 * 平衡节点
 * @param tree
 */
private BinaryNode<T> balance(BinaryNode<T> tree) {
    if (tree == null) {
        return null;
    }
    Integer leftHeight = height(tree.getLeft());
    Integer rightHeight = height(tree.getRight());
    if (leftHeight - rightHeight > 1) {
        //左-左情形,单旋转
        if (height(tree.getLeft().getLeft()) >= height(tree.getLeft().getRight())) {
            tree = rotateWithLeftChild(tree);
        } else {// 左-右情形,双旋转
            tree = doubleWithLeftChild(tree);
        }
    } else if (rightHeight - leftHeight > 1){
        //右-右情形,单旋转
        if (height(tree.getRight().getRight()) >= height(tree.getRight().getLeft())) {
            tree = rotateWithRightChild(tree);
        } else {//右-左情形,双旋转
            tree = doubleWithRightChild(tree);
        }
    }

    //当前节点的高度 = 最高的子节点 + 1
    tree.setHeight(Math.max(leftHeight,rightHeight) + 1);
    return tree;
}

/**
 * 右侧双旋转
 * @param k1
 * @return
 */
private BinaryNode<T> doubleWithRightChild(BinaryNode<T> k1) {
    k1.setRight(rotateWithLeftChild(k1.getRight()));
    return rotateWithLeftChild(k1);
}

由于左右单旋转的方法在之前已经实现过了,所以双旋转的实现,我们直接调用就可以了,先将k1的右节点进行一次左旋转,再将k1进行右旋转,最后返回新的根节点。因为节点的高度正在左右单旋转的方法里已经处理了,所以这里不需要特殊的处理。

删除节点

与插入节点一样,删除节点也会引起树的不平衡,同样,在删除节点后,我们调用balance方法使树再平衡。remove改造方法如下:

/**
 * 删除元素
 * @param element
 */
public void remove(T element) {
    root = remove(root, element);
}

private BinaryNode<T> remove(BinaryNode<T> tree, T element) {
    if (tree == null) {
        return null;
    }
    int compareResult = element.compareTo(tree.getElement());
    if (compareResult > 0) {
        tree.setRight(remove(tree.getRight(), element));
    } else if (compareResult < 0) {
        tree.setLeft(remove(tree.getLeft(), element));
    }
    if (tree.getLeft() != null && tree.getRight() != null) {
        tree.setElement(findMin(tree.getRight()));
        tree.setRight(remove(tree.getRight(), tree.getElement()));
    } else {
        tree = tree.getLeft() != null ? tree.getLeft() : tree.getRight();
    }
    return balance(tree);
}

同样,remove方法会引起子树根节点的变化,所以,第二个remove方法要增加返回值,在调用第二个remove方法时,要用返回值覆盖当前的节点。

总结

好了,AVL平衡二叉树的操作就完全实现了,它解决了树的不平衡问题,使得查询效率大幅提升。小伙伴们有问题,欢迎评论区留言~~

一、详解

1.1 介绍

现如今的 Web 项目,由服务端向外发起网络请求的场景,基本上随处可见!
传统情况下,在服务端代码里访问 http 服务时,一般会使用 JDK 的 HttpURLConnection 或者 Apache 的 HttpClient,不过这种方法使用起来太过繁琐,而且 api 使用起来非常的复杂,还得操心资源回收。

1.2 什么是 HttpUtils?

  • HttpUtils 是 Solon 提供的进行远程调用客户端
  • HttpUtils 提供了很多远程调用的方法,能够大大提高客户端的编写效率。 HttpUtils 接口实现了 HttpURLConnection 的适配(默认),以及 OkHttp 的适配。
  • 官网地址:
    solon-net-httputils

1.3 引入依赖

<dependency>
    <groupId>org.noear</groupId>
    <artifactId>solon-net-httputils</artifactId>
</dependency>

HttpUtils 不需要初始化,即可直接使用。而且,可以直接使用负载均衡的能力(需要引入 solon-cloud 的插件,提供底层支持)。像这样:

HttpUtils.http("user-service", "/user/get?id=1").get();

二、接口使用

HttpUtils 最大的特色就是对各种网络请求方式做了包装,能极大的简化开发人员的工作量,下面我们以 GET、POST、PUT、DELETE、文件上传与下载为例,分别介绍各个API的使用方式。

2.1 GET 请求

通过 HttpUtils 发送 HTTP GET 协议请求,经常使用到的方法有两个:

  • get() -> String
  • getAs(Type type) -> T
    (支持泛型)

在 Solon 环境下写一个单元测试用例,首先创建一个 Api 接口,然后编写单元测试进行服务测试。

不带参的get请求

@Controller
public class TestController {
    @Get
    @Mapping("testGet")
    public Result testGet(){
        Result result = new Result();
        result.setCode("200");
        result.setMsg("demo...");
        return result;
    }
}

@Data
public class Result {
    private String code;
    private String msg;
}

单元测试(不带参的get请求)

@Test
public void testGet(){
    //请求地址
    String url = "http://localhost:8080/testGet";
 
    //发起请求,直接返回对象
    Result result = HttpUtils.http(url).getAs(Result.class);
    System.out.println(result.toString());

带参的get请求(使用占位符号传参)

@Controller
public class TestController {
    @Get
    @Mapping("testGetByRestFul/{id}/{name}")
    public Result testGetByRestFul(@Path("id") String id, @Path("name") String name){
        Result result = new Result();
        result.setCode("200");
        result.setMsg("demo...");
        return result;
    }
}

单元测试(带参的get请求),顺带加了个 header 信息。

@Test
public void testGetByRestFul(){
    //请求地址
    String url = "http://localhost:8080/testGetByRestFul/001/张三";
 
    //发起请求,直接返回对象(restful风格)
    Result result = HttpUtils.http(url).header("App-Id","1").getAs(Result.class);
    System.out.println(result.toString());
}

2.2 POST 请求

其实 POST 请求方法和 GET 请求方法上大同小异,HttpUtils 的 POST 请求也包含两个主要方法:

  • post() -> String
  • postAs(Type type) -> T
    (支持泛型)

模拟表单请求,post方法测试

@Controller
public class TestController {
    @Post
    @Mapping("testPostByForm")
    public Result testPostByForm(String userName, String userPwd){
        Result result = new Result();
        result.setCode("200");
        result.setMsg("Demo...");
        return result;
    }
}

x-www-form-urlencoded post

@Test
public void testPostByForm(){
    //请求地址
    String url = "http://localhost:8080/testPostByForm";
 
    //发起请求
    Result result = HttpUtils.http(url)
                             .data("userName", "唐三藏")
                             .data("userPwd", "123456")
                             .postAs(Result.class);
                  
    System.out.println(result.toString());
}

form-data post,顺带加上文件上传

@Test
public void testPostByForm(){
    //请求地址
    String url = "http://localhost:8080/testPostByForm";
 
    //发起请求
    Result result = HttpUtils.http(url)
                             .data("userName", "唐三藏")
                             .data("userPwd", "123456")
                             .data("file", "logo.jpg", new File("/data/logo.jpg")) 
                             .postAs(Result.class, true); //useMultipart = true
                  
    System.out.println(result.toString());
}

json-body post

@Test
public void testPostByForm(){
    //请求地址
    String url = "http://localhost:8080/testPostByForm";
 
    //发起请求
    Result result = HttpUtils.http(url)
                             .bodyOfJson("{\"userName\":\"唐三藏\",\"userPwd\":\"123456\"}")
                             .postAs(Result.class); 
                  
    System.out.println(result.toString());
}

bean-body post

@Test
public void testPostByForm(){
    //请求地址
    String url = "http://localhost:8080/testPostByForm";
    
    UserBean user = new UserBean();
    user.setUserName("唐三藏");
    user.setUserPwd("123456")
 
    //发起请求
    Result result = HttpUtils.http(url)
                             .bodyOfBean(user)
                             .postAs(Result.class); 
                  
    System.out.println(result.toString());
}

2.3 PUT、PATCH、DELETE 请求

用法与 POST 完全相同。

2.4 高级用法

获取响应(用完要关闭)

try(HttpResponse resp = HttpUtils.http("http://localhost:8080/hello").data("name","world").exec("POST")) {
    int code = resp.code();
    String head = resp.header("Demo-Header");
    String body = resp.bodyAsString();
}

配置序列化器。默认为 json,改为 fury;或者自己定义。

FuryBytesSerializer serializer = new FuryBytesSerializer();

Result body = HttpUtils.http("http://localhost:8080/book")
                       .serializer(serializer)
                       .bodyOfBean(book)
                       .postAs(Result.class);