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

在内存（RAM）中存储数百万/数十亿条记录（假设记录包含名称和整数）的最佳数据结构是什么？最佳搜索时间（第一优先级）和内存有效性（第二优先级）？它是帕特里夏树吗？任何其他比这更好？存储数十亿整数的数据结构

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

在C，平台的Linux ..

基本上我的服务器程序分配一个32位的随机密钥给用户，我想存储相应的用户记录，这样我可以搜索/删除有效的方式记录。可以假定数据结构将被很好地填充。

来源

2009-07-29 Marc M

您是否在搜索名称或号码？或两者？ – 2009-07-29 10:38:47

这组记录是否经常更新，并且有多彻底？整数的分布是什么样的？将所有名称的哈希表安装在您可用的内存中是否舒适？ – reinierpost 2009-07-29 10:43:50

取决于。

你想搜索名称或整数？

这些名称都大约相同吗？

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

你确定这一切都适合内存？如果没有，那么你可能受到磁盘I/O的限制，内存（或磁盘使用率）不再是问题。

索引（名称或整数）是否具有相同的前缀或是否均匀分布？只有他们有共同的前缀，帕特里夏树才有用。

你是按顺序查找索引（团伙查找）还是随机查找索引？如果一切都是统一的，随机的，没有共同的前缀，散列已经是一样好（这是不好的）。

如果索引是使用组合查找的整数，则可以查看基数树。

来源

2009-07-29 10:41:51

很多问题都可以在RAM中适用。昨天我配置了一个带有96 GB RAM的Dell，价格低于20K欧元 – 2009-07-29 11:33:41

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

B树中都具有相当的优势在替代实现时节点的访问时间节点内，远远超出访问倍。当大多数节点位于辅助存储设备（如硬盘驱动器）时，通常会发生此问题。通过最大化每个内部节点内的子节点的数量树的高度减少，平衡发生的次数减少，并且效率增加。通常这个值被设置为使得每个节点在第二存储器中占满整个磁盘块或类似的大小。虽然2-3 B树可能在主内存中有用内存，并且当然更容易到说明，如果节点大小调整为为磁盘块的大小，则结果可能是257-513 B-树（其中尺寸与较大的的幂相关）。

来源

2009-07-29 10:56:59 pageman

而不是散列，你至少可以使用基数开始。

对于任何特定问题，您可以比btree，哈希表或patricia trie更好地完成任务。将问题描述得更好一些，我们可以建议可能的工作

来源

2009-07-29 11:37:27

如果您只想用整数键进行检索，那么简单的哈希表就是最快的。如果整数是连续的（或几乎连续的）并且是唯一的，那么一个简单的数组（指向记录的指针）甚至更快。

如果使用散列表，您希望为预期的最终大小预分配散列表，以免重新散列。

来源

2009-07-29 16:31:54

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

回答

相关问题