磁盘最长的前缀查找

Question

i当前有一些实现，从radix树数据结构中执行最长的前缀查找(LPM(。该数据结构包含IP前缀(最大深度为128位的radix树(，目前已完全维护在内存中。数据是仅读取的数据，从不修改。

不幸的是，数据变得更大，我不再能够将其维护在内存中。我正在寻找可以在磁盘上保存的有效数据结构，并将提供有效的查找。我计划在其上使用一些缓存机制。

Answer 1

可以保存在磁盘上并提供有效查找的有效数据结构

对我来说看起来像是XY问题：

1. 我们正在谈论IPv6(128位(。
2. 我们正在谈论IPv6路由(最长的前缀匹配(。
3. 对于10 Gbit/s链接，每秒可能有多达1480万个路线查找。
4. 根据公共数据，目前大约有50k IPv6前缀。

如果上述假设是正确的，我们需要将50k乘以128位= 800kb存储在radix树中。它应该轻松地适合内存。

我们需要每秒查找这些数据数百万次。将数据放在磁盘上是数量级放缓的顺序。

我的猜测是您的问题不是您的根部问题，所以请：

1. 包括有关更广泛图片的信息以及任何尝试的解决方案。
2. 如果您已经排除了其他解决方案，请分享为什么您将它们排除在外。这提供了有关您要求的更多信息。

更新：

因此，在仅读取的20m IPv6前缀中，每小时是2m IPv6查找。我们仍然不知道这些20m前缀是什么，因为从实际的角度来看，整个互联网中没有很多前缀。但是无论如何。

1. 2m查找/小时〜550查找/秒。根据Wikipedia的说法，传统(机械(硬盘无法承受这种负担。因此，我们需要一个SSD驱动器来存储数据库。

2. 根据Wikipedia，B-Trees是外部搜索的好结构。

3. 根据Wikipedia的说法，内存映射的文件即使在非常大的文件中也使用少量RAM。

将所有位放在一起。这些20M IPv6前缀应组织为具有节点大小PAGE_SZIE(通常为4KB(的B树，并映射到该过程的虚拟地址空间中。缓存将通过操作系统管理，因此不需要其他缓存机制。