二叉树并不特别适合多线程，因为重新平衡可能会在树范围的修改中退化。此外，全局互斥体会对性能产生非常负面的影响。
我强烈建议使用已经编写的线程安全容器。例如，英特尔TBB包含一个concurrent_hash_map.
如果您愿意learn然而，这里有一些关于构建并发排序关联容器的提示（我相信完整的介绍不仅超出了我的能力范围，而且也不合适，在这里）。
读者/作家
您可能想要使用读取器/写入器互斥体，而不是常规互斥体。这意味着并行读取，而写入保持严格顺序。
Own Tree
您还可以构建自己的红黑树或 AVL 树。通过每个节点使用读取器/写入器互斥体来扩充树结构。这允许您仅阻止part即使在重新平衡时，也是树的一部分，而不是整个结构。eg键间隔足够远的刀片可以是平行的。
跳过列表
链接列表更适合并发操作，因为您可以轻松隔离modified zone.
A 跳过列表建立在这个优势的基础上，但增强了结构以通过密钥提供 O(log N) 访问。
遍历列表的典型方法是使用交过手习语，即在释放当前节点的互斥体之前获取下一个节点的互斥体。跳跃列表添加了第二个维度，因为您可以在两个节点之间潜水，从而释放这两个节点（并让其他步行者走在您前面）。
实现比二叉搜索树简单得多。
执着的
另一个有趣的部分是持久（或半持久）数据结构的想法，通常在函数式编程中找到。二叉搜索树特别适合它。
基本思想是节点（或其内容）一旦存在就永远不会更改。您可以通过共享一个可变的head，这将指向更高版本。
- 读取：复制当前头，然后放心使用（信息不可变）
- 写入：您要在常规树中修改的每个节点都会被复制并修改副本，因此您每次都会重建树的一部分（直到根），并更新head指向新的根。有一些有效的方法可以在下降树时重新平衡。写入是连续的
主要优点是地图版本始终可用。也就是说，你可以随时read即使另一个线程正在执行插入或删除。此外，因为read访问只需要一个同时读（复制根指针时），它们接近无锁，因此具有出色的性能。
引用计数（固有的）是这些节点的朋友。
注意：树的副本非常便宜:)
我不知道 C++ 中并发跳过列表或并发半持久二叉搜索树的任何实现。
