Abstract: Balanced binary search tree is a typical structure for storing ordered data. With the coming of big data, high adjusting rate is incrementally affecting balanced binary search tree to be utilized in concurrent computation negatively. In order to resolve this drawback, this paper presents a type of balanced trigeminal search tree named Capacity Balanced Trigeminal search Tree（CBTT）, which stores two keys in each node and owns three sub-trees. Through complexity comparison and simulation experiment, the results show that: （1）compared to other ordered data structure, the worst height of CBTT is much lower; （2）range trading can be easily implemented by CBTT; （3）structure is stable so that few rebalanced operation ensues while inserting or deleting, and average internal path length is far shorter than typical balanced binary search tree. Owing to these advantages, CBTT runs fast and becomes more suitable for concurrent calculating.

Key words: ordered data structure, balanced tree, concurrent computing, trigeminal search tree

摘要： 平衡二叉树是一种用于存储有序数据的经典结构，伴随大数据时代的到来，平衡二叉树调整率高的问题愈发影响其运用于并行计算。有鉴于此，提出一种平衡三叉树，这种三叉树的一个节点存储两个值，维护三棵子树。通过复杂度对比与模拟实验结果表明：（1）相较其他有序数据机构，平衡三叉树具有较低的最坏高度；（2）平衡三叉树可以轻易实施区间操作；（3）平衡三叉树不需要对结构进行经常性的调整，平均内部路径长度远远小于传统平衡二叉树算法，运行速度快，更适合于并发应用。

关键词: 有序数据结构, 平衡树, 并行运算, 三叉树