最快的可搜索数据结构？ [英] fastest searchable datastructure?

问题描述

我需要某种类型的数组/列表/ ...我可以用一个唯一的密钥将对象存储在一起

。最重要的是性能：我需要

在给定键列表中进行整个搜索。哪种数据结构

最适合这个？哈希表？该列表可能包含最多10 ^ 12

项目，大部分时间更合适+ - 10 ^ 9甚至10 ^ 6 ...


非常感谢提前，

Pieter

Hi,

I need some type of array/list/... In which I can store objects together
with a unique key. The most important thing is performance: I will need to
do the whole time searches in the list of given keys. Which datastructure
will be best suited for this? A Hashtable? The list may contain upto 10^12
items, bit more proably most of the time +- 10^9 of even 10^6...

Thanks a lot in advance,
Pieter

推荐答案

我需要某种类型的数组/列表/ ...其中我可以将对象存储在一起

I need some type of array/list/... In which I can store objects together

使用唯一键。

with a unique key.

听起来像字典< TKey，TValue> ...

Sounds like Dictionary<TKey, TValue>...

该列表最多可包含10 ^ 12

The list may contain upto 10^12

说真的吗？你确实意识到即使每个项目只有一个字节，没有

索引开销，填充等等，这是TB？


我要去假设这是一个错字 - 但即便如此，对于大数字来说，你可能更好地使用数据库方法，在这个领域使用非聚集的

唯一索引（只有;不要跨越 - 让它使用书签

查找来获取值）并且理想情况下使用不同的

文件组的索引来获取主数据。


Marc

Seriously? You do realise that even at one byte per item, with no
index overhead, padding, etc that''s a TB?

I''m going to assume that is a typo - but even so, for large numbers
you may be better using a database approach, with a non-clustered
unique index on this field (only; don''t span - let it use a bookmark
lookup to get the value) and ideally with the index on a different
file-group to the main data.

Marc

Thansk都是你的答案！


其实：它'不是一种类型：它可以理论上达到6 * 10 ^ 12 :-)

但正如我所说的：我希望实际执行+ - 10 ^ 6 ...


当amoutn太大时我确实会使用SQL Server ...但是如果

它在10 ^ 6以下：字典会更好吗？哈希表？或者

soemthing？


" Marc Gravell" < ma ********** @ gmail.comwrote in message

news：e0 ******************** ************** @ h11g2000 prf.googlegroups.com ...

Thansk both for your answer!

Actually: it''s not a type: it could go theoretical upto 6*10^12 :-)
But as I said: I expect a practical implementation of +- 10^6...

I will use indeed SQL Server when the amoutn will be too big... But in case
it''s underneath 10^6: Will a dictionary be better than a Hashtable? Or
soemthing else?

"Marc Gravell" <ma**********@gmail.comwrote in message
news:e0**********************************@h11g2000 prf.googlegroups.com...

>我需要某种类型的数组/列表/ ...我可以用一个唯一的密钥将对象存储在一起
。

>I need some type of array/list/... In which I can store objects together
with a unique key.

听起来像字典< TKey，TValue> ...

Sounds like Dictionary<TKey, TValue>...

>该列表可能包含最多10 ^ 12

>The list may contain upto 10^12

说真的吗？你确实意识到即使每个项目只有一个字节，没有

索引开销，填充等等，这是TB？


我要去假设这是一个错字 - 但即便如此，对于大数字来说，你可能更好地使用数据库方法，在这个领域使用非聚集的

唯一索引（只有;不要跨越 - 让它使用书签

查找来获取值）并且理想情况下使用不同的

文件组的索引来获取主数据。


Marc

Seriously? You do realise that even at one byte per item, with no
index overhead, padding, etc that''s a TB?

I''m going to assume that is a typo - but even so, for large numbers
you may be better using a database approach, with a non-clustered
unique index on this field (only; don''t span - let it use a bookmark
lookup to get the value) and ideally with the index on a different
file-group to the main data.

Marc

你知道这些内存中有多少内存10 ^ 12项"是否需要？

因为如果你的物理内存耗尽，你的整个过程将会因为分页而大幅上涨或者大幅放缓。

所以最好的替代方案可能是保存物品的数据库。在这种情况下，在主键上使用聚簇索引搜索

表将是

最快。

- Peter

网站： http://www.eggheadcafe.com
UnBlog： http://petesbloggerama.blogspot.com

MetaFinder： http://www.blogmetafinder.com

彼得写道：

Do you know how much memory 10^12 of these "items" is going to require?
Because if you run out of physical RAM, your whole process will either blow
up or slow down dramatically due to paging.
So the best alternative may be a database to hold your items. A search on a
table with a clustered index on a primary key in this case will be the
fastest.
-- Peter
Site: http://www.eggheadcafe.com
UnBlog: http://petesbloggerama.blogspot.com
MetaFinder: http://www.blogmetafinder.com
"Pieter" wrote:

我需要某种类型的数组/列表/ ...我可以在其中存储对象使用唯一键一起

。最重要的是性能：我需要

在给定键列表中进行整个搜索。哪种数据结构

最适合这个？哈希表？该列表可能包含最多10 ^ 12

项目，大部分时间更合适+ - 10 ^ 9甚至10 ^ 6 ...


非常感谢提前，


Pieter

Hi,

I need some type of array/list/... In which I can store objects together
with a unique key. The most important thing is performance: I will need to
do the whole time searches in the list of given keys. Which datastructure
will be best suited for this? A Hashtable? The list may contain upto 10^12
items, bit more proably most of the time +- 10^9 of even 10^6...

Thanks a lot in advance,
Pieter

这篇关于最快的可搜索数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！