具有针对不断更新键的范围搜索的数据结构

Question

我需要存储很多数据流，包括：

struct Flow {
    source: Address,
    destination: Address,
    last_seq_num_sent: u32,
    last_seq_num_rcvd: u32,
    last_seq_num_ackd: u32
}

我需要通过last_seq_num_rcvd查询。我可以保证（用离屏魔法）这个字段在所有流中的唯一性。

流量可能发生在不可靠的连接上，因此一些序列号可能会由于网络数据包丢失而被跳过。我通过使用 window 来解释这一点，它也保证了整个范围的唯一性。数据流的速率相互独立，但有能力在冲突发生前重新编号它们的序列号。

因此，目标是对流执行范围查询，以在某个给定下一个序列号的 WINDOW_SIZE 常数距离内找到具有 last_seq_num_rcvd 的任何流。

我认为 BTreeMap 适合这里，因为它具有范围查询能力。

const WINDOW_SIZE = 10;
struct FlowValue { /* All original fields, minus last_seq_num_rcvd which now acts as key */ }

let mut flows = BTreeMap<u32, FlowValue>::new();

let query = 42;
for (k, v) in flows.range(Excluded(query), Included(query + WINDOW_SIZE)) {
    // This is how I would query for a flow
}

但现在我的密钥经常变化。似乎没有有效的方法就地更新它；它需要完全删除和重新插入（在递增键下），这听起来像是一项昂贵的操作。

BTreeMap方法是不是太贵了？有没有替代的数据结构？或者我可以重载 BTreeMap 以实际执行整数键的有效就地增量吗？

Answer 1

您说得对，B-Tree 地图对于此应用来说有点贵。

由于 window 大小不变，更快的实现是将序列号划分到大小约为 WINDOW_SIZE/2 的桶中。然后根据他们的 rcvd 桶将流放入哈希 table。

然后，要找到特定数据包的流，您只需查找可能包含匹配流的 3 个桶，并测试桶中的每个流。这将比 B-Tree 查找更快。

在更新时，情况更好，因为您只需要在条目更改存储桶时更新哈希 table，并且每 WINDOW_SIZE/2 个数据包只发生一次。

具有针对不断更新键的范围搜索的数据结构

Data Structure with Range Search Against Constantly Updating Keys

rust

data-structures

btreemap