在现代 Go 或 Java 项目中，有序数据结构的选型往往面临两难：树结构（如红黑树、B 树）虽然操作复杂度低，但每个节点都需要独立的内存分配，带来显著的 GC 压力；数组虽然内存紧凑、缓存友好，但插入操作需要 O (N) 的元素移动开销。Black-White Array（以下简称 BWArr）试图在两者之间找到平衡点，其核心承诺是 插入操作仅需 O (log N) 次内存分配，同时保持数组的顺序存储特性。
设计起源与核心思想
Black-White Array 的概念源自 Brandes 大学 Z. George Mou 教授于 2020 年发表的论文《Black-White Array: A New Data Structure for Dynamic Data Sets》。该数据结构的核心创新在于引入了一种「双数组协作」机制：用一个「黑数组」存储主数据，用一个「白数组」作为辅助缓冲区。当新元素插入时，首先进入白数组；每当白数组满时，与黑数组进行一次性归并，将有序结果写回黑数组。这种设计使得单次插入的内存分配次数与数据规模呈对数关系，而非线性关系。
具体实现中，白数组的大小被设计为 log₂(N) 量级，其中 N 为黑数组中已有元素数量。每次插入时，元素首先写入白数组的对应位置 —— 由于白数组规模很小，其内部移动操作可以忽略不计。当白数组满时，触发一次归并过程，此时需要分配新的数组空间用于存放归并结果。这次分配的规模虽然与 N 相关，但触发的频率极低：只有当插入次数达到约 N/ln N 次时才会发生一次，因此从摊销角度来看，内存分配次数为 O (log N)。
与传统方案的对比优势
在典型的 Go 项目中，使用 container/list 或自行实现的链表进行有序存储，每次插入都可能触发一次堆分配。使用 Google 的 btree 库，虽然时间复杂度为 O (log N)，但每个节点同样需要独立分配。根据 bwarr 仓库提供的基准测试数据，在插入 100 万个唯一整数的场景下，bwarr 的内存分配次数仅为传统 btree 的约 1/20 至 1/30，这对于高频写入且对延迟敏感的服务而言意义重大。
更关键的是，BWArr 本质上仍是基于数组实现的，这意味着它天然具备优秀的缓存局部性。遍历整个数据结构时，CPU 可以高效地预取后续元素，而非像树结构那样频繁跳转指针。对于需要大量顺序遍历或范围查询的场景（如时间序列数据的有序存储），BWArr 的性能表现往往优于基于指针的树结构。
实用特性与当前局限
BWArr 实现了完整的有序集合接口，包括 Insert、Delete、Get、Len 以及 Ascend/Descend 两种方向的迭代器。值得注意的是，它原生支持重复元素 —— 这在很多业务场景中非常实用，例如统计数据的「多维度计数」场景，无需额外包装层即可直接存入重复值。
然而，工程实现中也需要关注其固有的权衡。首先，虽然摊销复杂度为 O (log N)，但每 N 次插入中有一次可能触发 O (N) 级别的归并操作，这可能在百万级数据量时产生可感知的延迟峰值。对于实时性要求极高的系统，建议结合异步写入或后台归并策略。其次，在小规模数据（<1000 元素）场景下，搜索与删除操作的常数因子反而可能高于纯红黑树实现，因为其内部需要额外的定位逻辑。
选型建议与落地参数
如果你的系统满足以下特征，BWArr 值得考虑：写入频率显著高于读取频率；对 GC 暂停高度敏感（如延迟敏感型服务）；需要有序遍历且数据量预计增长到十万级别以上。落地时建议配置初始容量提示（bwarr.New 的第二个参数），以减少初始阶段的扩容次数；同时监控归并操作的触发频率，当发现单次归并耗时超过 10ms 时，考虑引入后台批量写入机制。
作为首个公开实现，bwarr 目前仍在积极维护中。其 API 设计为 google/btree 的 drop-in 替代，迁移成本可控。随着后续版本对序列化与批量操作的支持完善，BWArr 有望成为 Go 生态中处理有序动态数据集的又一重要选项。
资料来源：bwarr 仓库（github.com/dronnix/bwarr）及 Z. George Mou 教授原始论文。