当前位置：首页 > ai >正文

红黑树的线程安全的做法

ai 2025/5/14 22:50:46

🧭 本节概要

为什么红黑树需要线程安全
多线程下的读写冲突问题分析
常见加锁策略：粗粒度、细粒度、读写锁
使用 std::shared_mutex 实现线程安全的红黑树
读写并发模拟与完整 C++ 示例
总结和工程建议

一、为什么红黑树要线程安全？

红黑树本身是一种 高效平衡的搜索树，在内存管理、进程调度、数据库等系统中都有使用。在多线程环境中，多个线程同时访问/修改红黑树结构就可能出现如下问题：

❗常见冲突：

线程 A 正在插入新节点，线程 B 同时查找或删除，会导致野指针访问
线程 A 删除节点后旋转结构，线程 B 引用该节点时程序崩溃
内存泄漏、死锁、脏读、写入丢失等

因此，确保红黑树线程安全至关重要。

二、线程安全的几种策略

✅ 粗粒度锁（简单但影响并发）

使用一个 mutex，所有操作（读写）都锁整个树
优点：实现简单
缺点：性能差，不支持读写并发

✅ 细粒度锁（复杂但高性能）

每个节点加锁
插入/删除时只锁路径上的节点
实现复杂，要处理死锁问题

✅ 读写锁（推荐策略）

使用 C++17 std::shared_mutex
读操作加共享锁 shared_lock
写操作加独占锁 unique_lock
允许多个读线程并发读，写线程独占写

三、线程安全红黑树整体架构

template<typename Key, typename Value>
class ThreadSafeRBTree {
private:
struct Node {
Key key;
Value value;
Color color;
Node *left, *right, *parent;
Node(Key k, Value v): key(k), value(v), color(RED),
left(nullptr), right(nullptr), parent(nullptr) {}
};Node* root;
mutable std::shared_mutex tree_mutex; // 支持读写并发// 各种操作：插入、删除、查找等内部封装public:
ThreadSafeRBTree(): root(nullptr) {}void insert(Key key, Value value);
void erase(Key key);
bool find(Key key, Value& value);
};

四、核心操作：线程安全实现

✅ 插入（写操作：独占锁）

void insert(Key key, Value value) {std::unique_lock<std::shared_mutex> lock(tree_mutex);// 调用普通红黑树插入算法（略）...
}

✅ 查找（读操作：共享锁）

bool find(Key key, Value& value) {std::shared_lock<std::shared_mutex> lock(tree_mutex);Node* curr = root;while (curr) {if (key == curr->key) {value = curr->value;return true;} else if (key < curr->key)curr = curr->left;elsecurr = curr->right;}return false;
}

✅ 删除（写操作：独占锁）

void erase(Key key) {std::unique_lock<std::shared_mutex> lock(tree_mutex);// 调用红黑树删除算法（略）...
}

五、完整并发测试用例（含多线程插入 + 查找）

#include <iostream>
#include <thread>
#include <shared_mutex>
#include <vector>
using namespace std;int main() {ThreadSafeRBTree<int, string> tree;// 插入线程thread t1([&tree]() {for (int i = 0; i < 100; ++i) {tree.insert(i, "value" + to_string(i));}});// 查找线程thread t2([&tree]() {for (int i = 0; i < 100; ++i) {string val;if (tree.find(i, val))cout << "Found " << i << ": " << val << endl;elsecout << "Not found: " << i << endl;}});t1.join();t2.join();
}

六、实战工程建议

场景	加锁策略	说明
单线程	无需锁	最快
多线程读 + 少量写	`shared_mutex`	性能好
写操作频繁	粗锁或细粒度锁	细粒度更高效但复杂
极致并发场景	无锁数据结构	使用 skiplist 或 lock-free tree