3

我有一个数据集，它是前缀范围的列表，并且前缀的大小并不完全相同。这里有一些例子：

low: 54661601   high: 54661679   "bin": a
low: 526219100  high: 526219199  "bin": b
low: 4305870404 high: 4305870404 "bin": c

我想查找哪个“bin”对应于具有相应前缀的特定值。例如，值5466160179125211将对应于“bin”a。在重叠的情况下（其中很少），我们可以返回最长的前缀或所有前缀。

最佳算法显然是某种可以插入 bin 对象的树，其中树的每个连续级别代表越来越多的前缀。

问题是：我们如何在数据库中实现这一点（在一个查询中）？允许更改/添加到数据集。什么是最好的数据和查询设计？最好使用 mongo 或 MySQL 的答案。

4

4 回答 4

4

如果您对前缀范围内的重叠数量做出一个温和的假设，则可以使用 MongoDB 或 MySQL 以最佳方式执行您想要的操作。在下面的答案中，我将使用 MongoDB 进行说明，但是将这个答案移植到 MySQL 应该很容易。

首先，让我们重新表述一下这个问题。当您谈论匹配“前缀范围”时，我相信您实际上在谈论的是在字典顺序下找到正确的范围（直观地说，这只是字符串的自然字母顺序）。例如，前缀匹配 54661601 到 54661679 的数字集恰好是当写为字符串时，在字典上大于或等于“54661601”但在字典上小于“54661680”的数字集。因此，您应该做的第一件事是将所有上限加 1 ，这样您就可以用这种方式表达您的查询。在 mongo 中，您的文档看起来像

{low: "54661601", high: "54661680", bin: "a"}
{low: "526219100",  high: "526219200",  bin: "b"}
{low: "4305870404", high: "4305870405", bin: "c"}

现在问题变成了：给定一组 [ low , high )形式的一维区间，我们如何快速找到哪些区间包含给定点？最简单的方法是在低或高字段上使用索引。让我们使用高场。在 mongo 外壳中：

db.coll.ensureIndex({high : 1})

现在，让我们假设间隔根本不重叠。如果是这种情况，那么对于给定的查询点“x”，包含“x”的唯一可能区间是具有大于“x”的最小高值的区间。因此我们可以查询该文档并检查其低值是否也小于“x”。例如，这将打印出匹配间隔，如果有的话：

db.coll.find({high : {'$gt' : "5466160179125211"}}).sort({high : 1}).limit(1).forEach(
       function(doc){ if (doc.low <= "5466160179125211") printjson(doc) } 
  )

现在假设不是假设间隔根本不重叠，而是假设每个间隔与小于k个相邻间隔重叠（我不知道k的值对你来说是否正确，但希望它很小）。在这种情况下，您可以在上面的“限制”中将 1 替换为k，即

 db.coll.find({high : {'$gt' : "5466160179125211"}}).sort({high : 1}).limit(k).forEach(
       function(doc){ if (doc.low <= "5466160179125211") printjson(doc) } 
  )

这个算法的运行时间是多少？索引是使用 B-trees 存储的，因此如果您的数据集中有n 个区间，则需要 O(log n ) 时间来查找第一个匹配的高值文档，然后需要 O( k ) 时间来迭代下一个k文档，总共 O(log n + k ) 时间。如果k是常数，或者实际上小于 O(log n )，那么这是渐近最优的（这是在标准计算模型中；我没有计算外部存储器传输的数量或任何花哨的东西）。

唯一会发生故障的情况是k很大时，例如，如果某个大区间几乎包含所有其他区间。在这种情况下，运行时间为 O( n )。如果您的数据是这样的结构，那么您可能需要使用不同的方法。一种方法是使用 mongo 的“2d”索引，您的低值和高值编码x和y坐标。然后，您的查询将对应于查询x - y平面的给定区域中的点。这在实践中可能会做得很好，尽管使用当前的 2d 索引实现，最坏的情况仍然是 O(n)。

对于所有k值，有许多理论结果可以实现 O(log n ) 性能。它们的名称包括优先级搜索树、段树、间隔树等。但是，这些是您必须自己实现的专用数据结构。据我所知，目前没有流行的数据库实现它们。

于 2012-06-16T20:09:26.347 回答
0

佩顿！:)

如果您需要将所有内容保留为整数，并希望它与单个查询一起使用，则应该可以：

select bin from datatable where 5466160179125211 between 
      low*pow(10, floor(log10(5466160179125211))-floor(log10(low))) 
   and ((high+1)*pow(10, floor(log10(5466160179125211))-floor(log10(high)))-1);

在这种情况下，它将在数字 5466160100000000（具有低前缀的最小数字和与要查找的数字相同的位数）和 546616799999999（具有高前缀的最大数字和与该数字相同的位数）之间进行搜索找到）。在高前缀的位数多于低前缀的情况下，这仍然有效。它也应该在数字短于前缀长度的情况下工作（我认为），其中先前解决方案中的 varchar 代码可能会给出不正确的结果。

您需要进行实验来比较在查询中使用大量内联数学的性能（如在此解决方案中）与使用 varchars 的性能。

编辑：即使在没有索引的大表上，性能似乎也非常好；如果您可以使用 varchars，那么您可以通过索引低列和高列来进一步提高性能。请注意，如果任何前缀具有初始零，您肯定希望使用 varchars。这是一个修复，以允许在使用 varchars 时数字短于前缀的情况：

select * from datatable2 where '5466' between low and high
    and length('5466') >= length(high);
于 2012-06-15T19:40:54.390 回答
0

使用 MySQL，您可能必须使用存储过程，调用该存储过程将值映射到 bin。所述过程将查询每一行的桶列表并进行算术或字符串操作以找到匹配的桶。您可以通过使用固定长度的前缀来改进此设计，这些前缀排列在固定数量的层中。你可以为你的树分配一个固定的深度，每层都有一个表格。使用这些方法中的任何一种都不会获得类似树的性能。

如果你想做更复杂的事情，我怀疑你必须使用不同的平台。

Sql Server 有一个 Hierarchy 数据类型： http ://technet.microsoft.com/en-us/library/bb677173.aspx

PostgreSQL 有一个 cidr 数据类型。我不熟悉它的查询支持级别，但理论上你可以在你的数据库中构建一个路由表并使用它来分配存储桶： http ://www.postgresql.org/docs/7.4/static/ datatype-net-types.html#DATATYPE-CIDR

于 2012-06-15T16:22:37.667 回答
0

“最佳”对不同的人可能意味着不同的东西。似乎你可以做一些事情，比如将你的低值和高值保存为 varchars。那么你所要做的就是

select bin from datatable where '5466160179125211' between low and high

或者，如果您有某种理由将值保留为表中的整数，则可以在查询中进行 CAST。

我不知道这是否会给你一个大数据集带来糟糕的性能。我希望我明白你想做什么。

于 2012-06-15T17:04:40.643 回答