草庐IT

mysql - 用于前缀搜索的最佳数据库查询

coder 2023-10-19 原文

我有一个数据集，它是一个前缀范围列表，并且前缀的大小不尽相同。下面是几个例子:

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 的答案。

最佳答案

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

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

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

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

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

现在，我们假设间隔根本不重叠。如果是这种情况，那么对于给定的查询点“x”，包含“x”的唯一可能区间是具有大于“x”的最小 high 值的区间。因此我们可以查询该文档并检查其 low 值是否也小于“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 树存储，因此如果您的数据集中有 n 个间隔，则需要 O(log n) 时间来查找第一个匹配的文档 < strong="">high 值，然后 O(k) 时间迭代下一个 k 文档，总共 O(log n + k) 时间。如果 k 是常数，或者实际上小于 O(log n)，那么这是渐近最优的(这是在标准计算模型中；我不是计算外部存储器传输的数量或任何花哨的东西)。

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

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

关于mysql - 用于前缀搜索的最佳数据库查询，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11053512/

mysql用于strongemhighalgorithmmongodbtreeprefix

有关mysql - 用于前缀搜索的最佳数据库查询的更多相关文章

  1. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

  2. ruby - ECONNRESET (Whois::ConnectionError) - 尝试在 Ruby 中查询 Whois 时出错 - 2

    我正在用Ruby编写一个简单的程序来检查域列表是否被占用。基本上它循环遍历列表，并使用以下函数进行检查。require'rubygems'require'whois'defcheck_domain(domain)c=Whois::Client.newc.query("google.com").available?end程序不断出错(即使我在google.com中进行硬编码)，并打印以下消息。鉴于该程序非常简单，我已经没有什么想法了-有什么建议吗？/Library/Ruby/Gems/1.8/gems/whois-2.0.2/lib/whois/server/adapters/base.

  3. ruby-on-rails - Rails 常用字符串(用于通知和错误信息等) - 2

    大约一年前，我决定确保每个包含非唯一文本的Flash通知都将从模块中的方法中获取文本。我这样做的最初原因是为了避免一遍又一遍地输入相同的字符串。如果我想更改措辞，我可以在一个地方轻松完成，而且一遍又一遍地重复同一件事而出现拼写错误的可能性也会降低。我最终得到的是这样的:moduleMessagesdefformat_error_messages(errors)errors.map{|attribute,message|"Error:#{attribute.to_s.titleize}#{message}."}enddeferror_message_could_not_find(obje

  4. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  5. ruby-on-rails - 在 Rails 和 ActiveRecord 中查询时忽略某些字段 - 2

    我知道我可以指定某些字段来使用pluck查询数据库。ids=Item.where('due_at但是我想知道，是否有一种方法可以指定我想避免从数据库查询的某些字段。某种反拔？posts=Post.where(published:true).do_not_lookup(:enormous_field) 最佳答案 Model#attribute_names应该返回列/属性数组。您可以排除其中一些并传递给pluck或select方法。像这样:posts=Post.where(published:true).select(Post.attr

  6. Ruby Sinatra 配置用于生产和开发 - 2

    我已经在Sinatra上创建了应用程序，它代表了一个简单的API。我想在生产和开发上进行部署。我想在部署时选择，是开发还是生产，一些方法的逻辑应该改变，这取决于部署类型。是否有任何想法，如何完成以及解决此问题的一些示例。例子:我有代码get'/api/test'doreturn"Itisdev"end但是在部署到生产环境之后我想在运行/api/test之后看到ItisPROD如何实现？ 最佳答案 根据SinatraDocumentation:EnvironmentscanbesetthroughtheRACK_ENVenvironm

  7. ruby - Ruby 有 `Pair` 数据类型吗？ - 2

    有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳

  8. ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2

    我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll

  9. ruby - inverse_of 是否适用于 has_many？ - 2

    当我使用has_one时，它​​工作得很好，但在has_many上却不行。在这里您可以看到object_id不同，因为它运行了另一个SQL来再次获取它。ruby-1.9.2-p290:001>e=Employee.create(name:'rafael',active:false)ruby-1.9.2-p290:002>b=Badge.create(number:1,employee:e)ruby-1.9.2-p290:003>a=Address.create(street:"123MarketSt",city:"SanDiego",employee:e)ruby-1.9.2-p290

  10. ruby - 我如何添加二进制数据来遏制 POST - 2

    我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_

随机推荐