四种Bucket选择算法的复杂度权衡

从一个 bucket 里伪随机选出一个子项，CRUSH 提供四种算法，权衡的是”增删子项的代价”与”查找复杂度”：Uniform 假设权重相同、几乎不增删，换来最快的查找；List 把子项存成链表、按权重比例递归查找，复杂度 O(n)，但新增子项只需加到表头，代价很小；Tree 把子项组织成带权重的决策树，查找是 O(log n)，增删代价比 List 略高；Straw（默认算法）给每个子项算一个”抽签长度” f(权重)×hash(x,r,i)，取值最大的中签，查找 O(n) 但增删任意一个子项对其余子项的选中结果影响最小，因此默认用它来尽量减少扩缩容引发的数据迁移量。没有一种算法全面占优，选择本质是”稳定不变的集合用更快的算法，频繁增删的集合用扰动更小的算法”。