在 XML 中存储具有 co-indexed 个节点的树的最有效和高效的方法

Question

我正在接手我的一个旧项目，其中有效性和效率是关键。我解析了 100 GB 的 XML 数据。对于每棵 XML 树（数百万棵），使用一些 XML 属性从中扣除模式。不过，对于这个问题，我将大大简化事情——但重要的是要记住，有大量数据和快速处理，以及 [=83] 中结果的整齐存储=] 很重要。此外，还需要遍历生成的 XML 树。事实上，它将用作 BaseX 中使用的自定义索引机制，但稍后我会回过头来。

从每棵树（及其子树，但现在这并不重要）创建一个基于根节点直接 children 的模式。作为一个基本示例，采用以下 XML 树：

<node letter="X">
  <node letter="A"/>
  <node letter="B"/>
  <node letter="C"/>
  <node letter="D"/>
</node>

该模式是通过获取所有 children 的字母属性并对它们进行排序和连接来创建的。在这种情况下，模式将为 ABCD.

对于每棵树，也会生成所有可能的子树（顺序不重要，最少组合 2），即 children 的所有可能组合，并生成它们的模式。我不包括组合树的 XML，但是除了 ABCD 之外，可能的模式将是：

AB
ABC
ABD
AC
ACD
AD
BC
BCD
BD
CD

在层次结构中，它们看起来像这样（注意终端节点中的重复）。

此外，我们开始的完整模式应该以某种方式在生成的 XML 中指示，以指示它是树中的 'main' 模式。最终，我想恢复从给定模式派生的所有模式（稍后参见）并将它们过滤为仅 'main' 模式。

从查询的角度来看，您可以argue that I am doing a bottom-up look-up. If I am looking for a generalized pattern, e.g. AB, the more specific patterns should also be found becauseABis part ofABCD。所以如果我要用上面的数据寻找模式 AB，我想找到

ABCD
ABC
ABD

这里分两步可能就清楚了。首先，概括一个级别：AB -> ABC,ABD，然后是 ABC->ABCD（然后再次 ABD->ABDC，但每个结果当然只能找到一次）。中间步骤 ABC 和 ABD 对我来说也很重要，不仅仅是最终的 ABCD 结果。

我面临的问题是如何有效地存储一棵树，例如图像中显示的树，以便 1. 以我讨论的方式易于查询； 2. 在不丢失任何节点的情况下尽可能稀疏； 3.高效构建。后一点对于这个问题不太重要，因为我将自己实现构建脚本——这将在 Python 3.6.

中完成

到目前为止，我的想法是拥有一个由 'coindexing' 直接 parent 节点工作的相当扁平的结构。它看起来像这样：

<tree>
  <node pattern="AB" index="1">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="8"/> <!-- ABD -->
  </node>
  <node pattern="AC" index="2">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="9"/> <!-- ACD-->
  </node>
  <node pattern="AD" index="3">
    <parentnode coindex="8"/> <!-- ABD -->
    <parentnode coindex="9"/> <!-- ACD -->
  </node>
  <node pattern="BC" index="4">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="BD" index="5">    
      <parentnode coindex="8"/> <!-- ABD -->
      <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="CD" index="6">    
      <parentnode coindex="9"/> <!-- ACD -->
      <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="ABC" index="7">    
    <parentnode coindex="11"/> <!-- ABCD -->
  </node>
  <node pattern="ABD" index="8">    
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="ACD" index="9">   
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="BCD" index="10">    
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="ABCD" index="11" isMain="true"/>
</tree>

通过这样做，我想可以得到所有链接在一起的模式。例如，如果我现在要寻找 AB，我希望到达那个节点 children (parentnode) 并获取这些索引并使用它们来寻找直接的 parent秒。然后应该重复该过程，直到没有元素留下 coindex（例如 ABCD 在这种情况下）。

想象一下，像这样的 XML 个元素有数千个，主要的元素用 isMain 表示。注意isMain不一定是没有parent节点children的模式！结果是 all 原始 XML 树的累积。这意味着在某些情况下，一种模式可能是主要模式，而在其他情况下，它可能是组合的一部分。在这种情况下 node 是表示 isMain 因为在原来的 XML 中有 'some tree that has this pattern as its main pattern'.

到目前为止，这只是我的想法，但我不确定是否有更好的方法，或者更重要的是，是否可以在 BaseX 中轻松查询。基本上对于给定的输入 AB 我想通过使用索引检索所有相关的 patterns (ABC, ABD, ABCD) 然后通过只检索 [=35] 的那个来过滤这些结果=].我期待看到更好的想法，以及在 BaseX 中查询它们的方法。如果我的想法不错，那么我希望看到一种在单个 xquery 表达式中捕获查询的好方法。

Answer 1

我不太明白你想通过将分层数据放入平面结构而不是仍然使用高效的 XML 处理器 BaseX 来实现什么。

我认为将数据放入它已经表示的逻辑结构中并使用索引来有效地查询数据会更自然（也更快）。

因此您只需按原样使用层次结构，例如：

<tree>
    <node pattern="ABCD">
      <node pattern="ABC">
        <node pattern="AB"/>
        <node pattern="AC"/>
        <node pattern="BC"/>
      </node>
      <node pattern="ABD">
        <node pattern="AB"/>
        <node pattern="AD"/>
        <node pattern="BD"/>
      </node>
    </node>
</tree>

所以，我猜您选择该格式是出于性能原因。但是当你建立你的数据库时，你应该创建一个属性索引，即你所有的属性值都将被索引。通常，对于更常用的查询，应该重写它，但您可以直接使用属性索引。例如，我有一个 50GB 以上的数据库，其中包含英语维基百科的转储。比如我选择搜索一个页面List of Dragon Ball characters:

db:attribute("wikipedia", "List of Dragon Ball characters")/parent::*

这在我的机器上执行大约需要 20 毫秒。

所以类似地，您可以简单地搜索模式并上树：

db:attribute("<YOUR_DB>", "AB")/ancestor::node/@pattern => distinct-values()

考虑到您首先使用索引，然后简单地访问父级，这应该会尽可能快。

在 XML 中存储具有 co-indexed 个节点的树的最有效和高效的方法

Most effective and efficient way to store tree with co-indexed nodes in XML

xml

database

performance

xml-database

basex