在内存 (RAM) 中存储数百万/数十亿条记录(假设一条记录包含名称和整数)的最佳数据结构是什么。 最好的 - 最短搜索时间(第一优先级)和内存效率(第二优先级)？是帕特里夏树吗？还有比这更好的吗？
搜索关键字是整数(例如 32 位随机整数)。并且所有记录都在 RAM 中(假设有足够的 RAM 可用)。
在 C 中，平台 Linux..
基本上我的服务器程序会为用户分配一个 32 位的随 secret 钥，我想存储相应的用户记录，以便我可以高效地搜索/删除记录。可以假定数据结构将被很好地填充。
最佳答案
视情况而定。
您要搜索名称还是整数？
名字的大小都差不多吗？
所有整数都是 32 位的，还是一些大数字？
你确定这一切都适合内存吗？如果不是，那么您可能会受到磁盘 I/O 和内存(或磁盘使用)的限制，这就不再是问题了。
索引(名称或整数)是否有共同的前缀或它们是否均匀分布？只有当它们有共同的前缀时，帕特里夏树才有用。
您是按顺序(群组查找)还是随机查找索引？如果一切都是统一的、随机的并且没有共同的前缀，那么哈希就已经很好了(这很糟糕)。
如果索引是使用组合查找的整数，您可能会查看基数树。
关于c - 存储数十亿整数的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1199298/