特殊数据结构：Trie、Bitmap、Bloom Filter

#Trie · #Bitmap · #BloomFilter · #HyperLogLog · #CuckooFilter · #CountMinSketch · #RoaringBitmap · #RadixTree · #Redis · #Elasticsearch · #概率数据结构

这三者解决的是传统结构不擅长的领域：前缀匹配（Trie）、精确存在判定+去重（Bitmap）、概率存在判定（Bloom Filter）。它们在搜索引擎、数据库、缓存、安全领域无处不在。

1. Trie（前缀树 / 字典树）

1.1 结构

            root
          /  |  \
         c   d   t
        /    |     \
       a     o      e
      / \    |     / \
     r   t   g    a   n
                    / \
                   m   d

查找 "cat"：root → c → a → t（每层匹配一个字符），时间复杂度 = O(len(key))。

mermaid

flowchart LR
    subgraph Insert["插入 'car' 和 'cat'"]
        direction TB
        R((root)) --> C((c))
        C --> A((a))
        A --> R1((r★))
        A --> T((t★))
    end

    subgraph Search["查找 'cat'"]
        direction TB
        S1["root → c"] -->|匹配| S2["c → a"]
        S2 -->|匹配| S3["a → t"]
        S3 -->|"匹配 isEnd=true"| S4["✅ 找到"]
    end

    subgraph Prefix["前缀搜索 'ca'"]
        direction TB
        P1["root → c → a"] -->|到达| P2["遍历所有子树"]
        P2 --> P3["结果: car, cat"]
    end

    style R1 fill:#4CAF50,color:#fff
    style T fill:#4CAF50,color:#fff
    style S4 fill:#4CAF50,color:#fff
    style P3 fill:#2196F3,color:#fff

1.2 基本实现

type TrieNode struct {
    children [26]*TrieNode  // 假设只存小写字母
    isEnd    bool
}

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        idx := ch - 'a'
        if node.children[idx] == nil {
            node.children[idx] = &TrieNode{}
        }
        node = node.children[idx]
    }
    node.isEnd = true
}

func (t *Trie) Search(word string) bool {
    node := t.root
    for _, ch := range word {
        idx := ch - 'a'
        if node.children[idx] == nil {
            return false
        }
        node = node.children[idx]
    }
    return node.isEnd
}

// 前缀搜索：是否存在以 prefix 开头的单词
func (t *Trie) StartsWith(prefix string) bool {
    node := t.root
    for _, ch := range prefix {
        idx := ch - 'a'
        if node.children[idx] == nil { return false }
        node = node.children[idx]
    }
    return true
}

操作	复杂度
Insert	O(L) — L 为 key 长度
Search	O(L)
StartsWith	O(L)
删除	O(L)

1.3 空间优化：压缩 Trie（Radix Tree / Patricia Trie）

标准 Trie:                    压缩 Trie:
  c → a → r                        car
  c → a → t                        ca ─┬─ r
                                     └─ t

合并只有一个子节点的链 → Radix Tree。Linux 内核的页缓存、Nginx 的 IP 路由、etcd 的 boltdb 都用 Radix Tree。

1.4 各系统中的应用

系统	使用场景	变体
Elasticsearch	倒排索引的 term dictionary	FST (有限状态转换器)
Redis	Rax (Radix tree)	用于 Stream 的 consumer group
Linux 内核	页缓存（address_space）	Radix tree
Nginx	IP 地理位置查找	Radix tree
路由表	最长前缀匹配（Longest Prefix Match）	Patricia Trie
搜索引擎提示	搜索框自动补全	Trie
拼写检查	编辑距离搜索	Trie + DFS

1.5 搜索提示（Autocomplete）实现

// 找到以 prefix 为前缀的所有单词
func (t *Trie) Autocomplete(prefix string) []string {
    node := t.findNode(prefix)
    if node == nil { return nil }
    result := []string{}
    t.collect(node, prefix, &result)
    return result
}

func (t *Trie) collect(node *TrieNode, prefix string, result *[]string) {
    if node.isEnd {
        *result = append(*result, prefix)
    }
    for i, child := range node.children {
        if child != nil {
            t.collect(child, prefix+string('a'+i), result)
        }
    }
}

2. Bitmap（位图）

2.1 原理

用 1 bit 表示一个元素是否存在：

bitmap[0..7]: 0b10110010
              │││││││└─ id=0: 不存在
              ││││││└── id=1: 存在
              │││││└─── id=2: 不存在
              ...（依此类推）

内存使用：n 个元素只需 n/8 字节 → 极致压缩。

2.2 基本操作

type Bitmap struct {
    data []uint64
    size int
}

func (b *Bitmap) Set(pos int) {
    b.data[pos/64] |= (1 << (pos % 64))
}

func (b *Bitmap) Clear(pos int) {
    b.data[pos/64] &^= (1 << (pos % 64))
}

func (b *Bitmap) Test(pos int) bool {
    return b.data[pos/64]&(1<<(pos%64)) != 0
}

// 统计 1 的个数（popcount — 用 CPU 指令）
func (b *Bitmap) Count() int {
    total := 0
    for _, v := range b.data {
        total += bits.OnesCount64(v)  // 编译为 POPCNT 指令
    }
    return total
}

2.3 应用

场景	说明
用户签到	Bitmap 存 365 天签到记录，仅 46 字节
布隆过滤器基础	多个 Hash 函数 + Bitmap
Reddit 用户在线状态	数亿用户仅需几十 MB
去重	见过这个 ID 吗？Set bit + Test
ID 分配器	Find first zero（找空闲 ID）
权限系统	每个 bit 表示一种权限

2.4 Redis Bitmap

bash

SETBIT user:1001:login 0 1     # 2024-01-01 签到
SETBIT user:1001:login 1 1     # 2024-01-02 签到
BITCOUNT user:1001:login       # 签到天数
BITPOS user:1001:login 0       # 第一个未签到日

# 统计连续签到天数（两个 bitmap 的 AND）
BITOP AND result user:1001:login user:1002:login
BITCOUNT result                # 两人共同签到天数

3. Bloom Filter（布隆过滤器）

3.1 原理

Insert "hello":
  hash1("hello") = 3 → set bit 3
  hash2("hello") = 7 → set bit 7
  hash3("hello") = 11 → set bit 11

  bitmap: [0 0 0 1 0 0 0 1 0 0 0 1 0 0 0]
           0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Query "hello":
  检查 bit 3,7,11 → 全是 1 → "可能存在"

Query "world":
  检查 bit 2,5,9 → bit 2 是 0 → "肯定不存在"

核心特性：

说"不存在" → 100% 确定（无假阴性）
说"可能存在" → 有假阳性概率

mermaid

sequenceDiagram
    participant App as 应用层
    participant BF as Bloom Filter
    participant Cache as Redis/缓存
    participant DB as 数据库

    Note over App,DB: 缓存穿透防护流程

    App->>BF: key "user_12345" 存在吗？
    BF-->>App: ❌ 绝对不存在
    Note over App: 直接返回 404<br/>不打 DB

    App->>BF: key "user_67890" 存在吗？
    BF-->>App: ⚠️ 可能存在
    App->>Cache: 查缓存 user_67890
    alt 缓存命中
        Cache-->>App: 返回数据
    else 缓存未命中
        App->>DB: 查数据库 user_67890
        DB-->>App: 返回数据(或真的不存在)
    end

3.2 假阳性率计算

假阳性率 = (1 - e^(-k*n/m)) ^ k
其中:
  m = bitmap 大小（bit 数）
  k = hash 函数数量
  n = 已插入元素数量

最优 k = (m/n) * ln(2) ≈ 0.693 * m/n
此时假阳性率 = (0.6185) ^ (m/n)

例子：100 万元素，期望 1% 假阳性 → m ≈ 960 万 bit（≈ 1.2 MB），k ≈ 7

3.3 实现

type BloomFilter struct {
    bitset []uint64
    k      uint64  // hash 函数个数
    m      uint64  // bitmap 总 bit 数
}

func (bf *BloomFilter) Add(item []byte) {
    h1, h2 := hash(item)  // 两个基础 hash
    for i := uint64(0); i < bf.k; i++ {
        pos := (h1 + i*h2) % bf.m  // Double hashing 模拟 k 个 hash
        bf.bitset[pos/64] |= (1 << (pos % 64))
    }
}

func (bf *BloomFilter) Contains(item []byte) bool {
    h1, h2 := hash(item)
    for i := uint64(0); i < bf.k; i++ {
        pos := (h1 + i*h2) % bf.m
        if bf.bitset[pos/64]&(1<<(pos%64)) == 0 {
            return false  // 绝对不存在
        }
    }
    return true  // 可能存在
}

3.4 变体

变体	特点
Counting Bloom Filter	每个 bucket 换成计数器，支持删除
Cuckoo Filter	支持删除 + 更低假阳性 + 更省空间
Scalable Bloom Filter	元素超预期时动态增长
RedisBloom	Redis 模块，支持布隆 + 布谷鸟 + Top-K

3.5 应用

场景	说明
缓存穿透防护	"key 存在吗？" → Bloom filter 说不在 → 直接拒绝，不打 DB
数据库 LSM-Tree	LevelDB/RocksDB 用 Bloom filter 判断 SSTable 是否可能含某 key
爬虫 URL 去重	数十亿 URL，布隆过滤器极省内存
Chrome 恶意 URL	Safe Browsing 用布隆过滤已知恶意站点
比特币 SPV	轻节点用布隆过滤器筛选相关交易
Cassandra / HBase	判断 SSTable 是否含要找的 row key

3.6 Redis Bloom Filter 示例

bash

# 使用 RedisBloom 模块
BF.ADD myfilter item1
BF.EXISTS myfilter item1    # → 1（可能存在）
BF.EXISTS myfilter item2    # → 0（绝对不存在）

# 自定义容量和误报率
BF.RESERVE myfilter 0.01 1000000
#   0.01 = 1% 假阳性率, 1000000 = 预期元素数

4. 三者对比

维度	Trie	Bitmap	Bloom Filter
用途	前缀匹配、字典	精确去重、签到	概率去重、加速查询
准确度	100%	100%	有假阳性，无假阴性
空间（1000万 key）	~200MB+	~1.2MB	~12MB(1%假阳性)
支持删除	✅	✅	❌（Counting BF 可以）
查询 O()	O(L)	O(1)	O(k)
前缀搜索	✅	❌	❌
典型场景	搜索提示、路由	签到、ID 去重	缓存穿透、LSM 查询加速

选择决策

需要前缀搜索？ → Trie / Radix Tree
需要 100% 精确，空间够？ → HashMap 或 Bitmap
空间极有限，接受小概率误判？ → Bloom Filter
还要支持删除？ → Cuckoo Filter

5. Cuckoo Filter — 支持删除的 Bloom Filter

Cuckoo Filter 解决了 Bloom Filter 不支持删除的痛点，空间效率相当，且查询性能更好。

原理：双哈希 + 布谷鸟驱逐

插入元素 x:
  1. 计算两个候补位置: h1(x), h2(x) = h1(x) ⊕ hash(fingerprint(x))
  2. 如果 h1 位置空 → 放入
  3. 否则检查 h2 位置 → 空则放入
  4. 如果两个位置都满了 → 随机选一个，挤出原有元素
  5. 被挤出的元素重新插入到它的另一个候补位置
  6. 重复直到成功或达到最大驱逐次数（如 500 次）→ 扩容

删除: 直接清除 fingerprint（无需额外结构，不像 Counting BF）
查询: 检查两个候补位置是否有匹配的 fingerprint

// Cuckoo Filter 核心结构
type CuckooFilter struct {
    buckets [][]fingerprint // 每桶 4 个 slot（一个 cache line）
    size    int
}

func (cf *CuckooFilter) Insert(item []byte) bool {
    fp := fingerprint(item)
    i1 := hash(item)
    i2 := i1 ^ hash(fp)  // 部分键布谷鸟哈希

    // 尝试放入两个桶
    if cf.buckets[i1].insert(fp) || cf.buckets[i2].insert(fp) {
        return true
    }

    // 布谷鸟驱逐
    idx := i1
    for n := 0; n < 500; n++ {
        fp, cf.buckets[idx].evict(fp) // 随机踢出一个，放入新的
        idx = idx ^ hash(fp)           // 被踢出的找另一个位置
        if cf.buckets[idx].insert(fp) {
            return true
        }
    }
    return false // 需要扩容
}

空间对比（1 亿元素，1% 假阳性）：

结构	空间	支持删除
Bloom Filter	~115 MB	❌
Counting Bloom Filter	~460 MB	✅
Cuckoo Filter	~100 MB	✅

6. Count-Min Sketch — 频率估计

统计频率但不想存全量数据？Count-Min Sketch 用固定大小的二维数组给出上限估计。

结构: d 行 × w 列的计数器矩阵（d 个独立的哈希函数）

更新: 对每个哈希函数 h_i，matrix[i][h_i(item)] += 1

查询: 返回 min(matrix[0][h0(item)], matrix[1][h1(item)], ..., matrix[d-1][h_{d-1}(item)])
       → 取最小值作为频率估计（因为所有计数器都 ≥ 真实值）

特性:
  - 总是返回"上限估计"（可能高估，不会低估）
  - 误差: 以概率 1-δ，误差 ≤ ε × N（N = 所有计数的总和）
  - 空间: d × w = ⌈ln(1/δ)⌉ × ⌈e/ε⌉

type CountMinSketch struct {
    matrix [][]uint64
    d, w   int
    hashes []hash.Hash64
}

func (cms *CountMinSketch) Add(item []byte) {
    for i := 0; i < cms.d; i++ {
        cms.hashes[i].Reset()
        cms.hashes[i].Write(item)
        idx := cms.hashes[i].Sum64() % uint64(cms.w)
        cms.matrix[i][idx]++
    }
}

func (cms *CountMinSketch) Estimate(item []byte) uint64 {
    min := uint64(^uint64(0)) // 最大值
    for i := 0; i < cms.d; i++ {
        cms.hashes[i].Reset()
        cms.hashes[i].Write(item)
        idx := cms.hashes[i].Sum64() % uint64(cms.w)
        if cms.matrix[i][idx] < min {
            min = cms.matrix[i][idx]
        }
    }
    return min
}

应用：统计热搜词频率、异常流量检测、数据库查询频率统计。

6.1 与 HyperLogLog 协同使用

Count-Min Sketch: 统计频率（"这个词出现了多少次"）
HyperLogLog:      统计基数（"有多少个不同的词"）

互补使用:
  - HLL: 统计 UV（Unique Visitors）
  - CMS: 统计 PV（Page Views）或 top-K 热门页面

6.2 HyperLogLog 数学原理

HyperLogLog 能以 12KB 内存估算 2^64 个元素的基数，误差仅 0.81%。它的数学基础是伯努利试验和调和平均数。

伯努利试验与低位连续零

抛一枚均匀硬币，记录"直到出现正面"所需的抛掷次数：

第 1 次就抛到正面: 概率 = 1/2
连续 2 次反面后正面: 概率 = 1/4
连续 3 次反面后正面: 概率 = 1/8
...
连续 k 次反面后正面: 概率 = 1/(2^k)

这意味着：连续 k 次反面的情况极其罕见。如果某人说他连续抛了 10 次反面，他大概率已经抛了几百次（2^10 次期望）。

mermaid

flowchart TB
    subgraph Bernoulli["伯努利试验与低位连续零"]
        direction TB
        H1["对每个元素求 hash → 64位二进制"]
        H2["观察最低位连续 0 的个数"]
        H3["如果见到连续 15 个 0<br/>= 概率 1/2^15 = 1/32768"]
        H4["→ 说明大概率有 ~32768 种不同元素"]
    end

    H1 --> H2 --> H3 --> H4

核心洞察：如果把每个元素的哈希值看作一次抛硬币，最少见的现象（最长连续零）可以反推"已经做了多少次试验"（即不同元素的数量）。

从 LogLog 到 HyperLogLog

LogLog（Durand & Flajolet, 2003）：

1. 对每个元素 hash → 64 位
2. 取前 p 位作为桶索引（如 p=14 → 16384 个桶）
3. 在每个桶内，记录剩下的 50-p 位中"低位连续零的最大个数"
4. 基数值 ≈ constant × 2^(所有桶的平均最大连续零)

问题：算术平均数受极端值（outlier）影响大。如果一个桶"运气好"碰到特别长的连续零，整个估算被拉高。

HyperLogLog（Flajolet et al., 2007）的改进：用调和平均数代替算术平均数。

text

算术平均: (x₁ + x₂ + ... + x_m) / m    ← 被极端值拉偏
调和平均: m / (1/x₁ + 1/x₂ + ... + 1/x_m) ← 不受极端值影响

HyperLogLog 估计值 = α_m × m² / Σ(2^(-M[j]))

其中:
  α_m: 修正系数（仅依赖于桶数 m，有解析公式）
  M[j]: 第 j 个桶的最大连续零个数

完整算法流程

mermaid

flowchart TB
    A["输入: 元素 x"] --> B["hash(x) → 64位整数"]
    B --> C{"取高 p 位作为桶索引 idx"}
    C --> D["低 64-p 位中<br/>找最低位连续零的个数 w"]
    D --> E{"w > M[idx] ?"}
    E -->|是| F["更新 M[idx] = w"]
    E -->|否| G["跳过"]
    F --> H{"还有更多元素?"}
    G --> H
    H -->|是| A
    H -->|否| I["计算调和平均数<br/>E = α_m × m² / Σ(2^(-M[j]))"]
    I --> J{"E < 2.5×m ?"}
    J -->|"是 (小基数)"| K["使用 Linear Counting 修正"]
    J -->|否| L{"E > 2^32/30 ?"}
    L -->|"是 (大基数)"| M["使用大范围修正: -2^32×ln(1-E/2^32)"]
    L -->|否| N["直接输出 E"]

// HyperLogLog 核心结构（简化）
type HyperLogLog struct {
    p    uint8     // 精度参数：桶数 = 2^p
    m    uint32    // 桶数
    M    []uint8   // 每个桶的最大连续零数
    alpha float64  // 修正系数
}

func New(p uint8) *HyperLogLog {
    m := uint32(1) << p
    // α_m 的解析值（当 m ≥ 128 时）
    alpha := 0.7213 / (1 + 1.079/float64(m))
    return &HyperLogLog{
        p: p, m: m,
        M:    make([]uint8, m),
        alpha: alpha,
    }
}

func (h *HyperLogLog) Add(item []byte) {
    x := hash64(item)
    idx := x >> (64 - h.p)               // 高 p 位 → 桶索引
    w := countTrailingZeros(x<<h.p>>h.p) + 1  // 低位的连续零数 + 1

    if w > h.M[idx] {
        h.M[idx] = w
    }
}

func (h *HyperLogLog) Count() uint64 {
    // 调和平均数
    sum := 0.0
    zeroBuckets := 0
    for i := uint32(0); i < h.m; i++ {
        sum += 1.0 / float64(uint64(1)<<h.M[i])
        if h.M[i] == 0 {
            zeroBuckets++
        }
    }

    estimate := h.alpha * float64(h.m*h.m) / sum

    // 小基数修正 (Linear Counting)
    if estimate <= 2.5*float64(h.m) && zeroBuckets > 0 {
        estimate = float64(h.m) *
                   math.Log(float64(h.m)/float64(zeroBuckets))
    }

    return uint64(estimate)
}

// 计算低位连续零的个数
// 等价于：从最低位开始数，有多少个连续的 0
// 如 0b...101000 → trailingZeros = 3
func countTrailingZeros(x uint64) int {
    if x == 0 { return 64 }
    return bits.TrailingZeros64(x)
}

精度与内存权衡

p (桶数位数)	桶数 m=2^p	内存	标准误差
4	16	12 B	26%
8	256	192 B	6.5%
10	1024	768 B	3.25%
12	4096	3 KB	1.62%
14	16384	12 KB	0.81% ← Redis 默认
16	65536	48 KB	0.41%
18	262144	192 KB	0.20%

误差公式: σ ≈ 1.04 / √m

m=16384 → σ ≈ 1.04/128 ≈ 0.81%（Redis 的实现）
m=65536 → σ ≈ 1.04/256 ≈ 0.41%

加倍桶数 → 误差减半 → 内存翻倍
这是典型的"精度换空间"权衡

为什么不能精确计数？

text

HyperLogLog 不保存原始元素，只保存每个桶的最大连续零数。
这是不可逆的信息压缩——多个不同元素可能产生相同的 M[j] 值。

例如:
  元素 A: hash = 0b...0010  → trailingZeros = 1 → w = 2
  元素 B: hash = 0b...0110  → trailingZeros = 1 → w = 2
  元素 C: hash = 0b...0001  → trailingZeros = 0 → w = 1

  M[j] = max(2, 2, 1) = 2
  无法从 M[j]=2 反推出"到底有 2 个还是 3 个元素"

这就是信息丢失，也是 HLL 如此节省空间的代价。

Redis HyperLogLog 的使用

bash

PFADD uv:page:home user_001 user_002 user_003
PFCOUNT uv:page:home  # → 3

# 合并多个 HLL
PFADD uv:page:about user_002 user_004
PFMERGE uv:total uv:page:home uv:page:about
PFCOUNT uv:total  # → 4 (001,002,003,004 — 自动去重)

Redis 使用稀疏表示（少量元素时）和密集表示（大量元素时）的混合编码，进一步节省内存。初始时只需要几 KB 而非完整的 12KB。

7. Radix Tree (Patricia Trie) — 压缩前缀树

标准 Trie 的每个节点只存一个字符，导致路径冗长、节点数多。Radix Tree 合并单子节点路径，大幅减少节点数。

标准 Trie (存 "romane", "romanus", "romulus"):
  root → r → o → m → a → n → e → (end)
                          → u → s → (end)
                     → u → l → u → s → (end)
  节点数: 15

Radix Tree (压缩版):
  root → "rom" → "an" → "e" → (end)
                     → "us" → (end)
               → "ulus" → (end)
  节点数: 7（减少 53%）

type RadixNode struct {
    prefix   string               // 合并的字符串片段
    value    interface{}          // 叶子节点的值
    children map[byte]*RadixNode  // 按首字符索引子节点
}

Radix Tree 的工程应用：

系统	用途
Linux 内核	页缓存基数树（Page Cache Radix Tree）
Nginx	路由匹配（将 URL pattern 存为 Radix Tree）
Redis Stream	流 ID 索引（Rax — Redis Radix Tree）
etcd	Key 索引（BoltDB 底层）
Go net/http	`http.ServeMux` 路由匹配（实际上用了 radix tree 类似的压缩方法）

8. Roaring Bitmap — 高效压缩位图

传统 Bitmap 在稀疏数据场景下浪费严重（如存储用户 ID=1 和 ID=1亿两个值需要 12.5MB）。Roaring Bitmap 通过"分桶 + 自适应容器"将空间和计算同时优化。

8.1 核心设计：高低 16 位拆分

32 位整数 (如用户 ID) → 高 16 位 + 低 16 位

例如: 1234567890 = 0x499602D2
  → 高 16 位 = 0x4996 = 18838  (作为"桶"的索引)
  → 低 16 位 = 0x02D2 = 722    (作为桶内的值)

所有高 16 位相同的数值放在同一个桶中。
桶的数量 ≤ 2^16 = 65536（实际上只创建有数据的桶）。

8.2 三种自适应容器

一个桶（高 16 位相同）内的数值，根据数据密度在三种容器间自动转换：

mermaid

flowchart TB
    subgraph Array["Array Container — 稀疏 (< 4096 个值)"]
        direction LR
        A1["[3, 42, 107, 722, 800, ...]"]
        A2["有序 short 数组<br/>二分查找 O(log N)<br/>内存: 2B × N"]
    end

    subgraph Bitmap["Bitmap Container — 密集 (≥ 4096 个值)"]
        direction LR
        B1["0b0010010...0100"]
        B2["固定 8KB bit 数组<br/>O(1) 直接位操作<br/>内存: 始终 8KB"]
    end

    subgraph Run["Run Container — 连续区间"]
        direction LR
        R1["[(100, 200), (500, 600)]"]
        R2["用 [start, length] 表示连续段<br/>极致压缩，维护成本高<br/>求交/并时可能退化回 Array/Bitmap"]
    end

    Array -->|"元素 ≥ 4096"| Bitmap
    Bitmap -->|"元素 < 4096"| Array
    Array -->|"连续区间多"| Run
    Run -->|"碎片化"| Array

// Roaring Bitmap 核心结构
type RoaringBitmap struct {
    highLowContainer map[uint16]container  // key=高16位, value=容器
}

type container interface {
    add(x uint16)
    contains(x uint16) bool
    cardinality() int
    and(other container) container
    or(other container) container
}

// Array Container
type arrayContainer struct {
    content []uint16  // 有序存储
}

func (a *arrayContainer) add(x uint16) {
    // 二分查找插入位置，保持有序
    idx := sort.Search(len(a.content), func(i int) bool {
        return a.content[i] >= x
    })
    if idx < len(a.content) && a.content[idx] == x {
        return // 已存在
    }
    a.content = append(a.content, 0)
    copy(a.content[idx+1:], a.content[idx:])
    a.content[idx] = x

    // 超过 4096 → 转为 Bitmap Container
    if len(a.content) >= 4096 {
        convertToBitmapContainer(a)
    }
}

// Bitmap Container（固定 8KB）
type bitmapContainer struct {
    bitmap [1024]uint64  // 1024 × 64 = 65536 bits = 覆盖所有低 16 位
}

func (b *bitmapContainer) cardinality() int {
    count := 0
    for _, word := range b.bitmap {
        count += bits.OnesCount64(word)  // POPCNT 指令
    }
    // 运行中如果 count < 4096 → 转回 Array Container
    return count
}

8.3 容器转换的数学边界

text

Array → Bitmap 触发点 = 4096 个元素:

  Array Container 内存: 4096 × 2B = 8192 B = 8 KB
  Bitmap Container 内存: 1024 × 8B = 8192 B = 8 KB
  → 恰好相等！所以 4096 是临界点。

大于 4096：Bitmap 更省空间
小于 4096：Array 更省空间

Bitmap → Array 触发点：当 cardinality < 4096 时转回

Run Container 触发条件：
  - 连续区间长度足够长，使得 [(start, len)] 比 Array/Bitmap 更省空间
  - 例如: [0, 1, 2, ..., 999] → Run[(0, 1000)] = 4B vs Array = 2000B

8.4 求交集（AND）的优化

Roaring Bitmap 的加速秘密：只在相同高 16 位桶之间做交集。

func (rb *RoaringBitmap) And(other *RoaringBitmap) *RoaringBitmap {
    result := New()

    // 只在两个 bitmap 都有数据的桶之间做交集
    for high, c1 := range rb.highLowContainer {
        if c2, ok := other.highLowContainer[high]; ok {
            // 同桶内：容器级别的 AND
            c := c1.and(c2)
            if c.cardinality() > 0 {
                result.highLowContainer[high] = c
            }
        }
    }
    return result
}

// 容器级 AND 优化：根据容器类型选最优算法
func (a *arrayContainer) and(b container) container {
    switch b := b.(type) {
    case *arrayContainer:
        // Array vs Array: 双指针归并 O(N+M)
        return arrayAndArray(a, b)
    case *bitmapContainer:
        // Array vs Bitmap: 遍历 Array，检查 Bitmap O(N)
        return arrayAndBitmap(a, b)
    }
    return nil
}

text

为什么快？

传统 Bitmap AND:    两个 1 亿位的 bitmap → 12.5MB × 2 → AND 操作需遍历 12.5MB
Roaring Bitmap AND:  只有少数几个桶有数据 → 只处理有数据的桶
                     → 1000 万用户画像，通常只有几十个桶需要 AND
                     → 操作量从 12.5MB 降到 KB 级别

8.5 性能对比

场景：1 亿用户，随机分布 1000 万个用户 ID（稀疏度 10%）

┌──────────────────┬───────────┬───────────┬─────────────┐
│ 方案              │ 内存       │ AND 耗时   │ 集合运算     │
├──────────────────┼───────────┼───────────┼─────────────┤
│ 原始 Bitmap       │ 12.5 MB   │ ~1 ms     │ 简单的位运算  │
│ Roaring Bitmap    │ ~1.2 MB   │ ~0.05 ms  │ 桶级优化     │
│ HashSet           │ 280 MB    │ N/A       │ 需遍历       │
└──────────────────┴───────────┴───────────┴─────────────┘

结论：Roaring Bitmap 在稀疏场景下内存节省 10 倍，计算快 20 倍。

8.6 工程应用

系统	用途	为什么用 Roaring
Elasticsearch	Posting List 压缩	文档 ID 稀疏但可排序
Apache Druid	倒排索引	时间序列分桶天然适合
Apache Kylin	Cube 计算	多维聚合的 Bitmap 加速
Spark	DataFrame 过滤	列式存储下的高效过滤
ClickHouse	位图聚合函数	groupBitmap() 内置
Redis (RedisBloom)	用户画像标签	超大规模标签交集

bash

# Redis RedisBloom Roaring Bitmap 示例
# 存储用户标签
RB.SETBIT user:male 1001 1     # 用户 1001 是男性
RB.SETBIT user:male 2048 1     # 用户 2048 是男性

RB.SETBIT user:vip 1001 1      # 用户 1001 是 VIP
RB.SETBIT user:vip 2048 1

# 交集：男性 AND VIP 用户
RB.AND result user:male user:vip
# → [1001, 2048]

# 并集：男性 OR VIP 用户
RB.OR result user:male user:vip

9. 嵌套集合模型与物化路径 — 无限层级树的 SQL 优化

用 parent_id 查树需要递归 SQL（MySQL 8.0 CTE）或循环查询。嵌套集合和物化路径用"一次查询"解决"所有祖先"或"所有子孙"的问题。

9.1 四种方案的直观对比

数据: 电子产品 → 手机 → iPhone → iPhone 15 Pro

方案1: 邻接表 (parent_id)
  ┌────┬──────────────┬───────────┐
  │ id │ name         │ parent_id │
  ├────┼──────────────┼───────────┤
  │  1 │ 电子产品      │ NULL      │
  │  2 │ 手机          │ 1         │
  │  3 │ iPhone       │ 2         │
  │  4 │ iPhone 15 Pro│ 3         │
  └────┴──────────────┴───────────┘

方案2: 嵌套集合 (Nested Set)
  ┌────┬──────────────┬─────┬─────┬──────┐
  │ id │ name         │ lft │ rgt │ depth│
  ├────┼──────────────┼─────┼─────┼──────┤
  │  1 │ 电子产品      │  1  │  8  │  0   │
  │  2 │ 手机          │  2  │  7  │  1   │
  │  3 │ iPhone       │  3  │  6  │  2   │
  │  4 │ iPhone 15 Pro│  4  │  5  │  3   │
  └────┴──────────────┴─────┴─────┴──────┘

方案3: 物化路径 (Materialized Path)
  ┌────┬──────────────┬──────────┐
  │ id │ name         │ path     │
  ├────┼──────────────┼──────────┤
  │  1 │ 电子产品      │ 1/       │
  │  2 │ 手机          │ 1/2/     │
  │  3 │ iPhone       │ 1/2/3/   │
  │  4 │ iPhone 15 Pro│ 1/2/3/4/ │
  └────┴──────────────┴──────────┘

方案4: 闭包表 (Closure Table)
  ┌──────────┬──────────┬──────┐
  │ ancestor │ descendant│ depth│
  ├──────────┼──────────┼──────┤
  │    1     │    1     │  0   │
  │    1     │    2     │  1   │
  │    1     │    3     │  2   │
  │    1     │    4     │  3   │
  │    2     │    2     │  0   │
  │    2     │    3     │  1   │
  │    2     │    4     │  2   │
  │    3     │    3     │  0   │
  │    3     │    4     │  1   │
  │    4     │    4     │  0   │
  └──────────┴──────────┴──────┘

9.2 嵌套集合（Nested Set）— O(1) 查子孙/祖先

sql

-- 查"手机"的所有子孙（含自己）
SELECT * FROM category
WHERE lft BETWEEN 2 AND 7  -- lft ≥ 2 AND lft ≤ 7
ORDER BY lft;
-- 结果: 手机、iPhone、iPhone 15 Pro

-- 查"iPhone 15 Pro"的所有祖先
SELECT * FROM category
WHERE lft <= 4 AND rgt >= 5
ORDER BY lft;
-- 结果: 电子产品、手机、iPhone、iPhone 15 Pro

-- 查"手机"的直接子节点（不含更深层）
SELECT child.* FROM category parent
JOIN category child
  ON child.lft BETWEEN parent.lft AND parent.rgt
  AND child.depth = parent.depth + 1
WHERE parent.id = 2;

mermaid

flowchart TB
    subgraph Tree["嵌套集合的树结构"]
        direction TB
        N1["[1] 电子产品<br/>lft=1, rgt=8, depth=0"]
        N2["[2] 手机<br/>lft=2, rgt=7, depth=1"]
        N3["[3] iPhone<br/>lft=3, rgt=6, depth=2"]
        N4["[4] iPhone 15 Pro<br/>lft=4, rgt=5, depth=3"]
    end

    N1 --> N2
    N2 --> N3
    N3 --> N4

    subgraph Intuition["直觉理解"]
        I1["lft: 进入节点的序号（先序遍历）"]
        I2["rgt: 离开节点的序号"]
        I3["所有子孙 = lft 在 (parent.lft, parent.rgt) 之间的节点"]
        I4["祖先 = lft < node.lft AND rgt > node.rgt"]
        I1 ~~~ I2 ~~~ I3 ~~~ I4
    end

新增节点的 lft/rgt 重排：

sql

-- 在"iPhone"下新增"iPhone 16"
-- 需要先"腾出空间"：把插入位置右侧所有节点的 lft 和 rgt 都 +2
UPDATE category SET lft = lft + 2 WHERE lft > 4;   -- 插入位置的右边界右侧
UPDATE category SET rgt = rgt + 2 WHERE rgt >= 4;  -- 插入位置的右边界及右侧

-- 然后插入新节点
INSERT INTO category (name, lft, rgt, depth)
VALUES ('iPhone 16', 5, 6, 3);

嵌套集合的代价：新增/删除节点需要更新大量行的 lft/rgt → O(N)。只适合读多写少的树（如组织架构、分类目录）。

9.3 物化路径（Materialized Path）

sql

-- 查"手机"的所有子孙
SELECT * FROM category
WHERE path LIKE '1/2/%';
-- 结果: iPhone, iPhone 15 Pro

-- 查"iPhone 15 Pro"的所有祖先
-- 方法: 拆分路径为 [1, 2, 3, 4]，然后 WHERE id IN (1,2,3,4)
SELECT * FROM category
WHERE id IN (1, 2, 3, 4)
ORDER BY LENGTH(path);

-- 查"手机"的直接子节点
SELECT * FROM category
WHERE path REGEXP '^1/2/[0-9]+/$';  -- path 匹配 "1/2/{id}/"

新增节点：只需拼接 parent.path + id + '/' → O(1)！

sql

-- 新增"iPhone 16"到"iPhone"下
INSERT INTO category (name, path)
SELECT 'iPhone 16', CONCAT(path, LAST_INSERT_ID(), '/')
FROM category WHERE id = 3;

9.4 闭包表（Closure Table）— 最灵活的方案

sql

-- 查"手机"的所有子孙
SELECT c.* FROM category c
JOIN closure_table ct ON c.id = ct.descendant
WHERE ct.ancestor = 2 AND ct.depth > 0;

-- 查"iPhone 15 Pro"的所有祖先
SELECT c.* FROM category c
JOIN closure_table ct ON c.id = ct.ancestor
WHERE ct.descendant = 4;

-- 查"电子产品"的直接子节点
SELECT c.* FROM category c
JOIN closure_table ct ON c.id = ct.descendant
WHERE ct.ancestor = 1 AND ct.depth = 1;

新增节点时维护闭包表：

sql

-- 在"iPhone"(id=3)下新增"iPhone 16"
INSERT INTO category (name) VALUES ('iPhone 16');
SET @new_id = LAST_INSERT_ID();

-- 插入闭包记录：所有祖先 → 新节点
INSERT INTO closure_table (ancestor, descendant, depth)
SELECT ancestor, @new_id, depth + 1
FROM closure_table
WHERE descendant = 3;

-- 加上自引用
INSERT INTO closure_table (ancestor, descendant, depth)
VALUES (@new_id, @new_id, 0);

9.5 方案对比

方案	查子孙	查祖先	新增/删除	移动节点	存储开销
parent_id	❌ 递归	❌ 递归	✅ O(1)	✅ O(1)	极小
嵌套集合	✅ O(log N)*	✅ O(log N)*	❌ O(N) 重排	❌ O(N) 重排	小(+2列)
物化路径	✅ LIKE	❌ 需拆分	✅ O(1)	❌ 需更新子树	小(+1列)
闭包表	✅ O(N)	✅ O(N)	✅ O(M)	✅ O(M+N)	大(O(N²))

* 配合索引后

9.6 生产环境推荐

大多数场景 → 邻接表 (parent_id) + MySQL 8.0 CTE
  优点：简单，移动节点 O(1)
  查询: WITH RECURSIVE tree AS (
          SELECT * FROM category WHERE id = 2
          UNION ALL
          SELECT c.* FROM category c
          JOIN tree t ON c.parent_id = t.id
        ) SELECT * FROM tree;

读多写少的树 → 嵌套集合
  如：组织架构、地区分类、商品类目

频繁增删但很少移动 → 物化路径
  如：评论回复、文件目录

需要快速查询任意祖先/子孙 → 闭包表
  如：权限系统（查询用户对某部门下所有子部门的权限）

混合方案 → parent_id + 物化路径
  通过触发器或应用层同步维护 path 列，兼顾写性能和读性能

特殊数据结构：Trie、Bitmap、Bloom Filter ​

1. Trie（前缀树 / 字典树） ​

1.1 结构 ​

1.2 基本实现 ​

1.3 空间优化：压缩 Trie（Radix Tree / Patricia Trie） ​

1.4 各系统中的应用 ​

1.5 搜索提示（Autocomplete）实现 ​

2. Bitmap（位图） ​

2.1 原理 ​

2.2 基本操作 ​

2.3 应用 ​

2.4 Redis Bitmap ​

3. Bloom Filter（布隆过滤器） ​

3.1 原理 ​

3.2 假阳性率计算 ​

3.3 实现 ​

3.4 变体 ​

3.5 应用 ​

3.6 Redis Bloom Filter 示例 ​

4. 三者对比 ​

选择决策 ​

5. Cuckoo Filter — 支持删除的 Bloom Filter ​

原理：双哈希 + 布谷鸟驱逐 ​

6. Count-Min Sketch — 频率估计 ​

6.1 与 HyperLogLog 协同使用 ​

6.2 HyperLogLog 数学原理 ​

伯努利试验与低位连续零 ​

从 LogLog 到 HyperLogLog ​

完整算法流程 ​

精度与内存权衡 ​

为什么不能精确计数？ ​

Redis HyperLogLog 的使用 ​

7. Radix Tree (Patricia Trie) — 压缩前缀树 ​

8. Roaring Bitmap — 高效压缩位图 ​

8.1 核心设计：高低 16 位拆分 ​

8.2 三种自适应容器 ​

8.3 容器转换的数学边界 ​

8.4 求交集（AND）的优化 ​

8.5 性能对比 ​

8.6 工程应用 ​

9. 嵌套集合模型与物化路径 — 无限层级树的 SQL 优化 ​

9.1 四种方案的直观对比 ​

9.2 嵌套集合（Nested Set）— O(1) 查子孙/祖先 ​

9.3 物化路径（Materialized Path） ​

9.4 闭包表（Closure Table）— 最灵活的方案 ​

9.5 方案对比 ​

9.6 生产环境推荐 ​

💬 文章评论

特殊数据结构：Trie、Bitmap、Bloom Filter

1. Trie（前缀树 / 字典树）

1.1 结构

1.2 基本实现

1.3 空间优化：压缩 Trie（Radix Tree / Patricia Trie）

1.4 各系统中的应用

1.5 搜索提示（Autocomplete）实现

2. Bitmap（位图）

2.1 原理

2.2 基本操作

2.3 应用

2.4 Redis Bitmap

3. Bloom Filter（布隆过滤器）

3.1 原理

3.2 假阳性率计算

3.3 实现

3.4 变体

3.5 应用

3.6 Redis Bloom Filter 示例

4. 三者对比

选择决策

5. Cuckoo Filter — 支持删除的 Bloom Filter

原理：双哈希 + 布谷鸟驱逐

6. Count-Min Sketch — 频率估计

6.1 与 HyperLogLog 协同使用

6.2 HyperLogLog 数学原理

伯努利试验与低位连续零

从 LogLog 到 HyperLogLog

完整算法流程

精度与内存权衡

为什么不能精确计数？

Redis HyperLogLog 的使用

7. Radix Tree (Patricia Trie) — 压缩前缀树

8. Roaring Bitmap — 高效压缩位图

8.1 核心设计：高低 16 位拆分

8.2 三种自适应容器

8.3 容器转换的数学边界

8.4 求交集（AND）的优化

8.5 性能对比

8.6 工程应用

9. 嵌套集合模型与物化路径 — 无限层级树的 SQL 优化

9.1 四种方案的直观对比

9.2 嵌套集合（Nested Set）— O(1) 查子孙/祖先

9.3 物化路径（Materialized Path）

9.4 闭包表（Closure Table）— 最灵活的方案

9.5 方案对比

9.6 生产环境推荐