红黑树、B(+) 树、跳表、AVL 等数据结构，应用场景及分析

本文整理自网络技术资料，旨在分析常见数据结构（红黑树、B/B+ 树、跳表、AVL 树等）的特性、应用场景及工程实现差异，并附带相关英文缩写说明。

参考讨论：知乎 - 红黑树、B(+) 树、跳表、AVL 等数据结构，应用场景及分析

1. 核心数据结构概述

数据结构类型主要特点典型应用场景
AVL 树平衡二叉树高度平衡，左右子树树高差不超过 1，严格平衡。Windows 进程地址空间管理（历史版本）、查找多插入删除少的场景。
红黑树 (RB Tree)平衡二叉树近似平衡，路径长度不超过 2 倍，旋转代价较低。C++ STL (map/set)、Java TreeMap、Linux 进程调度 (CFS)、epoll、Nginx Timer。
B/B+ 树多路查找树分支多、层数少，减少磁盘 IO。B+ 树数据仅存叶子节点。文件系统、数据库索引 (如 MySQL)。
Trie 树字典树前缀共享，节省空间但耗内存。字符串统计排序、搜索引擎提示、IP 选路。
跳表 (Skip List)基于链表并发友好，局部更新，支持范围查询。Redis 有序集合 (ZSet)。

2. 典型应用场景分析

2.1 操作系统与内核

  • AVL 树：早期 Windows 对进程地址空间的管理曾用到 AVL 树。

  • 红黑树：

    • Linux 内核：epoll 实现中用红黑树管理事件块；著名的完全公平调度器 (Completely Fair Scheduler, CFS) 用红黑树管理进程控制块。
    • Nginx：用红黑树管理 Timer 等。
    • 其他：Java 的 TreeMap 实现。

2.2 数据库与文件系统

  • B/B+ 树：主要用在文件系统以及数据库中做索引。例如 MySQL 的 B-Tree Index。由于磁盘 IO 耗时，多路查找树能有效减少磁盘查找次数。
  • B+ 树特性：作为 B 树的变种，有 n 棵子树的节点中含有 n 个关键字，关键字仅用于索引，数据保存在叶子节点，专为文件系统而生。

2.3 字符串与网络

  • Trie 树：典型应用是前缀匹配。

    • 搜索引擎：输入时给予提示。
    • 网络选路：IP 选路也是前缀匹配，一定程度会用到 Trie。
    • 变种：前缀树 (Prefix Tree)、后缀树 (Suffix Tree)、Radix Tree (Patricia Tree, Compact Prefix Tree)、Crit-bit Tree、Double Array Trie。
    • 应用：Radix Tree 用于 Linux 内核、Nginx；后缀树用于查找字符串出现次数、最长公共部分等。

3. 跳表与红黑树：Redis 的选型分析

在 Redis 中，使用跳表 (Skip List) 而不是红黑树来存储管理有序集合元素（一级元素/Key）。需要注意的是，Redis 中还有 ziplist，它是一个非常省内存的链表（代价是性能略低），因此在 hash 元素个数很少（如几十个）时，使用 ziplist 可以在性能损失很小的情况下节约内存。

3.1 并发与性能考量

在 Server 端对并发和性能有要求的情况下，选择跳跃表而非红黑树的原因如下：

  • 锁竞争代价：如果单纯比较性能，跳跃表和红黑树相差不大。但在并发环境下，更新数据时跳跃表需要更新的部分较少，锁住的节点较少，线程争锁代价相对低。
  • 局部性操作：红黑树在插入和删除时可能需要 rebalance 操作，涉及整个树的其他部分；而 Skip List 的操作更加局部化，锁需要盯住的节点更少，性能表现更好。

3.2 Redis 作者的观点

Redis 作者关于选用 Skip List 的原因描述如下：

  1. 内存消耗：它们并不是非常消耗内存。基本上取决于你。改变节点拥有给定层数的概率参数，可以使它们比 B 树更节省内存。（注：跳表的一个缺点是耗内存，因为要重复分层存节点，但可以通过调参降低消耗，与平衡树结构达到差不多。）
  2. 范围操作与缓存局部性：有序集合经常是许多 ZRANGE 或 ZREVRANGE 操作的目标，即作为链表遍历跳表。在此操作下，跳表的缓存局部性 (Cache Locality) 至少与其他类型的平衡树一样好。（注：Redis 经常有范围操作，利用跳表里面的双向链表可以方便地操作。）

4. 工程实现视角：红黑树与 B+ 树

从工程角度区分红黑树与 B+ 树的应用场景：

  • 内存管理方式：

    • 红黑树：一个 Node 只存一对 KV，可以使用类似嵌入式链表的方式实现。数据结构本身不管理内存，比较轻量级，使用更灵活也更省内存。例如一个 Node 可以同时存在若干个树或链表中，内核中比较常见。
    • B+ 树：每个 Node 要存多对 KV，Node 结构的内存一般由数据结构自己来管，是真正意义上的容器 (Container)。相对嵌入式方法实现的红黑树，好处是用法简单，自己管理内存更容易做 Lock-free。

  • CPU Cache 命中率：

    • B+ 树：一个 Node 存多对 KV 的方式 CPU Cache 命中率更高。因此用户态实现的高并发索引一般还是选 B+ 树。
    • B 树 vs B+ 树：B 树的中间节点比 B+ 树多存了 Value，同样出度的情况下 Node 更大，相对来说 CPU Cache 命中率不如 B+ 树。

  • 无锁扫描特性：

    • B+ 树的扫描特性（链表串起来的叶子节点）在无锁情况下是很难做的。目前见到的无锁 B+ 树叶子节点通常是不串起来的。

5. 算法特性与选型指南

5.1 查找树选型 (AVL vs 红黑树)

  • AVL 树：

    • 特点：严格平衡二叉树，平衡条件非常严格（树高差只有 1）。插入或删除不满足条件就要通过旋转来保持平衡。
    • 代价：旋转非常耗费时间，维护高度平衡的代价比获得的效率收益大。
    • 适用：插入删除次数比较少，但查找多的情况。

  • 红黑树：

    • 特点：近似平衡。通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长 2 倍。
    • 优势：相对于 AVL 树，它的旋转保持平衡次数较少。
    • 适用：插入删除次数多的情况下，用红黑树取代 AVL。

5.2 磁盘索引选型 (B 树 vs B+ 树)

  • 共同点：都是多路查找树，用于数据库系统，目的是有效减少磁盘 IO 次数。
  • 差异：B+ 树是为文件系统而生的，数据都保存在叶子节点，中间节点只存索引。

6. 红黑树的维护机制

当查找树的结构发生改变时，红黑树的条件可能被破坏，需要通过调整使得查找树重新满足条件。调整可以分为两类：

  1. 颜色调整：即改变某个节点的颜色。

  2. 结构调整：即改变检索树的结构关系。包含两个基本操作：

    • 左旋 (Rotate Left)
    • 右旋 (Rotate Right)

核心原则：无论有多少情况，具体的调整操作只有两种：改变某些节点的颜色，或对某些节点进行旋转。

关于红黑树的详细讲解，可参考以下文章：

7. 附录：常见英文缩写

整理自相关技术讨论中的常用缩写：

缩写全称含义备注
imho / imoin my humble opinion / in my opinion在我看来常见于论坛
idkI don't know我不知道-
roflrolling on the floor laughing笑到摔到地上表示非常好笑
roflmaorolling on the floor laughing my ass off超级搞笑前两个的结合版
sthsomething某事某物-
nthnothing什么也没有-
plzplease请按照读音缩写，字尾是 z 音
thxthanks谢谢按照发音，ks 可以用字母 X 代替
说明：本文内容基于经典数据结构理论与主流开源软件（如 Linux Kernel, Redis, MySQL）的历史实现整理。部分外部链接（如搜狐文章）发布于 2016 年，具体内核版本或软件版本的实现细节可能随时间演进有所调整，请以官方最新文档为准。