多谓词的数据结构和搜索算法

Question

有没有人知道用多谓词进行搜索的好的数据结构和算法。

例如，假设我有一组tcp报头数据(假设没有副本)。如果我按src ip搜索列表的tcp报头，我可以按src IP对集合进行排序并执行二进制搜索。

如果我想要从集合中找到与所有src/dst ip/port匹配的tcp报头，我应该使用哪种数据结构/算法？(除了遍历所有集合之外)。

Answer 1

这正是数据库供应商多年来一直在处理的事情。如果您要始终按src/dst IP/port进行搜索，则可以将其用作排序的标准，并或多或少地直接查找它。

否则，典型的方法是按一个字段对数据进行排序，并为其他字段构建索引。然后，您可以在每个索引中执行二进制搜索，以查找符合该字段条件的记录集。这些集合的交集将是您要查找的记录。

当然，如果您愿意，也可以减少索引的数量，因此(例如)您可以使用索引来获取一组具有正确的源和目标IP的记录，然后只需扫描该集合(可能相当小)即可获得具有正确端口号的记录。

Answer 2

我建议在公共字段上分别建立索引，然后使用合并连接策略来满足多个字段的查询。

您还可以使用(a，b，c)的索引来查询(a，b)或仅查询(a)，因此明智地选择索引可以避免合并连接的需要。

Answer 3

也许您可以应用kd-trees作为一种获得高效多键搜索的方法？我不能声称对你试图解决的具体问题有太多了解，但在询问关于多个键的搜索时，它似乎是适用的。