我正在考虑实现一个IP黑名单，发现基数树和红黑树都可以用作存储IP黑名单的数据结构。我注意到很多现有的IP匹配实现都使用基数树，而Linux内核中使用红黑树来管理虚拟地址空间，这与IP匹配类似。所以我想知道它们在存储这种定长、可排序、常见范围的数据时有什么区别。
我注意到“合并”方面的差异。例如，对于4位数据，基数树无法合并两个具有不同前缀的数据，而红黑树在这方面不受限制。例如，“0111”不能合并基数树中的“1000”，但红黑树可以在表示范围的节点中存储“
我想听听任何会影响数据结构选择的因素（例如内存使用、工作负载、缓存？）。
当您假设两个随机获取的数据样本具有相同前缀的概率较高时，基数树更可取。如果您禁止 IP，它们很可能会出现在同一子网中，但您不希望（如果您）禁止整个子网。因此这些IP之间的公共前缀存在压缩。 如果您获得更均匀分布的数据，与更通用和平衡的方法红黑树相比，您将失去性能。我认为您的域倾向于使用基数树。
如果您正在考虑将范围存储在 rb-tree 中，那么实际上管理适用于禁止子网的范围树，您可能会注意到您也可以在基于基数树的解决方案中这样做。