03 · 工程视角的数据结构
“为什么 MySQL 用 B+Tree 而不用红黑树？答案不在算法书里，在硬件手册里。“
开场：一个”错”的选择
老陈：红黑树查找是 O(log n)，B+Tree 也是 O(log n)。MySQL 的索引用 B+Tree。为什么不用红黑树？
小林：……B+Tree 的树更矮？
老陈：为什么更矮？
小林：因为……每个节点能存更多 key？
老陈：为什么每个节点能存更多 key 就能更高效？ 假设 n = 100 万。
红黑树：二叉，树高 log₂(10⁶) ≈ 20 B+Tree：假设每个节点 1000 个 key，树高 log₁₀₀₀(10⁶) = 2
小林：所以 B+Tree 只要 2 次磁盘 IO，红黑树要 20 次？
老陈：对，但你的数字不对。 关键问题：B+Tree 的一个节点多大？
小林：……不知道。
老陈：16KB，跟 InnoDB 的页大小一样。 这是巧合吗？
小林：……不是。
老陈：当然不是。B+Tree 的节点大小被刻意设计成”一个磁盘页”，因为磁盘的最小 IO 单位是页。 你读 1 字节和读 16KB，代价一样。
现在算：
int64主键 8 字节 + 指针 6 字节 = 14 字节。16KB / 14 ≈ 1170 个 key/节点。树高 3 的 B+Tree：1170³ ≈ 16 亿条记录。
也就是说：16 亿条数据的表，最多 3 次磁盘 IO 就能查到。 红黑树需要 30 次。
小林：所以选择数据结构的依据不是”渐进复杂度”，而是”IO 次数”？
老陈：对。而且更进一步——数据结构是为存储层次设计的。 这一节我们就讲这个。
存储层次与数据结构
| 存储层次 | 访问延迟 | 适配的数据结构 | 关键设计 |
|---|---|---|---|
| CPU 缓存 | ~1-15 ns | 数组、紧凑结构 | 缓存行对齐、顺序访问 |
| 内存 | ~80 ns | 哈希表、跳表、红黑树 | 减少指针跳转 |
| SSD | ~100 μs | B+Tree、LSM-Tree | 节点 = 页大小，减少随机 IO |
| 机械硬盘 | ~10 ms | LSM-Tree | 把随机写变顺序写 |
| 网络/分布式 | ~1-100 ms | 一致性哈希、Raft 日志 | 减少网络往返 |
核心原则：每一层的设计，都要最小化对下一层的访问次数。
例子：
L1 缓存 miss 一次 = 15ns，从内存取一个缓存行（64B）
→ 数据结构应该让连续访问的数据在同一缓存行
磁盘 IO 一次 = 10ms，读一个页（4KB/16KB）
→ 数据结构应该让一次 IO 带回尽可能多的有用数据
数据结构 1：B+Tree
为什么是 B+Tree 而不是 B-Tree
| B-Tree | B+Tree | |
|---|---|---|
| 数据存储 | 所有节点都存数据 | 只有叶子节点存数据 |
| 叶子节点 | 不相连 | 用链表相连 ★ |
| 内部节点 | 存 key + 数据 | 只存 key + 指针 |
| 单节点 key 数 | 少（因为要存数据） | 多（只存 key） |
| 范围查询 | 要中序遍历整棵树 | 叶子链表顺序扫描 ★ |
B+Tree 的两个决定性优势：
① 内部节点只存 key → 单节点能存更多 key → 树更矮
节点 16KB:
B-Tree: key(8B) + data(1KB) = 1032B → 16 个 key/节点
B+Tree: key(8B) + ptr(6B) = 14B → 1170 个 key/节点 ★ 73 倍！
树高 3:
B-Tree: 16³ = 4096 条记录
B+Tree: 1170³ = 16 亿条记录 ★ 差 39 万倍
② 叶子节点用链表相连 → 范围查询极快
SELECT * FROM users WHERE id BETWEEN 100 AND 200;- B-Tree：中序遍历，可能在树里上下跳很多次，每次都可能是新的磁盘 IO
- B+Tree：找到 id=100 的叶子，然后顺着链表扫 100 个，几乎都是顺序 IO
老陈：这个”叶子链表”的设计，是 B+Tree 成为数据库索引标准的核心原因。
数据库 80% 的查询是范围查询（
BETWEEN、>、<、ORDER BY、GROUP BY），而不是点查询。B+Tree 就是为范围查询优化的。
Go 实现 B+Tree
package main
import (
"fmt"
"sort"
)
const (
// 节点的阶（最大子节点数）
// 真实数据库里这个值由页大小决定，可能几百上千
// 这里用小值方便演示和测试
MaxKeys = 4 // 每个节点最多 4 个 key（即最多 5 个子节点）
MinKeys = 2 // 非根节点最少 2 个 key
)
type BPlusTree struct {
root *Node
height int
size int
}
type Node struct {
// 是否是叶子节点
isLeaf bool
// key 列表（有序）
keys []int
// 叶子节点：values[i] 对应 keys[i]
values []any
// 内部节点：children[i] 指向第 i 个子节点
// children 长度 = len(keys) + 1
children []*Node
// 叶子节点的链表指针（范围查询用）★
next *Node
parent *Node
}
func NewBPlusTree() *BPlusTree {
return &BPlusTree{
root: &Node{isLeaf: true},
height: 1,
}
}
// ============ 查找 ============
func (t *BPlusTree) Get(key int) (any, bool) {
leaf := t.findLeaf(key)
// 在叶子里二分查找
i := sort.SearchInts(leaf.keys, key)
if i < len(leaf.keys) && leaf.keys[i] == key {
return leaf.values[i], true
}
return nil, false
}
func (t *BPlusTree) findLeaf(key int) *Node {
node := t.root
for !node.isLeaf {
// 找到第一个 > key 的位置，往左走
i := sort.SearchInts(node.keys, key)
if i < len(node.keys) && node.keys[i] == key {
i++ // B+Tree 的查找总是走到叶子
}
node = node.children[i]
}
return node
}
// ============ 范围查询 ★ B+Tree 的核心优势 ============
func (t *BPlusTree) Range(start, end int) [][2]any {
var result [][2]any
// 1. 找到起始叶子
node := t.findLeaf(start)
// 2. 顺着叶子链表扫描
for node != nil {
for i, k := range node.keys {
if k > end {
return result
}
if k >= start {
result = append(result, [2]any{k, node.values[i]})
}
}
node = node.next // ★ 关键：顺着链表走，不需要回到根节点
}
return result
}
// ============ 插入 ============
func (t *BPlusTree) Put(key int, value any) {
leaf := t.findLeaf(key)
// 找到插入位置
pos := sort.SearchInts(leaf.keys, key)
if pos < len(leaf.keys) && leaf.keys[pos] == key {
// key 已存在，更新
leaf.values[pos] = value
return
}
// 插入
leaf.keys = append(leaf.keys, 0)
copy(leaf.keys[pos+1:], leaf.keys[pos:])
leaf.keys[pos] = key
leaf.values = append(leaf.values, nil)
copy(leaf.values[pos+1:], leaf.values[pos:])
leaf.values[pos] = value
t.size++
// 节点满了，需要分裂
if len(leaf.keys) > MaxKeys {
t.splitLeaf(leaf)
}
}
func (t *BPlusTree) splitLeaf(leaf *Node) {
mid := len(leaf.keys) / 2
// 创建新叶子
newLeaf := &Node{
isLeaf: true,
keys: append([]int{}, leaf.keys[mid:]...),
values: append([]any{}, leaf.values[mid:]...),
parent: leaf.parent,
}
// ★ 维护叶子链表
newLeaf.next = leaf.next
leaf.next = newLeaf
// 分裂后，右半部分的第一个 key 要提升到父节点
promotedKey := newLeaf.keys[0]
// 截断原叶子
leaf.keys = leaf.keys[:mid]
leaf.values = leaf.values[:mid]
// 插入到父节点
if leaf.parent == nil {
// 根节点分裂，树长高
t.root = &Node{
isLeaf: false,
keys: []int{promotedKey},
children: []*Node{leaf, newLeaf},
}
leaf.parent = t.root
newLeaf.parent = t.root
t.height++
return
}
// 在父节点插入 promotedKey 和 newLeaf
t.insertIntoParent(leaf.parent, promotedKey, newLeaf)
}
func (t *BPlusTree) insertIntoParent(parent *Node, key int, child *Node) {
pos := sort.SearchInts(parent.keys, key)
parent.keys = append(parent.keys, 0)
copy(parent.keys[pos+1:], parent.keys[pos:])
parent.keys[pos] = key
parent.children = append(parent.children, nil)
copy(parent.children[pos+2:], parent.children[pos+1:])
parent.children[pos+1] = child
child.parent = parent
// 父节点也满了，继续分裂
if len(parent.keys) > MaxKeys {
t.splitInternal(parent)
}
}
func (t *BPlusTree) splitInternal(node *Node) {
mid := len(node.keys) / 2
// ★ 注意：内部节点分裂时，中间的 key 要提升到父节点，
// 而不是留在右半部分（因为内部节点的 key 是"分隔符"）
promotedKey := node.keys[mid]
newNode := &Node{
isLeaf: false,
keys: append([]int{}, node.keys[mid+1:]...),
children: append([]*Node{}, node.children[mid+1:]...),
parent: node.parent,
}
// 更新子节点的 parent 指针
for _, c := range newNode.children {
c.parent = newNode
}
node.keys = node.keys[:mid]
node.children = node.children[:mid+1]
if node.parent == nil {
t.root = &Node{
isLeaf: false,
keys: []int{promotedKey},
children: []*Node{node, newNode},
}
node.parent = t.root
newNode.parent = t.root
t.height++
return
}
t.insertIntoParent(node.parent, promotedKey, newNode)
}
// ============ 打印（调试用）============
func (t *BPlusTree) Print() {
fmt.Printf("B+Tree (height=%d, size=%d)\n", t.height, t.size)
t.printNode(t.root, 0)
}
func (t *BPlusTree) printNode(n *Node, depth int) {
indent := ""
for i := 0; i < depth; i++ {
indent += " "
}
if n.isLeaf {
fmt.Printf("%sLeaf: %v\n", indent, n.keys)
} else {
fmt.Printf("%sInternal: %v\n", indent, n.keys)
for _, c := range n.children {
t.printNode(c, depth+1)
}
}
}
// 验证叶子链表
func (t *BPlusTree) VerifyLeafChain() (int, bool) {
// 走到最左叶子
n := t.root
for !n.isLeaf {
n = n.children[0]
}
count := 0
prev := -1
for n != nil {
for _, k := range n.keys {
if k <= prev {
return count, false // 不是严格递增
}
prev = k
count++
}
n = n.next
}
return count, count == t.size
}
func demoBPlusTree() {
t := NewBPlusTree()
// 插入 1~20
for i := 1; i <= 20; i++ {
t.Put(i, fmt.Sprintf("value-%d", i))
}
t.Print()
// 点查询
if v, ok := t.Get(7); ok {
fmt.Printf("\nGet(7) = %v\n", v)
}
// 范围查询 ★
fmt.Printf("\nRange(5, 12):\n")
for _, kv := range t.Range(5, 12) {
fmt.Printf(" %v: %v\n", kv[0], kv[1])
}
// 验证叶子链表
count, valid := t.VerifyLeafChain()
fmt.Printf("\n叶子链表: %d 个 key, 有序且完整 = %v\n", count, valid)
}运行输出（节选）：
B+Tree (height=3, size=20)
Internal: [7 13]
Internal: [3 5]
Leaf: [1 2]
Leaf: [3 4]
Leaf: [5 6]
Internal: [9 11]
Leaf: [7 8]
Leaf: [9 10]
Leaf: [11 12]
Internal: [17 19]
Leaf: [13 14 15 16]
Leaf: [17 18]
Leaf: [19 20]
Get(7) = value-7
Range(5, 12):
5: value-5
6: value-6
7: value-7
...
12: value-12
叶子链表: 20 个 key, 有序且完整 = true
B+Tree 的并发控制：B-link Tree
真实数据库要解决并发读写。朴素的方案是给整棵树加锁——这会让 B+Tree 完全串行化。
解决方案：B-link Tree（B+Tree 的并发版本）
核心技巧 1：每个节点加一个 "high key"（该节点子树的最大 key）
核心技巧 2：每个节点加一个 "right link"（指向右兄弟）
查找时：
· 从根往下走，只锁当前节点（latch coupling）
· 如果发现目标 key > 当前节点的 high key
→ 说明节点已经被并发分裂了，顺着 right link 往右走
· 释放父节点的锁，再锁子节点
★ 关键：永远不需要同时锁住多个节点（除了"锁住子节点后才释放父节点"这短暂的一瞬）
老陈：这个技巧叫 “latch crabbing”（锁蟹行）——像螃蟹横着走一样，抓住下一个才放开上一个。
它的精妙之处：即使发生了并发分裂，查找也不会出错。 因为分裂是”向右”的，而 right link 让你总能找到正确的节点。
这是一个”用额外指针换并发度”的设计。 跟我们前面看到的”用空间换时间”是同一类交易。
数据结构 2：跳表（Skip List）
为什么 Redis 用跳表
Redis 的有序集合（ZSet）用跳表。为什么不用 B+Tree 或红黑树？
| 跳表 | 红黑树 | B+Tree | |
|---|---|---|---|
| 实现复杂度 | ⭐⭐ 简单 | ⭐⭐⭐⭐ 复杂 | ⭐⭐⭐⭐⭐ 最复杂 |
| 范围查询 | ⭐⭐⭐⭐⭐ 天然有序 | ⭐⭐⭐ 中序遍历 | ⭐⭐⭐⭐⭐ 叶子链表 |
| 插入删除 | ⭐⭐⭐⭐ 只需改局部指针 | ⭐⭐ 要旋转+重新平衡 | ⭐⭐⭐ 可能分裂合并 |
| 并发友好 | ⭐⭐⭐⭐ 局部修改 | ⭐ 旋转影响大 | ⭐⭐ |
| 内存局部性 | ⭐⭐ 指针跳转 | ⭐⭐ 指针跳转 | ⭐⭐⭐⭐⭐ 节点大，连续 |
| 磁盘友好 | ❌ 不适合 | ❌ 不适合 | ⭐⭐⭐⭐⭐ |
Redis 选跳表的理由：
- 内存数据库，不需要磁盘友好 → B+Tree 的最大优势用不上
- 实现简单，bug 少 → Redis 是单人维护起步的项目，代码简洁是核心价值
- 范围查询高效 → ZSet 的核心操作是
ZRANGE - 插入删除只需局部修改 → 不需要像红黑树那样重新平衡
跳表的原理
核心思想：用概率平衡代替严格平衡。
第 3 层: 1 ────────────────► 9 （2 个节点）
│
第 2 层: 1 ───────► 5 ─────► 9 ──────► 13 （4 个节点）
│ │ │ │
第 1 层: 1 ─► 3 ─► 5 ─► 7 ─► 9 ─► 11 ─► 13 （7 个节点）
│ │ │ │ │ │ │ │
第 0 层: 1 ► 3 ► 5 ► 7 ► 9 ► 11 ► 13 （全部节点，有序链表）
- 第 0 层：所有节点，是一个有序链表
- 第 i 层：第 i-1 层的”抽样”，每个节点以概率 p（通常 1/2 或 1/4）出现在上一层
查找：从第 3 层开始，能往右走就往右，不能就下降一层。
查找 7:
第 3 层: 1 → 9 > 7，不能走，下降
第 2 层: 1 → 5 < 7，走到 5；5 → 9 > 7，下降
第 1 层: 5 → 7，找到！
★ 只比较了 3 次
Go 实现
package main
import (
"fmt"
"math/rand"
"time"
)
const (
MaxLevel = 32
Probability = 0.25 // Redis 用 0.25（每次晋升概率 1/4）
)
type SkipListNode struct {
key float64
value any
forward []*SkipListNode // forward[i] 是第 i 层的下一个节点
backward *SkipListNode // 反向指针（用于 ZREVRANGE）
}
type SkipList struct {
header *SkipListNode
tail *SkipListNode
level int // 当前最大层数
length int
}
func NewSkipList() *SkipList {
header := &SkipListNode{
forward: make([]*SkipListNode, MaxLevel),
}
return &SkipList{
header: header,
level: 1,
}
}
// 随机生成层数
// ★ 这是跳表"概率平衡"的核心
func randomLevel() int {
level := 1
for rand.Float64() < Probability && level < MaxLevel {
level++
}
return level
}
func (sl *SkipList) Insert(key float64, value any) {
// update[i] 记录在第 i 层，新节点的前驱
update := make([]*SkipListNode, MaxLevel)
cur := sl.header
// 从最高层往下找
for i := sl.level - 1; i >= 0; i-- {
for cur.forward[i] != nil && cur.forward[i].key < key {
cur = cur.forward[i]
}
update[i] = cur
}
// 如果 key 已存在，更新
cur = cur.forward[0]
if cur != nil && cur.key == key {
cur.value = value
return
}
// 随机层数
newLevel := randomLevel()
if newLevel > sl.level {
// 新层的前驱是 header
for i := sl.level; i < newLevel; i++ {
update[i] = sl.header
}
sl.level = newLevel
}
// 创建新节点
newNode := &SkipListNode{
key: key,
value: value,
forward: make([]*SkipListNode, newLevel),
}
// 插入每一层
for i := 0; i < newLevel; i++ {
newNode.forward[i] = update[i].forward[i]
update[i].forward[i] = newNode
}
// 维护 backward 指针
if update[0] == sl.header {
newNode.backward = nil
} else {
newNode.backward = update[0]
}
if newNode.forward[0] != nil {
newNode.forward[0].backward = newNode
} else {
sl.tail = newNode
}
sl.length++
}
func (sl *SkipList) Search(key float64) (any, bool) {
cur := sl.header
for i := sl.level - 1; i >= 0; i-- {
for cur.forward[i] != nil && cur.forward[i].key < key {
cur = cur.forward[i]
}
}
cur = cur.forward[0]
if cur != nil && cur.key == key {
return cur.value, true
}
return nil, false
}
// 范围查询 ★ 跳表的优势
func (sl *SkipList) Range(min, max float64) []any {
var result []any
// 找到起始位置
cur := sl.header
for i := sl.level - 1; i >= 0; i-- {
for cur.forward[i] != nil && cur.forward[i].key < min {
cur = cur.forward[i]
}
}
cur = cur.forward[0]
// 顺着第 0 层扫描
for cur != nil && cur.key <= max {
result = append(result, cur.value)
cur = cur.forward[0]
}
return result
}
// 删除
func (sl *SkipList) Delete(key float64) bool {
update := make([]*SkipListNode, MaxLevel)
cur := sl.header
for i := sl.level - 1; i >= 0; i-- {
for cur.forward[i] != nil && cur.forward[i].key < key {
cur = cur.forward[i]
}
update[i] = cur
}
cur = cur.forward[0]
if cur == nil || cur.key != key {
return false
}
for i := 0; i < sl.level; i++ {
if update[i].forward[i] == cur {
update[i].forward[i] = cur.forward[i]
}
}
// 更新 backward
if cur.forward[0] != nil {
cur.forward[0].backward = cur.backward
} else {
sl.tail = cur.backward
}
// 降低层数（如果最高层空了）
for sl.level > 1 && sl.header.forward[sl.level-1] == nil {
sl.level--
}
sl.length--
return true
}
// 演示
func demoSkipList() {
rand.Seed(time.Now().UnixNano())
sl := NewSkipList()
// 插入 100 万个元素，统计层数分布
levelDist := make(map[int]int)
for i := 0; i < 1_000_000; i++ {
l := randomLevel()
levelDist[l]++
}
fmt.Println("层数分布（p=0.25, n=100万）:")
for i := 1; i <= 8; i++ {
count := levelDist[i]
pct := float64(count) / 10000
fmt.Printf(" 第 %d 层: %8d 个 (%.3f%%)\n", i, count, pct)
}
total := 0
for _, c := range levelDist {
total += c
}
// 期望层数 = 1/(1-p) = 1.33
fmt.Printf(" 平均层数: %.2f (理论值 %.2f)\n",
float64(total)/1000000, 1/(1-Probability))
// 性能测试
for i := 0; i < 1_000_000; i++ {
sl.Insert(float64(i), i)
}
start := time.Now()
for i := 0; i < 100000; i++ {
sl.Search(float64(i))
}
searchTime := time.Since(start)
fmt.Printf("\n10 万次查找: %v (平均 %.0f ns/op)\n",
searchTime, float64(searchTime.Nanoseconds())/100000)
// 范围查询
start = time.Now()
r := sl.Range(1000, 2000)
rangeTime := time.Since(start)
fmt.Printf("范围查询 [1000,2000]: %v, 返回 %d 个\n", rangeTime, len(r))
}关键参数：为什么 p = 0.25？
p = 0.5: 平均层数 2，每层节点数减半，查找平均比较 2×log₂(n) 次
p = 0.25: 平均层数 1.33，查找平均比较 1.33×log₄(n) 次
★ p 越小，越省内存，但查找越慢
★ p = 0.25 是"内存"和"速度"的平衡点
Redis 的注释里明确写了这个权衡：
“The probability of a node having level i is 1/4^i… This gives a good tradeoff between memory usage and search speed.”
数据结构 3：LSM-Tree
为什么 LevelDB/RocksDB 用 LSM-Tree
核心洞察：机械硬盘的顺序写比随机写快 100 倍。
机械硬盘：
随机写: 寻道 10ms + 旋转延迟 5ms + 传输 = 约 10ms/次
顺序写: 一次寻道后连续写 = 约 0.1ms/KB
★ 差 100 倍
SSD（虽然没有寻道，但有写放大）：
随机写会触发"读-改-写"整个擦除块（通常 256KB）
顺序写可以合并，减少写放大
★ 差 10 倍
B+Tree 的问题：更新一个叶子节点，可能要读-改-写一个完整的页（16KB），即使只改了 8 字节。这是随机写。
LSM-Tree 的解法：所有写都是”追加”，把随机写变成顺序写。
LSM-Tree 的结构
写入
│
▼
┌──────────────┐
│ MemTable │ ← 内存中的有序结构（跳表/红黑树）
│ (可写) │ 写入 O(log n)，无磁盘 IO
└──────┬───────┘
│ 满了（通常 64MB）
▼
┌──────────────┐
│ Immutable │ ← 只读，准备落盘
│ MemTable │
└──────┬───────┘
│ flush（顺序写！）★
▼
┌─────────────────────────────────────┐
│ 磁盘上的 SSTable 分层 │
│ │
│ L0: [SST] [SST] [SST] ← 直接从 │
│ (key 范围可能重叠) MemTable 刷下│
│ │
│ L1: [SST][SST][SST][SST] ← key 范围 │
│ (每个 SST 内有序， 互不重叠) │
│ │
│ L2: [SST]×10 ← 大小是 L1 的 10 倍 │
│ │
│ L3: [SST]×100 │
└─────────────────────────────────────┘
│
│ 后台 Compaction（合并）
▼
减少文件数，删除过期版本
三个关键操作：
① 写入（Write）
1. 写 WAL（顺序写，用于崩溃恢复）
2. 写 MemTable（内存，跳过表）
3. 返回成功
★ 完全没有随机磁盘 IO！这是 LSM 写快的原因
② 读取（Read）
1. 查 MemTable
2. 查 Immutable MemTable
3. 查 L0 的所有 SSTable（因为 L0 的 key 范围可能重叠）
4. 查 L1, L2, ...（每层最多查一个 SSTable，因为范围内不重叠）
★ 可能需要查多个文件 → 读放大
③ 合并（Compaction）
后台把 Li 层的某个 SSTable 和 Li+1 层重叠的 SSTable 合并
· 删除被覆盖的旧版本
· 删除已标记删除的 key
· 生成新的、更大的 SSTable
★ 这是 LSM-Tree 复杂度的来源
三个”放大”
这是 LSM-Tree 的核心权衡：
| 放大类型 | 含义 | 原因 | 缓解 |
|---|---|---|---|
| 写放大 | 实际写入磁盘量 / 用户写入量 | Compaction 反复重写数据 | 增大 MemTable、调整层间比例 |
| 读放大 | 实际读取次数 / 需要读的次数 | 要查多层、多个文件 | 布隆过滤器、Block Cache |
| 空间放大 | 实际占用空间 / 有效数据量 | 旧版本未清理 | 更激进的 Compaction |
典型数值（RocksDB 默认配置）：
- 写放大：10-30 倍
- 读放大：1-10 次 IO（有布隆过滤器时）
- 空间放大：1.1-2 倍
老陈：这三个放大之间存在着不可能三角。
- 想减少写放大 → 少做 Compaction → 读放大和空间放大变大
- 想减少读放大 → 多做 Compaction（让层数少）→ 写放大变大
- 想减少空间放大 → 激进 Compaction → 写放大变大
这就是”没有最优，只有权衡”的又一个例子。 RocksDB 提供了多种 Compaction 策略（Leveled、Universal、FIFO），就是让使用者根据业务特点选择：
- Leveled：默认，读放大最小，写放大最大 → 读多写少
- Universal：写放大最小，读放大和空间放大最大 → 写多读少
- FIFO：不做合并，直接淘汰老文件 → 时序数据（只查最近的）
什么时候用 B+Tree，什么时候用 LSM？
| 场景 | 选择 | 理由 |
|---|---|---|
| 读多写少 | B+Tree | 读只要 3-4 次 IO，无读放大 |
| 写多读少 | LSM-Tree | 写是纯顺序，无随机 IO |
| 需要事务 | B+Tree | LSM 的事务实现复杂得多 |
| 范围查询多 | B+Tree | LSM 的范围查询要合并多层 |
| 数据量大（>1TB） | LSM-Tree | 压缩率高（SSTable 可压缩），空间放大可控 |
| 需要稳定的延迟 | B+Tree | LSM 的 Compaction 会造成延迟尖刺 |
这也是为什么：
- MySQL/PostgreSQL（OLTP，读写混合，需要事务）→ B+Tree
- RocksDB/LevelDB/Cassandra/HBase（写密集，大数据量）→ LSM-Tree
- TiDB（NewSQL，既要事务又要扩展）→ RocksDB（LSM）+ 分布式事务层
数据结构 4：布隆过滤器
原理
用极小的空间，快速判断”一个元素是否可能存在于集合中”。
特性：
· 如果返回"不存在" → 一定不存在（100% 准确）★
· 如果返回"存在" → 可能存在（有误判率）
★ 这是"假阳性"（false positive），没有"假阴性"（false negative）
结构：
- 一个 m 位的位数组
- k 个哈希函数
插入 "apple":
h1("apple") % m = 2 → 设置 bit[2] = 1
h2("apple") % m = 7 → 设置 bit[7] = 1
h3("apple") % m = 11 → 设置 bit[11] = 1
查询 "apple":
检查 bit[2], bit[7], bit[11] 是否都为 1
全是 1 → 可能存在
有 0 → 一定不存在 ★
误判率计算
误判率 P ≈ (1 - e^(-k·n/m))^k
其中：
m = 位数
n = 已插入元素数
k = 哈希函数个数
最优 k = (m/n) · ln(2) ≈ 0.7 · (m/n)
此时 P ≈ (0.6185)^(m/n)
实用数字：
| 每个元素占的位数 (m/n) | 误判率 | 最优 k |
|---|---|---|
| 8 | 2.16% | 6 |
| 10 | 1.18% | 7 |
| 16 | 0.046% | 11 |
| 32 | 0.00021% | 22 |
对比：
1 亿个元素：
哈希表: 1 亿 × (key 大小 + 指针) ≈ 3-8 GB
布隆过滤器 (m/n=16): 1 亿 × 16 bit = 200 MB ★ 15-40 倍节省
误判率 0.046%
Go 实现
package main
import (
"fmt"
"hash/fnv"
"math"
)
type BloomFilter struct {
bits []uint64 // 用 uint64 数组存位
numBits uint32
numHash uint32
count uint32
}
func NewBloomFilter(expectedItems uint32, falsePositiveRate float64) *BloomFilter {
// m = -n·ln(p) / (ln2)^2
m := -float64(expectedItems) * math.Log(falsePositiveRate) / (math.Ln2 * math.Ln2)
numBits := uint32(math.Ceil(m))
// k = (m/n)·ln2
k := float64(numBits) / float64(expectedItems) * math.Ln2
numHash := uint32(math.Ceil(k))
if numHash < 1 {
numHash = 1
}
// 对齐到 64 的倍数，方便用 uint64 数组
numBits = ((numBits + 63) / 64) * 64
return &BloomFilter{
bits: make([]uint64, numBits/64),
numBits: numBits,
numHash: numHash,
}
}
// 双哈希：用两个哈希函数模拟 k 个
// ★ 这是标准做法（Kirsch-Mitzenmacher 优化）
// h_i(x) = h1(x) + i·h2(x)
func (bf *BloomFilter) hash(data []byte) (uint32, uint32) {
h1 := fnv.New64()
h1.Write(data)
v1 := h1.Sum64()
h2 := fnv.New64a() // 用 FNV-1a 作为第二个（不同的变体）
h2.Write(data)
v2 := h2.Sum64()
return uint32(v1), uint32(v2>>32)
}
func (bf *BloomFilter) Add(data []byte) {
h1, h2 := bf.hash(data)
for i := uint32(0); i < bf.numHash; i++ {
pos := (h1 + i*h2) % bf.numBits
bf.bits[pos/64] |= (1 << (pos % 64))
}
bf.count++
}
func (bf *BloomFilter) MayContain(data []byte) bool {
h1, h2 := bf.hash(data)
for i := uint32(0); i < bf.numHash; i++ {
pos := (h1 + i*h2) % bf.numBits
if bf.bits[pos/64]&(1<<(pos%64)) == 0 {
return false // ★ 一定不存在
}
}
return true // 可能存在
}
// 估算当前误判率
func (bf *BloomFilter) EstimateFalsePositiveRate() float64 {
// 统计被设置的位数
setBits := 0
for _, w := range bf.bits {
setBits += popcount(w)
}
// P ≈ (setBits / numBits)^k
ratio := float64(setBits) / float64(bf.numBits)
return math.Pow(ratio, float64(bf.numHash))
}
func popcount(x uint64) int {
count := 0
for x != 0 {
count++
x &= x - 1
}
return count
}
func demoBloomFilter() {
// 目标：100 万元素，1% 误判率
bf := NewBloomFilter(1_000_000, 0.01)
fmt.Printf("布隆过滤器配置:\n")
fmt.Printf(" 位数: %d (%.2f MB)\n",
bf.numBits, float64(bf.numBits)/8/1024/1024)
fmt.Printf(" 哈希函数数: %d\n", bf.numHash)
fmt.Printf(" 每个元素占: %.1f bits\n",
float64(bf.numBits)/1000000)
// 插入
for i := 0; i < 1_000_000; i++ {
bf.Add([]byte(fmt.Sprintf("key-%d", i)))
}
fmt.Printf("\n插入 100 万后，实际误判率: %.3f%%\n",
bf.EstimateFalsePositiveRate()*100)
// 测试：查询存在的
existCount := 0
for i := 0; i < 1000; i++ {
if bf.MayContain([]byte(fmt.Sprintf("key-%d", i))) {
existCount++
}
}
fmt.Printf("查询 1000 个已插入的 key: 命中 %d 个 (应为 1000)\n", existCount)
// 测试：查询不存在的（统计误判）
falsePositive := 0
for i := 0; i < 10000; i++ {
key := fmt.Sprintf("nonexist-%d", i)
if bf.MayContain([]byte(key)) {
falsePositive++
}
}
fmt.Printf("查询 10000 个不存在的 key: 误判 %d 个 (%.2f%%)\n",
falsePositive, float64(falsePositive)/100)
}布隆过滤器在真实系统中的应用
| 系统 | 用途 | 效果 |
|---|---|---|
| LevelDB/RocksDB | 每个 SSTable 一个布隆过滤器 | 查询不存在时避免读磁盘，读放大从 10 降到 1 |
| Redis | BF.ADD / BF.EXISTS（RedisBloom 模块） | 缓存穿透防护 |
| Chrome | 恶意 URL 检测 | 本地过滤，保护隐私（不上传完整 URL） |
| Cassandra/HBase | 判断 row key 是否存在于某个 SSTable | 减少磁盘 IO |
| 比特币 | SPV 钱包的交易过滤（BIP37） | 轻节点节省带宽 |
最重要的应用：解决缓存穿透
问题：攻击者查询大量不存在的 key
→ 缓存不命中 → 每次都打到数据库 → 数据库崩溃
方案：在缓存前加布隆过滤器
1. 查询先过布隆过滤器
2. 返回"不存在" → 直接返回，不打数据库 ★
3. 返回"存在" → 查缓存 → 查数据库
效果：99% 的恶意查询在布隆过滤器层就被拦截
老陈：注意布隆过滤器的局限：它不支持删除。
原因：多个 key 共享同一个 bit。删除 A 会清掉 B 的标记。
如果需要删除，有两个方案：
- Counting Bloom Filter：把 bit 换成计数器（4-8 bit），删除时减一。代价是空间放大 4-8 倍。
- Cuckoo Filter：布谷鸟过滤器，支持删除，空间效率更高，但实现复杂。
这是”功能”和”空间”的又一次权衡。
数据结构 5：并查集（Union-Find）
为什么值得单独讲
并查集是**唯一一个摊还复杂度是”反阿克曼函数”**的数据结构——它增长慢到实际上可以认为是常数。
α(n) = 阿克曼函数的反函数
α(1) = 0
α(2) = 1
α(4) = 2
α(16) = 3
α(65536) = 4
α(2^65536) = 5
★ 对宇宙中所有原子数（10^80），α(n) = 4
★ 实际上就是常数
两个优化
① 路径压缩（Path Compression）
func (uf *UnionFind) Find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.Find(uf.parent[x]) // ★ 递归时直接指向根
}
return uf.parent[x]
}② 按秩合并 / 按大小合并（Union by Rank/Size）
func (uf *UnionFind) Union(x, y int) {
rx, ry := uf.Find(x), uf.Find(y)
if rx == ry {
return
}
// ★ 小树挂到大树下，避免树变高
if uf.rank[rx] < uf.rank[ry] {
uf.parent[rx] = ry
} else if uf.rank[rx] > uf.rank[ry] {
uf.parent[ry] = rx
} else {
uf.parent[ry] = rx
uf.rank[rx]++
}
}两个优化缺一不可：
- 只有路径压缩：O(log n) 摊还
- 只有按秩合并：O(log n)
- 两者结合：O(α(n)) ★
Go 实现 + 应用：社交网络的好友关系
type UnionFind struct {
parent []int
rank []int
size []int // 每个集合的大小
count int // 连通分量数
}
func NewUnionFind(n int) *UnionFind {
uf := &UnionFind{
parent: make([]int, n),
rank: make([]int, n),
size: make([]int, n),
count: n,
}
for i := 0; i < n; i++ {
uf.parent[i] = i
uf.size[i] = 1
}
return uf
}
func (uf *UnionFind) Find(x int) int {
// 迭代版路径压缩（避免递归栈溢出）
root := x
for uf.parent[root] != root {
root = uf.parent[root]
}
// 路径压缩：把路径上所有节点直接指向根
for uf.parent[x] != root {
next := uf.parent[x]
uf.parent[x] = root
x = next
}
return root
}
func (uf *UnionFind) Union(x, y int) bool {
rx, ry := uf.Find(x), uf.Find(y)
if rx == ry {
return false // 已经连通
}
if uf.rank[rx] < uf.rank[ry] {
rx, ry = ry, rx
}
uf.parent[ry] = rx
uf.size[rx] += uf.size[ry]
if uf.rank[rx] == uf.rank[ry] {
uf.rank[rx]++
}
uf.count--
return true
}
func (uf *UnionFind) Connected(x, y int) bool {
return uf.Find(x) == uf.Find(y)
}
func (uf *UnionFind) ComponentSize(x int) int {
return uf.size[uf.Find(x)]
}
// 应用：朋友圈
// n 个人，m 对好友关系，求有多少个朋友圈
func FriendCircles(n int, friendships [][2]int) int {
uf := NewUnionFind(n)
for _, f := range friendships {
uf.Union(f[0], f[1])
}
return uf.count
}
// 应用：动态连通性 —— 判断图中是否有环
func HasCycle(n int, edges [][2]int) bool {
uf := NewUnionFind(n)
for _, e := range edges {
if !uf.Union(e[0], e[1]) {
return true // 两个点已经连通，再加边就有环
}
}
return false
}
// 应用：最小生成树 Kruskal 算法
type Edge struct {
U, V, Weight int
}
func Kruskal(n int, edges []Edge) (mst []Edge, totalWeight int) {
// 按权重排序
sort.Slice(edges, func(i, j int) bool {
return edges[i].Weight < edges[j].Weight
})
uf := NewUnionFind(n)
for _, e := range edges {
if uf.Union(e.U, e.V) {
mst = append(mst, e)
totalWeight += e.Weight
if len(mst) == n-1 {
break // 最小生成树有 n-1 条边
}
}
}
return
}并查集在分布式系统中的应用
老陈：你可能觉得并查集只是个”算法题玩具”。但它在真实系统里用得很多：
- 编译器的寄存器分配：图着色算法的合并阶段用并查集合并”不冲突”的变量
- Krushkal 最小生成树：网络拓扑、聚类
- 图像处理：连通区域标记（Connected Component Labeling）
- 数据库的数据分片：判断两个 key 是否在同一个分片
- Go 的逃逸分析：合并类型信息时用到了类似的思想
这个数据结构的价值在于：它把”集合合并”这个操作做到了理论最优，而且实现只有 30 行。
这是”简单 + 深刻”的典范，值得记住。
思考题 ·【应用层】
你要为一个 Go 写的时序数据库设计索引。需求：支持按 (metric_name, timestamp) 查询时间序列数据；数据保留 30 天；每秒写入 100 万数据点；查询主要是”查某个 metric 最近 1 小时的数据”。请设计存储结构和索引，说明每个选择针对什么硬件特性。
参考答案
需求分析
写入: 100 万点/秒 × 16 字节 = 16 MB/s
保留: 30 天 = 16 MB/s × 86400 × 30 = 41 TB （原始）
实际有压缩，约 4-8 TB
查询模式: 查某个 metric 最近 1 小时
→ 时间范围查询，且 metric 是过滤条件
→ 热点数据是最近的
关键观察：
- 写入是追加的（时间戳递增）→ 顺序写友好
- 查询总是按时间范围 → 时间是有序的
- metric 是高基数（可能有几百万个不同的 metric）
- 最近的数据是热点 → 可以分层
设计：LSM + 时间分区 + 倒排索引
层次 1：内存（最近 2 小时）
┌──────────────────────────────────────────┐
│ MemTable │
│ │
│ key: (metricID, timestamp) │
│ value: float64 │
│ │
│ 结构: 每个 metric 一个有序数组 │
│ (因为同一 metric 的时间戳基本递增) │
│ │
│ ★ 用 metricID → data[] 的 map │
│ data 是一个按时间排序的切片 │
│ 写入 = append（O(1)，顺序内存访问） │
└──────────────────────────────────────────┘
为什么不用跳表？
因为时序数据的写入几乎总是递增的时间戳。用有序数组 + append：
- 写入 O(1)（比跳表的 O(log n) 快）
- 内存连续，缓存友好
- 查询用二分 O(log n)
只有”补写历史数据”时才需要插入，这是罕见情况，用插入排序即可。
层次 2：磁盘（2 小时 ~ 30 天）
用 LSM-Tree 的分层结构，但按时间分块（Time Partitioning）：
/data/
├── 2026-08-29/
│ ├── 00/ ← 0-2 点的数据块
│ │ ├── meta.json
│ │ ├── data.bin ← 压缩后的数据点
│ │ ├── index.idx ← metricID → 在 data.bin 中的偏移
│ │ └── bloom.bf ← 布隆过滤器（快速判断 metric 是否存在）
│ ├── 02/
│ ├── 04/
│ └── ...
├── 2026-08-28/
└── ...
每个时间块（2 小时）的结构：
data.bin:
┌──────────────────────────────────────────────┐
│ metricID=1 的时间序列（压缩后） │
│ ├─ 时间戳: 用 Delta-of-Delta 编码 │
│ └─ 值: 用 XOR 编码（Facebook Gorilla） │
├──────────────────────────────────────────────┤
│ metricID=2 的时间序列 │
├──────────────────────────────────────────────┤
│ ... │
└──────────────────────────────────────────────┘
index.idx:
┌──────────────────────────────────────────────┐
│ B+Tree 或 有序数组 + 二分 │
│ metricID → (offset, length, startTime, │
│ endTime, pointCount) │
└──────────────────────────────────────────────┘
压缩：Gorilla 编码（Facebook 的方案）
时间戳压缩：Delta-of-Delta
原始时间戳: 1000, 1010, 1020, 1030, 1040
Delta: -, 10, 10, 10, 10
Delta-of-Delta: -, -, 0, 0, 0 ← 大部分是 0！
编码: 第一个 delta 用 14 bits
后续的 delta-of-delta:
0 → 1 bit ('0')
[-63,64] → 9 bits ('10' + 7 bits)
...
★ 实测：时间戳从 8 字节压缩到平均 0.3 字节（26 倍）
值压缩：XOR
时序数据的相邻值通常很接近（比如 CPU 使用率 45.2 → 45.3 → 45.1）
float64: 45.2 = 0x4046900000000000
45.3 = 0x4046A66666666666
XOR: = 0x0000F66666666666
↑ 前导 0 有 13 个，尾随 0 有 1 个
编码: 如果 XOR = 0 → 1 bit ('0')，表示值没变
否则 → '1' + 前导 0 数(5 bits) + 有效位长度(6 bits) + 有效位
★ 实测：值从 8 字节压缩到平均 1.5-2 字节（4-5 倍）
总体压缩率：16 字节 → 约 2 字节，8 倍。41 TB → 5 TB。
索引设计
为什么不用 B+Tree？
B+Tree 的问题：每次写入都要更新索引，而索引更新是随机 IO。
100 万点/秒 × 随机 IO = 灾难
用 LSM 的思路：索引也是批量构建的
内存里: metricID → 内存中的时间序列
↓ 每 2 小时 flush
磁盘上: 生成 index.idx（一次性顺序写入，之后只读）★
这样索引的写入也是顺序的！
索引的结构：有序数组 + 二分（因为块内不再修改）
type BlockIndex struct {
// 按 metricID 排序
entries []IndexEntry
// 布隆过滤器
bloom *BloomFilter
}
type IndexEntry struct {
MetricID uint64
Offset uint32 // 在 data.bin 中的偏移
Length uint32 // 压缩后的字节数
StartTime int64
EndTime int64
PointCount uint32
MinValue float64 // 预聚合，加速 MAX/MIN 查询
MaxValue float64
Sum float64 // 加速 AVG 查询
}
// 查询：二分查找
func (idx *BlockIndex) Find(metricID uint64) *IndexEntry {
// 先过布隆过滤器
if !idx.bloom.MayContain(metricIDBytes(metricID)) {
return nil // ★ 一定不存在，避免磁盘 IO
}
// 二分查找
i := sort.Search(len(idx.entries), func(i int) bool {
return idx.entries[i].MetricID >= metricID
})
if i < len(idx.entries) && idx.entries[i].MetricID == metricID {
return &idx.entries[i]
}
return nil
}查询流程
查询: metric="cpu.usage", 时间范围 [T-1h, T]
1. 确定要查哪些时间块
→ 最近 1 小时 = 1 个块（2 小时的块）
2. 对每个块:
a. 用布隆过滤器快速排除（如果该 metric 不在这个块里）
b. 二分查找 index.idx，找到 IndexEntry
c. 从 data.bin 的 offset 读 length 字节
d. 解压
e. 在时间范围内过滤
3. 同时查内存中的 MemTable（最近 2 小时还没落盘的）
4. 合并结果，按时间排序
IO 次数：
理想情况（metric 在布隆过滤器里命中，且数据连续）:
1 次读 index.idx（可能已经在 page cache 里）
1-2 次读 data.bin
★ 总共 1-3 次 IO
对比 B+Tree 方案:
需要为每个数据点更新索引 → 100 万次随机 IO/秒
冷热分层
最近 2 小时: 内存（MemTable） ← 查询最快
最近 2 天: SSD ← 次热
2-30 天: HDD / 对象存储 ← 冷数据
>30 天: 删除
★ 这个分层直接对应"访问频率"，也对应"存储成本"
每个设计针对什么硬件特性
| 设计 | 硬件特性 |
|---|---|
| MemTable 用有序数组而非跳表 | 时间戳递增 → append 是顺序内存访问 → 缓存友好 |
| LSM 风格，批量构建索引 | 顺序写比随机写快 100 倍（HDD）/ 10 倍（SSD） |
| 2 小时一个时间块 | 块大小 = 115GB，太大；这里按时间切，让查询能跳过整个块 |
| 布隆过滤器 | 用几 MB 内存，避免几千次磁盘 IO |
| Gorilla 压缩 | 减少 87% 的存储空间 → 减少 87% 的 IO 带宽 |
| 预聚合（Min/Max/Sum） | 避免读取原始数据（MAX 查询直接读索引） |
| 冷热分层 | 热数据放 SSD（低延迟），冷数据放 HDD（低成本） |
与通用方案的对比
| 方案 | 写入 | 查询 | 存储 | 适用 |
|---|---|---|---|---|
| MySQL (B+Tree) | 1 万点/秒 | 好 | 大 | ❌ 写入差 100 倍 |
| Cassandra (LSM) | 100 万点/秒 | 中 | 中 | ✅ 可以，但不是为时序优化 |
| InfluxDB (TSM) | 100 万点/秒 | 好 | 小 | ✅ 专用时序数据库 |
| 我们的设计 | 100 万点/秒 | 好 | 小 | ✅ 类似 InfluxDB |
这个设计基本就是 InfluxDB / Prometheus / TimescaleDB 的核心思路。
一句话总结
时序数据库的索引设计，核心是”让写入变成顺序，让查询跳过无关数据”：
- 写入顺序化 → LSM 风格，批量构建索引（针对磁盘的顺序/随机写差异）
- 查询剪枝 → 时间分区 + 布隆过滤器 + 预聚合（减少 IO 次数）
- 减少数据量 → Gorilla 压缩（减少 IO 带宽）
- 冷热分层 → 用存储成本换访问速度
每一个设计都能追溯到某个硬件特性。这就是”工程视角的数据结构”——不是背算法，而是理解硬件，然后让数据结构适配它。
第 2 章总结
三种规模的思维
| 规模 | 关注点 | 代表结构 |
|---|---|---|
| 缓存行级（64B） | 减少 cache miss | 紧凑数组、SoA、缓存行对齐 |
| 内存级（GB） | 减少指针跳转、GC 友好 | 跳表、哈希表、CSR 图 |
| 磁盘级（TB） | 减少 IO 次数、顺序化 | B+Tree、LSM-Tree、布隆过滤器 |
核心判断框架
选数据结构时，问这四个问题：
Q1: 数据在哪一层存储？（缓存 / 内存 / SSD / HDD / 网络）
→ 决定了优化的 target
Q2: 读写比例如何？
→ 读多写少用 B+Tree，写多读少用 LSM
Q3: 查询模式是什么？（点查 / 范围 / 聚合）
→ B+Tree 擅长范围，哈希表擅长点查，预聚合擅长聚合
Q4: 能接受近似吗？
→ 能接受用布隆过滤器 / Count-Min Sketch，不能就用精确结构
与第 1 章的联系
这一章的所有内容，都是第 1 章”存储层次”的应用：
第 1 章：理解了 L1/L2/L3/内存/磁盘/NUMA 的层次
第 2 章：学会了为每一层设计适配的数据结构
↓ 同一个法则
"让相关的东西物理上靠近"
· 缓存行 → 紧凑结构
· 内存页 → B+Tree 节点 = 页大小
· 磁盘 → LSM 的顺序写
下一章
老陈的预告：JVM 和 V8 是两座高峰。下一章我们不”学 Java”或”学 JS”，而是把它们当作”运行时设计的两个样本”来解剖——然后你会用 Go 手写一个 GC、一个字节码虚拟机、一个逃逸分析器。
学完之后，你能回答这个问题：如果 Go 的 GC 停顿还是太长，给我六个月，我怎么改？