第7章：哈希索引与外部排序
元数据卡
维度 值 难度 （进阶） 前置 第4章 B+树（理解索引思想），基础排序算法知识 关键词 哈希索引、静态哈希、可扩展哈希、外排序、ORDER BY、DISTINCT、Merge-Join 代码语言 SQL / 伪代码 / Python
你的进度
在老陈的仓库里有两个很实用的工具间。一个是快速查找台——你说出一个货号，它直接告诉你位置，但没法告诉你'货号在A到C之间的所有货物'。另一个是巨大的分拣室，当货物太多、桌面放不下时，分拣员把货物分批搬到走廊上排好，再逐批合并。前者是哈希索引，后者是外部排序。
破局 · 溯源
等值查询——B+树够快，但还不够快
你走到快速查找台前，手里拿着一张纸条，上面写着'艾琳'。
B+树在点查上已经是 O(log n) 的优秀水平了。但数据库的 = 条件在语义上是最简单的——'给我精确的这个值'。用二分查找在树里定位 3-4 次，总觉得杀鸡用牛刀。
sql
-- 哈希索引的理想场景
SELECT * FROM adventurers WHERE name = '艾琳'; -- 精确匹配，大冒险者册，高并发
-- B+树的优势场景
SELECT * FROM adventurers WHERE level BETWEEN 20 AND 30; -- 范围查询
SELECT * FROM adventurers ORDER BY adventurer_id DESC LIMIT 10; -- 排序有没有一种结构，可以在常数时间内完成等值匹配？哈希表就可以。
哈希索引——O(1) 的代价与限制
'试一下。'老陈把你带到快速查找台前——一个带着编号柜子的小台子，你输入'艾琳'，柜门直接弹开了。
基本原理：对键做哈希函数，得到一个哈希值，然后用这个哈希值在数组中找到槽位（bucket）。
pseudo
hash("艾琳") → 0xA3B2C1D4
↓
bucket_index = 0xA3B2C1D4 % num_buckets → 17
↓
bucket[17] → ("艾琳" row_id=42)
查找：1 次哈希计算 → 1 次数组索引 → 完成
不需要树搜索，不需要比较。一个简单哈希索引的磁盘布局：
Hash Table Directory
(定长数组，每个元素是
指向桶的指针)
0 1 2 ... n-2 n-1
桶0 桶1 桶2
hash hash hash
键 键 键
指针→ 指针→ 指针→
溢出页
hash
overflow
← 多个键映射到同一桶时用链表链起来哈希索引的限制：
- 不支持范围查询。
age > 20无法用哈希索引——哈希函数破坏了键的顺序。 - 不能排序。
ORDER BY name走不了哈希索引。 - 不支持部分匹配。
LIKE 'ali%'也无法使用。 - 哈希冲突需要处理。链表或开放寻址。
这就是为什么 B+树是数据库索引的"全能选手"，哈希索引是"专才"。
静态哈希 vs 动态哈希
静态哈希（Static Hashing）——建好了不能改
'最简单的做法，'老陈指了指台子后面的一个固定柜子，'假设箱子数量是固定的——比如 1024 个。'
哈希表的桶数是固定的。选一个足够大的初始大小。
桶数 = 1024
hash(key) % 1024 → 0-1023问题：
- 数据量暴增时，所有桶都满了 → 溢出链越来越长 → 最终退化成链表 O(n)
- 数据量很少时，大部分桶空着 → 空间浪费
'一个要命的缺陷，'老陈说，'你必须在建表时预知数据量。但谁说得出一年后要塞多少东西？'
可扩展哈希（Extendible Hashing）——满的桶才分裂
'另一种做法：桶不够用了就扩容，而且只扩装满了的那个。'
可扩展哈希的核心想法：动态增加桶数，每次只分裂装满的那个桶，不重建整个表。
结构：
Global Depth = 2 ← 全局深度，决定目录大小 = 2^depth = 4
Directory:
[ 00 → 桶A ] ← 两个目录项指向同一个桶（桶A的本地深度=1）
[ 01 → 桶B ] ← 桶 B 的本地深度=2
[ 10 → 桶A ] ← 两个目录项指向同一个桶
[ 11 → 桶C ] ← 桶 C 的本地深度=2
每个桶有本地深度（Local Depth）：
- 桶A: local_depth=1（前 1 bit 决定它指向哪些目录项）
- 桶B: local_depth=2
- 桶C: local_depth=2插入触发分裂：
pseudo
// 插入 key=15 (hash=1111)，计算 hash % 4 = 3，对应目录项 [11] → 桶C
// 桶C已满 → 分裂
步骤：
1. 桶C分裂成 桶C' (hash的最后 2 bits = 11) 和 桶D (最后2 bits = ??)
实际是根据 hash 的第 3 个 bit 来分：
- 第3 bit = 0 → 留在 C
- 第3 bit = 1 → 去 D
2. 桶C 的 local_depth 从 2 变成 3
桶D 的 local_depth = 3
3. 如果 3 > global_depth (2)，目录需要翻倍：
从 [00011011] → [000001010011100101110111]
原来的目录项复制到新的两个位置
4. 更新目录项，让新桶D 被正确指向这个设计的关键：只有装满的桶才分裂，而且分裂是局部的。
python
# 可扩展哈希（简化）
class ExtendibleHashIndex:
def __init__(self bucket_capacity=4):
self.global_depth = 1
self.directory_size = 2 ** self.global_depth
self.directory = [Bucket(local_depth=self.global_depth)
for _ in range(self.directory_size)]
self.bucket_capacity = bucket_capacity
def hash_key(self key):
# 简化：直接用 key 的哈希值的低 global_depth 位
return hash(key) & (self.directory_size - 1)
def find(self key):
bucket_idx = self.hash_key(key)
bucket = self.directory[bucket_idx]
return bucket.get(key)
def insert(self key value):
bucket_idx = self.hash_key(key)
bucket = self.directory[bucket_idx]
if bucket.is_full():
self._split_bucket(bucket_idx)
# 分裂后重新插入
bucket_idx = self.hash_key(key)
self.directory[bucket_idx].insert(key value)
else:
bucket.insert(key value)
def _split_bucket(self idx):
bucket = self.directory[idx]
new_local_depth = bucket.local_depth + 1
if new_local_depth > self.global_depth:
# 目录需要翻倍
self._double_directory()
# 创建新桶
new_bucket = Bucket(local_depth=new_local_depth)
# 把旧桶的数据按新的 hash 值分配到两个桶
old_bucket = Bucket(local_depth=new_local_depth)
for k v in bucket.items:
h = hash(k)
if h & (2 ** (new_local_depth - 1)): # 检查新增的那位
new_bucket.insert(k v)
else:
old_bucket.insert(k v)
# 更新目录项
mask = (2 ** new_local_depth) - 1
for i in range(self.directory_size):
if (i & mask) == (idx & mask):
# 根据新增的那位决定指向旧桶还是新桶
if i & (2 ** (new_local_depth - 1)):
self.directory[i] = new_bucket
else:
self.directory[i] = old_bucket可扩展哈希的代价：目录翻倍意味着内存中的目录数组要扩大一倍（从
2^d到2^(d+1)）。如果 global_depth=20，目录有 100 万项。如果 global_depth=30，目录有 10 亿项——内存不够了。所以可扩展哈希不太适合主存有限的场景，但在内存较大或数据量可控的场景非常好用。
哈希索引在 MySQL Memory 引擎中的使用
MySQL 的 MEMORY（以前叫 HEAP）存储引擎完全基于哈希索引（可选的 BTREE 也支持）：
sql
-- MEMORY 引擎默认使用哈希索引
CREATE TABLE mem_adventurers (
adventurer_id INT NOT NULL PRIMARY KEY
name VARCHAR(100) NOT NULL
UNIQUE INDEX idx_name (name) USING HASH
) ENGINE=MEMORY;
-- 插入和查询
INSERT INTO mem_adventurers VALUES (1 '艾琳') (2 '铁锤');
SELECT * FROM mem_adventurers WHERE adventurer_id = 1; -- O(1) 哈希索引MEMORY 引擎的特点：
- 数据全部在内存中（重启丢失）
- 表级锁（不是行级锁）
- 哈希索引只支持
=和<=>（equals 运算符） - 不支持 BLOB/TEXT 类型
为什么生产环境很少用 MEMORY 引擎？
- 重启丢失数据
- 表级锁，高并发不够
- 内存消耗不可控
- 哈希索引不支持范围查询和部分匹配
实际生产中 Redis 才是哈希索引最成功的代表——使用全局哈希表，O(1) 的 GET/SET，配合 TTL、LRU 淘汰、丰富的数据类型，成为缓存的首选。
外排序——内存装不下时怎么排序？
你写了 ORDER BY amount DESC LIMIT 100。数据库怎么排 10 亿条记录？
如果 10 亿记录的 amount 列占 8GB 内存，没问题——内存排序（QuickSort）。但如果排的是整行数据（80GB），内存只有 16GB，这就需要用外排序（External Sort）。
外排序的核心思想：分而治之。
步骤 1：排序阶段（Sort Phase）
把数据分成若干块，每块小到能在内存中排序。对每块在内存中排序，写入临时文件。
80GB 数据 → 分成 10 个 8GB 的分块
块 1 → 内存排序 → sort_1.tmp
块 2 → 内存排序 → sort_2.tmp
内存 16GB 块 3 → 内存排序 → sort_3.tmp
8GB 给排序 ...
块 10 → 内存排序 → sort_10.tmp步骤 2：合并阶段（Merge Phase）
把多个有序的临时文件合并成一个有序的大文件——这就用到了多路归并（Multi-way Merge）。
pseudo
// 10 路归并
// 每个临时文件都有自己的"读取缓冲区"和当前最小记录
sort_1.tmp 中的最小值
↓
sort_1 10路归并器 输出文件（最终有序）
sort_2 (优先队列)
sort_3 每次从 10 个文件中取最小的那一个
... 写入输出文件，然后从该文件读取下一个值
sort_10python
# 多路归并的简化实现
import heapq
def merge_sorted_files(input_files output_file):
"""
多路归并多个有序文件
用堆（优先队列）每次取最小的记录
"""
heap = []
file_handles = []
# 打开所有文件，读取第一个元素到堆中
for i fname in enumerate(input_files):
f = open(fname)
file_handles.append(f)
first_line = f.readline().strip()
if first_line:
heapq.heappush(heap (first_line i))
with open(output_file 'w') as out:
while heap:
# 取出最小的
smallest file_idx = heapq.heappop(heap)
out.write(smallest + '\n')
# 从同一文件读取下一个
next_line = file_handles[file_idx].readline().strip()
if next_line:
heapq.heappush(heap (next_line file_idx))
for f in file_handles:
f.close()双缓冲优化
外排序中，I/O 的代价远大于 CPU 的代价。合并阶段的瓶颈是从临时文件中读数据。
双缓冲（Double Buffering）：当当前缓冲区被归并完时，后台预先加载下一个缓冲区。
pseudo
未使用双缓冲：
读 → 归并 → 等待读 → 归并 → 等待读 → ... (I/O 阻塞 CPU)
双缓冲：
缓冲区 A：[数据块] ← 正在被归并
缓冲区 B：← 后台预加载下一个数据块
当 A 归并完，切换到 B，同时开始加载 A
读 → 归并 → 切换 → 后台加载 → 归并 → 后台加载 → ... (流水线)数据库如何用外排序
ORDER BY——你写个排序，数据库在背后搬东西
'排个序听起来简单，'你边说边敲了一个查询。
sql
-- 触发外排序的查询
EXPLAIN ANALYZE SELECT * FROM vault_items
ORDER BY value DESC
LIMIT 100;执行计划中会看到 Sort Method: external merge 或者 Sort Method: quicksort。PostgreSQL 的执行计划允许你看到排序发生了多少次 I/O：
sql
-- PostgreSQL 中查看排序统计
SELECT *
FROM pg_stat_user_tables
WHERE relname = 'vault_items';
-- 查看 sort 相关字段当 work_mem 设置得太小不足以容纳要排序的数据时，PostgreSQL 会自动切换为外排序：
sql
-- 查看 work_mem
SHOW work_mem; -- 默认 4MB
-- 如果一个 ORDER BY 需要 100MB 内存
-- PostgreSQL 会：
-- 1. 分配 4MB 缓冲区
-- 2. 读 4MB 数据到内存 → 快排 → 写入临时文件 → 重复 25 次
-- 3. 25 路归并生成最终有序结果DISTINCT——去重也是排序的活
'那去重呢？'你又敲了一行。
sql
-- DISTINCT 的实现也依赖排序
SELECT DISTINCT item_type FROM vault_items;数据库有两种方式实现 DISTINCT：
- 哈希聚合：对
item_type做哈希，只保留第一次出现的值。适合基数低的情况。 - 排序 + 去重：先排序，然后遍历时跳过重复值。适合数据量大的情况。
当 DISTINCT 的数据量大到内存装不下时，数据库会使用外排序来去重。
pseudo
// 排序去重（Sort + Dedup）
// 1. 外排序 → 得到有序的 item_type 列表
// 2. 遍历：只保留"与前一个不同的值"
// 时间复杂度：O(n log n)（排序）+ O(n)（去重）
// 空间复杂度：O(1)
原始：武器 防具 药水 防具 武器 卷轴 药水
排序后：防具 防具 卷轴 药水 药水 武器 武器
去重后：防具 卷轴 药水 武器Merge-Join——两个排序列表的拉链式合并
'排序不光是为了展示结果，'老陈走到了分拣室旁边的档案整理台。'连接操作也靠排序提速。'
当两个表都已经按连接键排序后，可以用 Merge-Join 高效地做连接——就像把两条排好序的名单从头到尾'拉链'到一起：
sql
SELECT *
FROM quests q
JOIN adventurers a ON q.adventurer_id = a.adventurer_id
ORDER BY q.adventurer_id;Merge-Join 的步骤：
pseudo
// 假设两个表都按 adventurer_id 排好序了
//
// quests: [1 1 2 3 3 4 5 ...]
// adventurers: [1 2 3 4 5 6 7 ...]
//
// 双指针扫描：
quests 指针 → 1 1 2 3 3 ...
adventurers 指针 → 1 2 3 4 5 ...
Step 1: quests.adventurer_id(1) == adventurers.adventurer_id(1) → 输出匹配
Step 2: quests.adventurer_id(1) == adventurers.adventurer_id(1) → 输出匹配
Step 3: quests.next → 2 adventurers 不动 (因为 2 > 1)
更精确的算法：
1. quests 指针 p adventurers 指针 q
2. 如果 quests[p] == adventurers[q]：输出所有匹配对
3. 如果 quests[p] < adventurers[q]：p++
4. 如果 quests[p] > adventurers[q]：q++Merge-Join 的 IO 效率：
Merge-Join 对每个表只需要扫描一次（线性 I/O）
对比 Nested Loop Join：
- 内表可能被反复扫描（每次外表行都要在内表查找）
对比 Hash Join：
- 需要建立哈希表（额外内存）
- 哈希表也面临内存装不下的问题（Grace Hash Join）
Merge-Join 的代价主要来自"先排序"——如果表已经有序了，
Merge-Join 就是最高效的连接方式（没有之一）。sql
-- 在 PostgreSQL 中，可以看到 Merge-Join
EXPLAIN (ANALYZE BUFFERS)
SELECT * FROM quests q
JOIN adventurers a ON q.adventurer_id = a.adventurer_id
WHERE a.level > 20;
-- 如果 quests 已经有 adventurer_id 上的索引（有序），
-- Merge-Join 可能比 Hash Join 更优深入冒险
哈希索引的现代变体——Cuckoo Hashing
'还有一种特殊玩法，'老陈又翻开另一本资料，'叫 Cuckoo Hash——占用别人位置，被占的再去找新位置，就像……布谷鸟把蛋下到别的鸟窝里。'
Cuckoo Hash 作为一种现代哈希表实现，被一些数据库（如 MySQL 的某些实验特性）用于内存索引。
核心思想：使用两个哈希函数，解决冲突时不是链表，而是"踢走"一个已有元素。
pseudo
// Cuckoo Hashing
// 两张哈希表 T1 和 T2，两个哈希函数 h1 和 h2
插入 key=42:
1. if T1[h1(42)] 为空 → 直接插入
2. else:
- 把 T1[h1(42)] 的旧值 x 踢出去
- 插入 42 到 T1[h1(42)]
- 尝试把 x 插入到 T2[h2(x)]
- 如果 T2[h2(x)] 也满了 → 踢出旧值 y → 再回到 T1
- 如果超过最大踢出次数 → 扩容重新哈希
查找: 只需检查 T1[h1(k)] 和 T2[h2(k)] 两个位置
O(1) 最坏情况，没有链表Cuckoo Hashing 在数据库中的优势：确定性 O(1) 查找，没有链表遍历的开销，CPU 缓存友好。
常见陷阱
1. 哈希索引不是万能加速器
sql
-- 错误用法
CREATE INDEX idx_hash ON adventurers(level) USING HASH;
SELECT * FROM adventurers WHERE level > 20; -- 哈希索引不生效！
SELECT * FROM adventurers ORDER BY level; -- 哈希索引不生效！
-- 正确用法
CREATE INDEX idx_hash ON adventurers(name) USING HASH;
SELECT * FROM adventurers WHERE name = '艾琳'; -- 哈希索引完美适用MEMORY 引擎默认哈希索引＝你只能等值查询它。 如果误以为索引能加速范围查询，你就会得到一个全表扫描。
2. 外排序的 I/O 代价被低估
排序 10 个块，需要读取：10 次 × 块大小（写临时文件）+ 10 次 × 块大小（归并阶段读回）。
总 I/O = 2 × 数据量 × 通道数。
如果你的数据是 80GB，临时文件要用 160GB 的 I/O。如果磁盘带宽只有 200MB/s，排序需要 800 秒（13 分钟）——这还只是 I/O 时间，不包括归并 CPU。
优化方向：
- 增大
work_mem减少排序通道数 - 让表本身就是有序的（ORDER BY 列建索引）
- 使用 SSD
3. ORDER BY LIMIT 不一定是外排序
sql
-- 这个查询可能不需要全排序！
SELECT * FROM vault_items ORDER BY value DESC LIMIT 100;如果 value 上有 B+树索引，数据库直接遍历索引的最后 100 条记录就行——O(log n + 100)，不需要外排序。
如果没索引，数据库才需要做全排序（可能是外排序）并取前 100 条。
通关挑战
** 热身（5 分钟，必做）**
- 测试 MySQL MEMORY 引擎：
sql
CREATE TABLE mem_test (
adventurer_id INT NOT NULL PRIMARY KEY
name VARCHAR(100)
INDEX idx_name (name) USING HASH
) ENGINE=MEMORY;
INSERT INTO mem_test VALUES (1 '艾琳') (2 '铁锤') (3 '影刃');
-- 确认这走哈希索引
EXPLAIN SELECT * FROM mem_test WHERE name = '艾琳';
-- 确认范围查询不走索引
EXPLAIN SELECT * FROM mem_test WHERE name > '艾';- 测试 PostgreSQL 的外排序触发条件：
sql
-- 设置 work_mem 为很小的值
SET work_mem = '64kB';
-- 对 vault_items 排序
EXPLAIN (ANALYZE BUFFERS)
SELECT * FROM generate_series(1 1000000) item_id
ORDER BY item_id DESC;
-- 看 "Sort Method: external merge Disk: 12352kB"** 挑战（30 分钟，选做）**
实现一个外排序：
python
# external_sort.py
import os
import tempfile
import heapq
def external_sort(input_file output_file memory_limit_mb=16):
"""
对超大文件进行外排序。
参数：
input_file: 输入文件路径（每行一个整数）
output_file: 输出文件路径（排序后的整数，每行一个）
memory_limit_mb: 内存限制（MB）
算法：
1. 读入数据到内存，直到达到 memory_limit
2. 在内存中排序，写入临时文件
3. 重复步骤 1-2 直到输入文件读完
4. 多路归并所有临时文件
"""
# 你的实现在这里
pass
# 验证
def test_external_sort():
import random
# 生成测试数据（200 万个整数，约 15MB）
with open('/tmp/test_input.txt' 'w') as f:
for _ in range(2000000):
f.write(f"{random.randint(0 10000000)}\n")
# 用 1MB 内存限制做外排序
external_sort('/tmp/test_input.txt' '/tmp/test_output.txt'
memory_limit_mb=1)
# 验证结果
with open('/tmp/test_output.txt') as f:
lines = [int(line.strip()) for line in f]
assert lines == sorted(lines) "Sort failed!"
print(f" 排序正确，共 {len(lines)} 行")
test_external_sort()** 观察**：用 iostat 观察外排序的 I/O 模式：
bash
# 在 PostgreSQL 执行大排序时观察
iostat -x 1
# 你会发现：
# - 第一阶段（排序）：读写交替（读原始数据 → 写临时文件）
# - 第二阶段（归并）：读取平衡，写连续（写最终结果）验收标准
读完本章后，你应该能：
- [x] 解释哈希索引为什么 O(1)、为什么不支持范围查询和排序
- [x] 对比静态哈希和可扩展哈希的优缺点
- [x] 描述可扩展哈希在桶满时如何局部分裂（目录翻倍）
- [x] 解释 MySQL MEMORY 引擎为什么不适合生产环境
- [x] 描述外排序的两阶段：排序阶段（分块排序）和合并阶段（多路归并）
- [x] 解释数据库如何用外排序做 ORDER BY（超过 work_mem 时）
- [x] 解释 Merge-Join 如何依赖有序数据及其 I/O 效率
- [x] 判断一个查询更适合哈希索引还是 B+树索引
常见卡点
| 卡点 | 原因 | 解决 |
|---|---|---|
| "哈希索引能处理重复键吗？" | 取决于实现。MySQL MEMORY 引擎的哈希索引支持链式溢出处理重复 | 重复键在哈希桶中用链表。查找时需要遍历链表 |
| "外排序的临时文件还放哪里——不是内存也不够吗？" | 临时文件放在磁盘上。数据库的 temp_tablespaces（PG）或 tmpdir（MySQL）指定位置 | 要确保临时目录所在磁盘有足够的空间 |
| "Merge-Join 和 Hash Join 哪个快？" | 如果数据已经有序 → Merge-Join 更快（线性扫描）。如果无序 → Hash Join 通常更快 | 这是查询优化器的选择。可以通过 enable_mergejoin = off 强制禁用看区别 |
| "MySQL 的 MEMORY 引擎既然哈希索引这么好，为什么 Redis 更流行？" | MEMORY 引擎是表级锁、只支持 SQL。Redis 是单线程事件循环、丰富的数据结构、天然的 TTL | 需求不同。需要 SQL 兼容和 JOIN 用 MEMORY，需要高性能缓存用 Redis |
现在不需要理解
- Grace Hash Join：当哈希表本身也放不下内存时的 Hash Join 实现（也用到外排序的思想）
- Linear Hashing：可扩展哈希的另一变种，逐步增长桶数，不用目录翻倍
- T-tree：内存数据库中针对时间序列的混合索引
- 基数排序的数据库应用：在特定场景比比较排序更快的外排序方法
旅人笔记
哈希索引和 B+树是数据库索引的阴阳两面——哈希专攻等值查询的 O(1)，B+树统揽范围查询的 O(log n)。外排序则是数据库"你给多少内存我就做多少事"的工程体现：内存不够时，磁盘是你的伙伴，归并是你的算法。这三者共同构成了数据库在"你怎么找到数据"和"你怎么排好数据"两个核心问题上的答案。