存储数十亿个整数的数据结构

Question

存储数十亿个整数的数据结构

clinuxperformancedata-structuresrecord

3

什么是在内存(RAM)中存储百万/亿级记录的最佳数据结构（假设记录包含名称和整数）？以最小搜索时间（第一优先级）和内存效率（第二优先级）为标准，最好的是什么？是 Patricia 树吗？还有其他更好的吗？

搜索键是整数（假设为32位随机整数）。所有记录都在RAM中（假设有足够的RAM可用）。

使用 C 语言，在 Linux 平台上实现。

基本上，我的服务器程序为用户分配一个32位随机密钥，并且我希望存储相应的用户记录，以便我可以以高效的方式搜索/删除记录。可以假定数据结构将被充分填充。

- Marc M

你是在搜索名称还是编号？还是两者都要？ - Dirk Vollmar

1

记录集是否经常更新，而且更新程度如何？整数的分布情况是怎样的？使用哈希表存储所有名称时，它们能舒适地适应你可用的内存吗？ - reinierpost

5个回答

2

我的猜测是一个B-Tree（但我可能错了...）：

当节点访问时间远远超过节点内访问时间时，B树比其他实现具有重大优势。这通常发生在大多数节点位于诸如硬盘驱动器之类的二级存储中时。通过最大化每个内部节点中的子节点数量，树的高度减少，平衡发生的次数较少，效率提高。通常，此值设置为每个节点占用一个完整的磁盘块或与二级存储中的类似大小的块。虽然2-3 B树可能在主存储器中很有用，并且肯定更容易解释，但如果将节点大小调整为磁盘块的大小，则结果可能是257-513 B树（其中大小与更大的2的幂相关）。

- pageman

0

你至少可以使用一个基数来开始代替哈希。

对于任何具体问题，你可以做得比B树、哈希表或Patricia Trie更好。描述问题得更好一些，我们可以建议可能适用的方法。

- Stephan Eggermont

0

如果你只需要通过整数键进行检索，则简单的哈希表是最快的。如果这些整数是连续的（或几乎连续）且唯一的，则一个简单的数组（指向记录的指针）甚至更快。

如果使用哈希表，您要预先分配期望最终大小的哈希表，以便它不需要重新哈希。

- Larry Watanabe

0

我们可以使用一种trie数据结构，其中每个节点是1/0来存储整数值。通过这种方式，我们可以确保树的深度为32/64，因此获取时间是恒定的，并且具有次线性空间复杂度。

- Pushya Mitra

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rutger Nijlunsing · Accepted Answer

视情况而定。

你想要按名称还是按整数进行搜索？

这些名称大小都差不多吗？

所有整数都是32位的，还是有一些大数字？

你确定它们全部能放进内存吗？如果不能，那么你可能受到磁盘I/O的限制，内存（或磁盘使用）就不再成为问题了。

索引（名称或整数）是否具有公共前缀，或者它们是否均匀分布？只有当它们具有公共前缀时，PATRICIA树才有用。

你是按顺序（gang lookup）查找索引，还是随机查找？如果一切都是均匀的、随机的而且没有公共前缀，那么哈希已经是最好的选择了（但这很糟糕）。

如果索引是使用gang lookup的整数，则可以考虑基数树。