为何位图式位字典树未成为有序映射的主流实现方案？

• 硬件缓存亲和性的实际劣势
  像std::map底层的红黑树这类BST，节点结构极其紧凑：通常只包含键、值、左右子节点指针，单个节点占用内存极小，CPU缓存命中率更高。而位图式位字典树的节点需要存储至少8字节的位图，再加上子节点指针数组——哪怕多数子节点为空，数组本身也会占据不少内存。即便用动态数组增长和废弃数组复用的策略，节点的内存占用还是远大于BST节点，大规模数据场景下缓存未命中会大幅增加，反而抵消了指针解引用次数减少带来的性能收益，实际运行速度可能更慢。

• 实现复杂度与工程成本过高
  BST（尤其是红黑树）的逻辑已经极度成熟，几乎所有编程语言的标准库都有经过极致优化的实现，开发者无需从零构建。而位图式位字典树的实现门槛高得多：要处理Int64键的按位拆分逻辑、位图的位运算操作、动态数组的扩容与复用，还要实现有序遍历这一有序映射的核心需求——仅针对Int64键的位段拆分策略就需要大量调试优化，整体工程成本远超BST。

• 有序遍历效率不足
  有序映射的核心需求之一是范围遍历（比如从键A到键B的所有条目）。BST的中序遍历天然有序，遍历过程是连续的指针跳转，缓存友好性极佳。而位图式位字典树的遍历需要按位段顺序处理位图，逐个检查每个位对应的子节点，过程涉及大量位运算和非连续指针访问，遍历效率远不如BST。在很多有序映射的使用场景中，遍历性能的优先级甚至高于单次查找。

• 场景适配性狭窄
  BST几乎能适配所有可比较类型的键（字符串、自定义结构体等），只要能定义比较规则即可。而位图式位字典树严重依赖键的二进制结构，仅对Int64这类固定长度整数键适配良好，对变长键（比如字符串）的适配复杂度极高，通用性很差。实际开发中键的类型多种多样，这直接限制了它的应用范围。

• 已有成熟方案的替代挤压
  针对大规模整数键的有序映射需求，已有不少成熟替代方案：比如键可预排序时用数组存储+二分查找；跳表（如Redis有序集合的实现）的指针解引用次数与BST相当，但实现更简单、并发性能更好；如果不需要严格有序遍历，哈希表的性能优势更明显。这些方案要么实现更简单，要么特定场景下性能更优，进一步压缩了位图式位字典树的生存空间。

内容的提问来源于stack exchange，提问作者Andrey Godyaev