良好的数据结构,可以有效地插入/查询任意属性

Question

我正在开发一个项目,其中Arrays是所有内容的默认数据结构,每个查询都是以下列形式的线性搜索:

• 需要一个具有特定名称的客户？ customer.Find(x => x.Name == name)
• 需要具有特定唯一ID的客户？ customer.Find(x => x.Id == id)
• 需要特定类型和年龄的客户？ customer.Find(x => x is PreferredCustomer && x.Age >= age)
• 需要特定名称和年龄的客户？ customer.Find(x => x.Name == name && x.Age == age)

在几乎所有情况下,查找的标准都是明确定义的.例如,我们仅按一个或多个属性Id,Type,Name或Age搜索客户.我们很少搜索任何其他内容.

是否有一个好的数据结构来支持这些类型的任意查询,而查找优于O(n)？.NET的任何开箱即用的实现？

Answer 1

对于记忆，您有几种选择。

大多数选项的复杂度都是 O(n)。话虽这么说，字典查找可以接近 O(1)。

一种选择是将您的客户存储在多个字典中，每个字典都有一个设置为“姓名”、“ID”和“年龄”的键。如果在字典中使用相同的对象引用，则可以进行任何单次查找 O(1)，而无需大量开销。

诚然，随着标准数量的增加，这会变得不太实用，但对于 3 个标准来说，这也不算太糟糕。

如果您想要更大的灵活性，那么数据库是一个合适的选择。许多数据库都可以选择作为完全内存数据库工作，包括 SQLite，它允许以比 O(n) 速度快得多的任意查询。