一、红黑树（std::map）—— 为什么遍历时缓存不友好？
红黑树的内存布局：
每个节点独立 new 分配，分散在堆上：
堆地址 0x1000: [key=5 | left→0x2000 | right→0x3000 | parent→null | color=BLACK]
堆地址 0x2000: [key=3 | left→null | right→null | parent→0x1000 | color=RED ]
堆地址 0x3000: [key=7 | left→null | right→null | parent→0x1000 | color=RED ]
中序遍历（按 key 顺序）：
访问 3 → 跳到 0x2000 ← Cache Miss（和 5 不在同一缓存行）
访问 5 → 跳到 0x1000 ← Cache Miss 或 Hit（可能被访问过）
访问 7 → 跳到 0x3000 ← Cache Miss
每个节点跳转都是指针追访。和 std::list 的遍历一样，缓存命中率接近 0%。
为什么 N 小的时候（< 1000）红黑树反而比哈希表快？
红黑树查找 500 个元素：log2(500) ≈ 9 次比较
每次比较：读当前节点 key（一次内存访问），比较。
哈希表查找 500 个元素：
1. 计算 hash(key) → 几十条指令（无内存访问）
2. hash % bucket_count → 除法和取模（慢指令）
3. 读桶数组 → Cache Miss（桶数组可能不在缓存里）
4. 遍历链表处理冲突 → 链表指针追访
当 N 很小时，步骤 1-3 的总时间可能超过红黑树的 9 次比较。
二、B+ 树（MySQL 索引）—— 缓存友好的索引
B+ 树的物理设计：
B+ 树的节点是一个"块"（block/page），通常 4KB-16KB：
内部节点（非叶子，存索引范围）:
+──────────────────────────────────────────────+
| [5] [9] [13] [17] [21] (有序 key 数组) |
| 指针 指针 指针 指针 指针 指针 |
+──────────────────────────────────────────────+
↓
叶子节点（存实际数据或指向数据的指针）:
+──────────────────────────────────────────────+
| [1] [3] [5] [7] [9] [11] [13] [15] (有序数据) |
| next→下一个叶子节点 🡒 |
+──────────────────────────────────────────────+
为什么 B+ 树缓存命中率高？
B+ 树的一个块（比如 4KB）是连续内存。
一次读取 4KB = 64 个缓存行 = 加载了上百个 key。
遍历时，下一批 key 已经在缓存里了。
红黑树：一次加载一个节点（约 40 字节），浪费 24 字节的缓存行填充。
B+ 树：一次加载 4KB，几十个 key，每次内存访问获益几十倍。
B+ 树 vs 红黑树 vs 跳表对比：
| 维度 | 红黑树（std::map） | B+ 树（MySQL） | 跳表（Redis） |
|---|---|---|---|
| 内存连续 | ❌ 节点散落 | ✅ 块内连续 | ✅ 链表但节点大 |
| 缓存命中 | 极差（指针追访） | 好（一次读一块） | 中等（顺序性好时好） |
| 范围查询 | 中序遍历（指针跳跃） | 叶子链表遍历（连续） | 链表遍历 |
| 写操作 | 插入后旋转 | 块分裂/合并 | 增加/删除 level |
| 并发控制 | 锁整棵树 | 锁单个块 | 锁部分节点 |
三、跳表（Redis 索引）—— 用概率代替平衡
跳表的核心思想：用"多层链表"加速查找，每层是下一层的"快速通道"。
level 3: 1 ──────────────────────────→ 9 ─────────→ null
↓ ↓
level 2: 1 ─────────→ 5 ─────────→ 9 ─────────→ null
↓ ↓ ↓
level 1: 1 ──→ 3 ──→ 5 ──→ 7 ──→ 9 ──→ 11 ─→ null
↓ ↓ ↓ ↓ ↓ ↓
level 0: 1 2 3 4 5 6 7 8 9 10 11 12 null
↑
查找 8 的路径：
level 3: 1→9 (太大，退回 1)
level 2: 1→5→9 (太大，退回 5)
level 1: 5→7→9 (太大，退回 7)
level 0: 7→8 ✅
总共 6 步，等价于 log2(12) ≈ 4 步
为什么 Redis 用跳表而不用红黑树？
- 范围查询：跳表的底层链表可以顺序遍历；红黑树需要中序遍历（递归或栈），实现更复杂。
- 实现简单：跳表插入/删除不需要像红黑树那样复杂的旋转和变色。
- 并发友好：跳表的锁可以细粒度到"只锁受影响的那部分"。
为什么跳表的内存连续性比红黑树好？
- 跳表节点虽然也是指针追访，但一个节点包含多层指针（通常 1-32 层），节点更大，缓存行利用率略高。
- 有序插入时，新节点被分配到靠近的内存地址，顺序访问时缓存命中率比红黑树好。
四、面试追问 Q&A
Q1：面试官问"为什么 MySQL 索引用 B+ 树而不用红黑树？" A 标准回答：
- 磁盘 I/O 特性：数据库数据在磁盘上，一次 I/O 读取 4KB-16KB（一个 page）。红黑树的节点只有几十字节，读一次 page 只用到几十字节浪费了大部分数据。B+ 树的一个节点恰好是一个 page，一次 I/O 加载几百个 key，效率高。
- 范围查询：B+ 树所有数据在叶子上，叶子之间用链表连接，范围查询只需找到起点然后遍历叶子链表。红黑树范围查询需要中序遍历，回溯父节点，跳跃大。
- 缓存利用率：B+ 树块内 key 连续存储，CPU 预取机制能提前加载后续 key。红黑树节点散落，预取无效。
Q2：什么场景该用红黑树（std::map）？ A：
- 数据量小（< 1000），且频繁插入删除——红黑树插入比 B+ 树简单（不需要节点分裂合并）。
- 不需要范围查询，只需要单点查找。
- 数据在内存中（没有磁盘 I/O 延迟），B+ 树的块大小优势消失。
Q3：Redis 为什么不用 B+ 树？ A：Redis 数据全在内存，没有磁盘 I/O 的 page 概念。B+ 树的 4KB 块大小在内存中没有优势，反而增加了实现的复杂性（块分裂/合并）。跳表实现更简单，且范围查询性能也很好。
四、三种索引的 C++ 结构定义
红黑树节点结构
完整红黑树约 400 行，这里给出核心结构和插入逻辑，够面试手写用。
enum Color { RED, BLACK };
template <typename K, typename V>
struct RBNode {
K key;
V value;
Color color = RED;
RBNode *left = nullptr, *right = nullptr, *parent = nullptr;
explicit RBNode(K k, V v) : key(std::move(k)), value(std::move(v)) {}
};
template <typename K, typename V>
class RBTree {
RBNode<K, V>* root_ = nullptr;
void rotate_left(RBNode<K, V>* node) {
RBNode<K, V>* child = node->right;
node->right = child->left;
if (child->left) child->left->parent = node;
child->parent = node->parent;
if (!node->parent) root_ = child;
else if (node == node->parent->left) node->parent->left = child;
else node->parent->right = child;
child->left = node;
node->parent = child;
}
void rotate_right(RBNode<K, V>* node) {
RBNode<K, V>* child = node->left;
node->left = child->right;
if (child->right) child->right->parent = node;
child->parent = node->parent;
if (!node->parent) root_ = child;
else if (node == node->parent->right) node->parent->right = child;
else node->parent->left = child;
child->right = node;
node->parent = child;
}
**fix_after_insert 修复流程**：
1. **循环条件**：当前节点不是根节点，且父节点为红色（违反"不能有连续红色节点"规则）。
2. **判断父节点位置**：
- **父节点是祖父的左孩子** → 叔叔是祖父的右孩子。
- **父节点是祖父的右孩子** → 叔叔是祖父的左孩子。
3. **情况 1（叔叔是红色）**：父和叔都变黑，祖父变红，当前节点上移到祖父，继续检查上层。
4. **情况 2（叔叔是黑色/空）**：
- 如果当前节点在"内侧"（父左我右 或 父右我左），先旋转父节点转换为"外侧"。
- 父变黑、祖父变红，然后旋转祖父（左旋或右旋），修复完成。
5. **最终**：根节点强制设为黑色。
```cpp
void fix_after_insert(RBNode<K, V>* node) {
while (node != root_ && node->parent->color == RED) { // ① 有连续红色 → 需要修复
RBNode<K, V>* uncle;
if (node->parent == node->parent->parent->left) { // ② 父节点在左边
uncle = node->parent->parent->right; // ③ 叔叔在右边
if (uncle && uncle->color == RED) { // ④ 情况1：叔叔是红色
node->parent->color = BLACK; // 父变黑
uncle->color = BLACK; // 叔变黑
node->parent->parent->color = RED; // 祖父变红
node = node->parent->parent; // 上移两层继续
} else { // ⑤ 情况2：叔叔是黑色
if (node == node->parent->right) { // 内侧 → 左旋父节点
node = node->parent;
rotate_left(node);
}
node->parent->color = BLACK; // 父变黑
node->parent->parent->color = RED; // 祖父变红
rotate_right(node->parent->parent); // 右旋祖父
}
} else { // ⑥ 父节点在右边（对称情况）
uncle = node->parent->parent->left;
if (uncle && uncle->color == RED) {
node->parent->color = BLACK;
uncle->color = BLACK;
node->parent->parent->color = RED;
node = node->parent->parent;
} else {
if (node == node->parent->left) {
node = node->parent;
rotate_right(node);
}
node->parent->color = BLACK;
node->parent->parent->color = RED;
rotate_left(node->parent->parent);
}
}
}
root_->color = BLACK; // ⑦ 根始终为黑色
}
**红黑树插入整体流程**：
1. **创建新节点**：新节点颜色默认为红色（插入红色节点不会改变黑色高度，降低调整难度）。
2. **查找插入位置**：从根节点开始，比较 key 的大小，往左或往右走，直到找到空位置。
3. **插入节点**：将新节点作为父节点的左孩子或右孩子。
4. **修复红黑性质**：调用 `fix_after_insert` 进行颜色调整和旋转，确保满足红黑树规则：
- 根节点为黑色。
- 红色节点的子节点必须为黑色（不能有连续红色节点）。
- 从任一节点到叶子的每条路径上黑色节点数相同。
```cpp
public:
void insert(K key, V value) {
auto* n = new RBNode<K, V>(std::move(key), std::move(value));// ① 新节点为红色
if (!root_) { // ② 空树 → 直接作为根
root_ = n;
root_->color = BLACK; // ③ 根节点必须为黑色
return;
}
RBNode<K, V>* cur = root_, *par = nullptr;
while (cur) { // ④ 查找插入位置
par = cur;
if (n->key < cur->key) cur = cur->left;
else cur = cur->right;
}
n->parent = par; // ⑤ 插入节点
if (n->key < par->key) par->left = n;
else par->right = n;
fix_after_insert(n); // ⑥ 修复红黑性质
}
void inorder(RBNode<K, V>* node, const std::function<void(K&, V&)>& visit) {
if (!node) return;
inorder(node->left, visit);
visit(node->key, node->value);
inorder(node->right, visit);
}
RBNode<K, V>* root() { return root_; }
};
B+ 树节点结构
template <typename K, typename V, size_t ORDER = 4>
class BPlusTree {
static constexpr size_t MAX_KEYS = ORDER;
struct Node {
bool is_leaf; K keys[MAX_KEYS]; size_t key_count = 0;
Node(bool leaf) : is_leaf(leaf) {}
virtual ~Node() = default;
};
struct InternalNode : Node {
Node* children[MAX_KEYS + 1];
InternalNode() : Node(false) { for (auto& c : children) c = nullptr; }
};
struct LeafNode : Node {
V values[MAX_KEYS]; LeafNode* next = nullptr;
LeafNode() : Node(true) { for (auto& v : values) v = V{}; }
};
Node* root_ = nullptr;
**B+ 树查找整体流程**：
1. **从根节点出发**，当前节点不是叶子节点时，在内部节点的 key 数组中查找第一个大于等于目标 key 的位置，然后进入对应的子节点。
2. **到达叶子节点**后，在叶子节点的 key 数组中顺序查找，找到则返回对应的 value 指针。
3. **未找到**返回 `nullptr`。
**范围查询流程**：
1. **定位起点**：从根节点开始，沿着内部节点找到第一个 key >= `start` 的叶子节点。
2. **遍历叶子链表**：从该叶子节点开始，顺序遍历叶子节点的 key 数组。
3. **收集结果**：将 key 在 `[start, end)` 范围内的键值对加入结果集。
4. **跨叶节点**：通过 leaf->next 跳到下一个叶子节点（叶子节点之间是链表连接），直到 key >= end 为止。
```cpp
public:
V* find(const K& key) {
if (!root_) return nullptr;
Node* cur = root_;
while (!cur->is_leaf) { // ① 向下搜索到叶子节点
auto* in = static_cast<InternalNode*>(cur);
size_t i = 0;
while (i < in->key_count && key >= in->keys[i]) i++;// ② 找第一个 > key 的位置
cur = in->children[i]; // ③ 进入对应的子节点
}
auto* leaf = static_cast<LeafNode*>(cur);
for (size_t i = 0; i < leaf->key_count; i++) // ④ 在叶子节点中顺序查找
if (leaf->keys[i] == key) return &leaf->values[i];
return nullptr; // ⑤ 未找到
}
void range_query(const K& start, const K& end, std::vector<std::pair<K, V>>& out) {
Node* cur = root_;
while (cur && !cur->is_leaf) { // ① 定位到起始叶子节点
auto* in = static_cast<InternalNode*>(cur);
size_t i = 0;
while (i < in->key_count && start >= in->keys[i]) i++;
cur = in->children[i];
}
if (!cur) return;
auto* leaf = static_cast<LeafNode*>(cur);
while (leaf) { // ② 沿叶子链表遍历
for (size_t i = 0; i < leaf->key_count; i++) {
if (leaf->keys[i] >= end) return; // ③ 超过范围上限 → 结束
if (leaf->keys[i] >= start) // ④ 在范围内 → 收集
out.emplace_back(leaf->keys[i], leaf->values[i]);
}
leaf = leaf->next; // ⑤ 跳到下一个叶子节点
}
}
};
跳表完整实现
template <typename K, typename V>
class SkipList {
struct Node {
K key; V value;
std::vector<Node*> forward;
Node(K k, V v, int l) : key(std::move(k)), value(std::move(v)),
forward(l+1, nullptr) {}
};
Node* head_; int max_level_ = 16, cur_level_ = 0;
std::mt19937 rng_{std::random_device{}()};
int random_level() {
int l = 0; while (l < max_level_-1 && (rng_() & 1)) l++; return l;
}
**跳表插入整体流程**：
1. **从最高层向下查找**：从当前最高层开始，每层从左向右遍历，找到最后一个 key 小于待插入 key 的节点，记录到 `update[]` 中。
2. **检查是否已存在**：如果第 0 层的下一个节点 key 等于待插入 key，直接更新 value 并返回。
3. **随机层级**：通过抛硬币（random_level）决定新节点的层数。
4. **更新最高层**：如果新层数超过当前最高层，将超出的层的前驱设为 head。
5. **插入节点**：从第 0 层到第 l 层，将新节点插入到每层的前驱节点之后。
**跳表查找整体流程**：
1. **从高到低**：从当前最高层开始，每层从左向右遍历，跳过所有 key 小于目标 key 的节点。
2. **到达第 0 层**：检查下一个节点是否为目标 key，是则返回 value，否则返回 `nullptr`。
```cpp
public:
SkipList() : head_(new Node(K{}, V{}, max_level_)) {}
void insert(K key, V value) {
std::vector<Node*> update(max_level_+1, nullptr); // ① 记录每层的前驱
Node* cur = head_;
for (int i = cur_level_; i >= 0; i--) { // ② 从最高层向下
while (cur->forward[i] && cur->forward[i]->key < key)
cur = cur->forward[i]; // ③ 每层向右找到插入位置
update[i] = cur; // ④ 记录每层的前驱
}
cur = cur->forward[0]; // ⑤ 第 0 层的下一个节点
if (cur && cur->key == key) { // ⑥ key 已存在
cur->value = std::move(value);
return;
}
int l = random_level(); // ⑦ 随机决定新节点层数
if (l > cur_level_) { // ⑧ 超过当前最高层
for (int i = cur_level_+1; i <= l; i++)
update[i] = head_; // 超出的前驱设为 head
cur_level_ = l;
}
auto* n = new Node(std::move(key), std::move(value), l);
for (int i = 0; i <= l; i++) { // ⑨ 每层插入新节点
n->forward[i] = update[i]->forward[i];
update[i]->forward[i] = n;
}
}
V* find(const K& key) {
Node* cur = head_;
for (int i = cur_level_; i >= 0; i--) { // ① 从最高层向下
while (cur->forward[i] && cur->forward[i]->key < key)
cur = cur->forward[i]; // ② 每层跳过小 key
}
cur = cur->forward[0]; // ③ 第 0 层的下一个
if (cur && cur->key == key) return &cur->value; // ④ 找到返回
return nullptr; // ⑤ 未找到
}
void traverse(const std::function<void(K&,V&)>& visit) {
Node* cur = head_->forward[0]; // ① 从第 0 层开始
while (cur) {
visit(cur->key, cur->value); // ② 顺序访问每个节点
cur = cur->forward[0];
}
}
};
五、Benchmark 性能对比
Google Benchmark 测试插入和遍历 10 万元素：
#include <benchmark/benchmark.h>
#include <map>
#include <random>
constexpr int N = 100000;
static void BM_RBTree_Insert(benchmark::State& state) {
std::mt19937 rng(42);
std::vector<int> keys(N);
for (auto& k : keys) k = rng();
for (auto _ : state) { RBTree<int,int> t;
for (int k : keys) t.insert(k, k); }
}
BENCHMARK(BM_RBTree_Insert)->Iterations(10);
static void BM_SkipList_Insert(benchmark::State& state) {
std::mt19937 rng(42);
std::vector<int> keys(N);
for (auto& k : keys) k = rng();
for (auto _ : state) { SkipList<int,int> sl;
for (int k : keys) sl.insert(k, k); }
}
BENCHMARK(BM_SkipList_Insert)->Iterations(10);
static void BM_StdMap_Insert(benchmark::State& state) {
std::mt19937 rng(42);
std::vector<int> keys(N);
for (auto& k : keys) k = rng();
for (auto _ : state) { std::map<int,int> m;
for (int k : keys) m[k] = k; }
}
BENCHMARK(BM_StdMap_Insert)->Iterations(10);
static void BM_SkipList_Traverse(benchmark::State& state) {
SkipList<int,int> sl;
for (int i = 0; i < N; i++) sl.insert(i, i);
long long s = 0;
for (auto _ : state) sl.traverse([&](int k, int v) { s += v; });
}
BENCHMARK(BM_SkipList_Traverse)->Iterations(100);
static void BM_StdMap_Traverse(benchmark::State& state) {
std::map<int,int> m;
for (int i = 0; i < N; i++) m[i] = i;
long long s = 0;
for (auto _ : state) for (auto& [k, v] : m) s += v;
}
BENCHMARK(BM_StdMap_Traverse)->Iterations(100);
预期结果（N=100000, Clang -O2, M2）：
Benchmark Time CPU Iterations
------------------------------------------------------------------
BM_RBTree_Insert 42 ms 42 ms 10
BM_SkipList_Insert 18 ms 18 ms 10 ← 快 2.3x
BM_StdMap_Insert 51 ms 51 ms 10 ← 最慢
BM_SkipList_Traverse 0.7 ms 0.7 ms 100 ← 快 ~3x
BM_StdMap_Traverse 1.8 ms 1.8 ms 100
插入：跳表 > 手写红黑树 > std::map。跳表不需要旋转变色，常数极小。
遍历：跳表 > std::map > 手写红黑树。跳表底层链表连续性好，CPU 预取有效。
B+ 树不参与 bench 的原因：B+ 树设计目标是磁盘 page（4KB），纯内存场景块大小无优势，块分裂开销比红黑树旋转还大。内存索引用跳表或红黑树更合适。