定义

二叉搜索树在极端情况下会退化成链表:如果全部或者部分地按照关键字的递增或者递减顺序插入二叉查找树的结点，则所建立的二叉查找树全部或者在局部形成退化的单分支结构，为了优化（时间复杂度）引入了平衡二叉树。

AVL树又称为平衡二叉树，即Balanced Binary Tree或者Height-Balanced Tree，它或者是一棵空二叉树，或者是具有如下性质的二叉查找树：其左子树和右子树都是高度平衡的二叉树，且左子树和右子树的高度之差的绝对值不超过1。如果将二叉树上结点的平衡因子BF（Balanced Factor）定义为该结点的左子树与右子树的高度之差，根据AVL树的定义，AVL树中的任意结点的平衡因子只可能是-1（右子树高于左子树）、0或者1（左子树高于右子树）.

BalanceFactor = height(left-sutree) − height(right-sutree)

介绍

Trie树，又称为字典树、单词查找树或者前缀树，是一种用于快速检索的多叉树结构。比如小写英文字母的字典树是26叉数，数字的字典树是10叉树。

Trie树的基本性质有三点，归纳为：

1. 根节点不包含字符，根节点外每一个节点都只包含一个字符
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符不相同（分叉）

Trie树从根节点到某一节点，都可以称为一个字符串，但是不一定是单词。比如图中在没有添加pan这个单词的时候,pan 只是 panda的前缀,一个普通字符串. 只有在添加pan这个字符串之后，pan这时候才是一个单词。

介绍

线段树（Segment Tree）是一种二叉树形数据结构，用以存储区间或线段，并且允许快速查询结构内包含某一点的所有区间。

1. 线段树是一棵高度平衡的二叉树，有可能是满二叉树或者完全二叉树，但这不是必要条件
2. 线段树的每一个结点都代表一个区间。父结点所代表的区间是两个子结点的融合。兄弟结点所代表的区间相互不重叠。根结点代表整个区间。
3. 叶子节点对应原始数组中的元素
4. 线段树不考虑添加元素，即区间固定。跟堆一样用数组表示，如果给定原生区间数组有n个元素，那么这个线段树的数组表示需要4n的空间

一个包含 n 个区间的线段树，空间复杂度为 O(n)，查询的时间复杂度则为 O(logn+k)，其中 k 是符合条件的区间数量。一颗线段树的构造就是根据区间的性质来构造的

前言

堆（Heap）是一个可以被看成近似完全二叉树的数组。树上的每一个结点对应数组的一个元素。除了最底层外，该树是完全充满的，且最底层尽可能地从左到右填入。

堆我们可模拟看成是一颗完全二叉树，但是它底层数据结构是数组（完全二叉树是满二叉树的一部分， 不满的那一部分一定是树的右下部分）。而满二叉树是一颗除了最底下一层叶子结点外，其他节点都有左右子树。

堆包括最大堆和最小堆：最大堆的每一个节点（除了根结点）的值不大于其父节点值；最小堆的每一个节点（除了根结点）的值不小于其父节点值。
堆常见的操作：

• HEAPIFY 建堆：把一个乱序的数组变成堆结构的数组，时间复杂度为 O(n)。
• HEAPPUSH：把一个数值放进已经是堆结构的数组中，并保持堆结构，时间复杂度为 O(log n)。
• HEAPPOP：从最大堆中取出最大值或从最小堆中取出最小值，并将剩余的数组保持堆结构，时间复杂度为 O(log n)。
• HEAPSORT：借由 HEAPFY 建堆和 HEAPPOP 堆数组进行排序，时间复杂度为 O(n log n)，空间复杂度为 O(1)。

堆结构的一个常见应用是建立优先队列（Priority Queue）。

介绍

二叉搜索树（英语：Binary Search Tree），也称为 二叉查找树、有序二叉树（Ordered Binary Tree）或排序二叉树（Sorted Binary Tree），是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(logn)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。

题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例1:

1
2
3

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

简介

RocketMQ提供了两种消费模式，Push和Pull，大多数场景使用的是Push模式，而在Pull模式下，需要业务应用代码自身去完成比较多的事情，例如需要Consumer端自己保存消息消费的offset偏移量至本地变量中。因此在实际应用中用的较少。

在源码中这两种模式分别对应的是DefaultMQPushConsumer类和DefaultMQPullConsumer类。Push模式实际上在内部还是使用的Pull方式实现的，通过Consumer采用长轮询方式不断地轮询Broker获取消息，当不存在新消息时，Broker端会挂起Pull请求，直到有新消息产生才取消挂起，返回新消息。

之所以Push模式不设计为Broker主动推送，我猜测一是在于加大了Broker的压力，二是分布式系统中并不知道消费者的消费能力-这一点不可控

在上篇博客RocketMQ-消息存储中，已经看到了消息是如何从 Broker 最终存储到MappedFile内存缓冲区中的，但是此时消息存储的任务并没有完成，因为消息还没有刷盘，即存储到文件中，本篇继续探索RocketMQ是如何进行消息刷盘的。

刷盘策略

CommitLog在初始化的时候，见构造方法 会根据配置，启动两种不同的刷盘策略。

1
2
3
4
5
6

if (FlushDiskType.SYNC_FLUSH == defaultMessageStore.getMessageStoreConfig().getFlushDiskType()) {
    this.flushCommitLogService = new GroupCommitService();
} else {
    this.flushCommitLogService = new FlushRealTimeService();
}
this.commitLogService = new CommitRealTimeService();

• CommitRealTimeService：异步刷盘并且开启内存字节缓冲区
• FlushRealTimeService：异步刷盘但是不开启内存字节缓冲区
• GroupCommitService：同步刷盘

同步刷盘：当消息追加到内存后，就立即刷到文件中存储
异步刷盘：当消息追加到内存中，并不是立即刷到文件中，而是在后台任务中进行异步操作

每个Broker都对应有一个MessageStore，专门用来存储发送到它的消息，不过MessageStore本身不是文件，只是存储的一个抽象，MessageStore 中保存着一个 CommitLog，CommitLog 维护了一个 MappedFileQueue，而MappedFileQueue 中又维护了多个 MappedFile，每个MappedFile都会映射到文件系统中一个文件，这些文件才是真正的存储消息的地方，MappedFile的文件名为它记录的第一条消息的全局物理偏移量。

RocketMQ-消息发送

由于消息发送还涉及到延迟发送，顺序发送，批量发送等情况，分享下自己看源码总结的一般同步发送消息逻辑。