07 | 为什么Stream使用了Radix Tree？-Redis源码剖析与实战

当前位置:　首页>> 技术小册>> Redis源码剖析与实战

### 07 | 为什么Stream使用了Radix Tree？

在Redis的众多高级特性中，Stream是一种用于消息传递的强大数据类型，它支持高效的消息发布与订阅、消息持久化以及消息的消费确认机制。而Radix Tree（基数树），作为一种高效的数据结构，在Redis中被用来实现Stream的内部结构，为Stream提供了快速的查询、插入和删除操作。本章将深入探讨为什么Redis选择Radix Tree作为Stream的底层数据结构，并详细解析其实现原理及优势。

#### 一、Radix Tree概述

Radix Tree，也称为PATRICIA Trie或Compact Prefix Tree，是一种有序字典树，特别适用于处理字符串数据。与普通的Trie树相比，Radix Tree在节点只有一个子节点时会进行压缩，以减少树的深度和节点数量，从而提高空间效率和查询速度。在Redis中，Radix Tree的实现主要集中在`rax.c`和`rax.h`等文件中，通过`raxNode`结构体定义节点，并包含了一系列操作函数，如节点的创建、插入、查找和删除等。

#### 二、Stream的需求分析

Redis Stream的设计目标是为用户提供一种可靠的消息队列机制，支持多种场景下的消息传递需求。具体来说，Stream需要满足以下几个方面的要求：

1. **高性能**：能够快速处理大量消息的发布与订阅，同时支持高效的查询操作。
2. **持久化**：确保消息在Redis重启后依然可用。
3. **消息确认机制**：支持消息的消费确认，确保消息被正确处理。
4. **有序性**：保证消息按照发布顺序被消费。

为了满足这些需求，Redis需要一种高效的数据结构来管理Stream中的消息ID和消息体。消息ID在Stream中扮演着至关重要的角色，它不仅是消息的唯一标识，还决定了消息的顺序。在Redis Stream中，消息ID通常由时间戳和序号组成，这种结构使得消息ID之间具有很强的顺序性和可比较性。

#### 三、Radix Tree在Stream中的应用

Redis选择Radix Tree作为Stream的底层数据结构，主要基于以下几个方面的考虑：

1. **高效的查询性能**

Radix Tree通过前缀共享的方式，减少了节点的数量，降低了树的深度，从而提高了查询效率。在Stream中，由于消息ID之间具有相似的前缀（时间戳部分），Radix Tree能够迅速定位到特定的消息ID，支持快速的点查询和范围查询。

2. **内存友好**

通过节点压缩，Radix Tree显著减少了内存的占用。在Stream中，消息ID的时间戳部分往往很长且相似，如果不进行压缩，将会占用大量的内存空间。Radix Tree通过压缩连续只有一个子节点的节点，有效降低了内存的使用率。

3. **支持快速插入和删除**

Radix Tree的插入和删除操作相对简单且高效。在插入新消息时，Redis会根据消息ID的字节逐步遍历树，并根据是否遇到相同前缀路径来决定是否分裂节点或创建新节点。如果遇到连续相同前缀路径，则进行节点压缩以优化空间。删除操作虽然相对复杂，但Redis通过精细的内存管理，确保了操作的高效性和内存的正确释放。

4. **灵活性**

Radix Tree的每个节点都可以携带关联数据，这使得它在Redis中有多种用途。在Stream中，每个节点不仅存储了消息ID的前缀信息，还关联了具体的消息体。这种设计使得Radix Tree能够灵活地支持多种查询和操作需求。

#### 四、Radix Tree在Stream中的实现细节

在Redis Stream的实现中，Radix Tree主要用于管理消息ID和消息体的映射关系。具体来说，Redis通过以下步骤将Radix Tree应用于Stream：

1. **初始化Radix Tree**

当创建一个新的Stream时，Redis会初始化一个空的Radix Tree来存储消息ID和消息体的映射关系。此时，树中没有任何节点。

2. **插入消息**

当向Stream中发布新消息时，Redis会生成一个唯一的消息ID，并将其与消息体一起插入到Radix Tree中。插入操作从根节点开始，根据消息ID的字节逐步深入树中，直到找到或创建一个能够存储该消息ID的节点。然后，Redis会将消息体与该节点关联起来。

3. **查询消息**

用户可以通过消息ID来查询Stream中的消息。Redis会根据消息ID的字节逐步遍历Radix Tree，直到找到对应的节点。如果找到了该节点，Redis就会返回与该节点关联的消息体。

4. **删除消息**

在某些情况下，用户可能需要从Stream中删除消息。Redis会根据消息ID找到对应的节点，并将其从Radix Tree中删除。如果删除操作导致节点变为空，Redis还会进一步清理树中的空节点以释放内存。

5. **内存管理**

Redis通过精细的内存管理来确保Radix Tree的高效运行。在插入和删除操作中，Redis会动态地分配和释放内存空间，以确保树的结构和内存分配始终处于最优状态。

#### 五、总结

Redis选择Radix Tree作为Stream的底层数据结构，主要是因为它具有高效的查询性能、内存友好、支持快速插入和删除以及灵活性等优点。这些特点使得Radix Tree成为实现Redis Stream的理想选择。通过深入分析Radix Tree在Redis Stream中的实现原理和应用场景，我们可以更好地理解Redis的高级特性和底层实现机制，从而更好地利用Redis来满足各种复杂的应用需求。

在本书的后续章节中，我们将继续探讨Redis的其他高级特性和底层实现机制，如Redis的持久化机制、复制机制、集群管理以及Redis的模块化设计等。希望这些内容能够帮助读者更全面地了解Redis的内部原理和应用方法。

该分类下的相关小册推荐：

Redis面试指南

Redis零基础到实战

Redis核心技术与实战

Redis的Lua脚本编程