使用Java和SQLite的递归数据处理性能

Question

如果您的答案与Java / SQLite无关，我很乐意阅读它。

环境

我使用以下方案将项目存储在数据库中：

###################
#       Item      #    
###################
#      _id        #    This is the primary key
#    parent_id    #    If set, it the ID of the item containing this item
#      date       #    An ordinary date
#  geocontext_id  #    Foreign key to a pair of named coordinates
###################

###################
#   Geocontext    #    
###################
#       _id       #    This is the primary key
#       name      #    Way for the user to label a pair of coordinates (e.g : "home", "work")
#         x       #    One of the coordinate
#         y       #    The other one
###################

问题

我必须根据geocontext和日期过滤项目。如果项目都在同一级别，那将是一件容易的事，但诀窍在于它是递归的。 E.G：

root
      |_item 1
      |_item 2 
      |      |_item 4
      |      |_item 5
      |             |_item 6
      |_item 3
      |      |_item 8
      |             |_item 10
      |_item 11
      |       |_item 12
      |_item 7

递归深度没有明确的限制。

现在，如果我们在任何节点并使用日期“4月1日”进行过滤，我们不仅必须看到节点中直接包含的与日期匹配的项目，而且我们必须看到包含与日期匹配的项目的项目。

E.G：我们在“第2项”中，如果“第6项”与日期匹配，那么我们认为“第5项”也与日期相符，我们必须保留它。如果我们在根，则必须显示第2项。

geocontext也是如此，但它更难，因为：

• 它存储在另一个表中。
• 匹配上下文是一项代价高昂的数学计算。

当然，强制匹配的暴力会导致软件变慢并且用户体验非常差。

注意：我不需要显示树。我显示了树中过滤数据的列表。我们必须只看到顶级元素的平面列表。根据所有孩子的层次结构，挑战在于决定是否显示每个元素。

我是怎么试图解决它的

我以为我可以通过使用更多表来缓存平面数据来缓解一些问题：

###################
# Geocontex_cache #    
###################
#     item_id     #     I can Join the items table on this field
#     child_id    #     I can delete / update a child, and so delete / update the cache
#  geocontext_id  #     I can delete / update a geocontext, and so delete / update the cache
#        x        #      Here, I can brute force :-)
#        y        # 
###################

###################
#    Date_cache   #    
###################
#     item_id     #     
#     child_id    #    
#       date      #    
###################

这似乎是合理的，但我还没有尝试过。不过，它应该有以下缺点：

• 我将昂贵的流程转移到了必须管理缓存日期的get / set / create / delete方法。这将是一个麻烦的编写和维护代码。一个五个深度级别的项目将分解一个过程，该过程将递归地击中五个父母。
• 数据库的大小可能变得巨大。五个深度级项目存储五个父项的缓存数据。不知道它是否相关，因为这是一个带有手动输入的单用户应用程序。我认为任何人都不会插入超过10个深度的1000个项目。

现在好消息是我们从金字塔的底部走到顶端，而不是其他方式，所以它看起来并不可怕。当我必须处理父项删除时，这将是另一个很好的头痛，但我将其保存为另一个问题;-)。

现在我的问题

您将如何以最佳方式存储数据并处理过滤？

可选的 ：

我应该定义一个明确的递归深度限制吗？我应该使用SQL还是Java执行过滤？ SQL肯定会更快，但在Java中更容易匹配geocontext。

当我在Android平台上工作时，我有以下约束：

• Java是唯一可用的语言，而不是整个标准库。
• SQLite是唯一可用的DBMS。
• 性能和内存是重要的问题。如果您必须选择，电池寿命和性能是首要任务。
• Exotics外部库可能无法使用。

P.S：我挖到了SO并发现了一些有趣的信息（尤其是qazxsw opi）。这是一个提示，但不是问题解决者。

Answer 1

1）首先，让我们看看简单地将所有内容都放在内存中。这是简单，灵活，最重要的是快速解决方案。缺点包括你必须在启动时将所有内容读入内存（给用户一个漂亮的加载栏，他们甚至都不会注意到），并且可能需要做一些额外的工作来确保一切都反映到磁盘上用户认为它是，所以数据不会丢失。

在这个分析中，我正在做一些关于Android / Dalvik的一般性假设我真的不太了解，所以希望它有点准确:)记住G1有192MB的RAM。此外，您的上述假设最多约为1000项。

What is the most efficient/elegant way to parse a flat table into a tree?

注意：我意识到虽然一个孩子只能有一个指针，但父母可以有多个孩子。但是，parent-> child指针的数量是（elements-1），所以parent-> child指针的平均成本是（elements-1）/ elements~1个元素或4个字节。这假定子结构不分配未使用的内存，例如LinkedList（而不是ArrayList）

2）我的书呆子说这对于剖析B +树来说是一个有趣的地方，但我认为这对你现在想要的东西来说太过分了:)但是，无论你最终采用什么解决方案，如果你没有拿到所有东西在内存中，您肯定希望尽可能多地在内存中缓存树的顶层。这可能会大幅减少磁盘活动量。

3）如果您不想全部记忆，另一种可能的解决方案可能如下。 Bill Karwin建议使用相当优雅的

Object superclass ~ 8 bytes
parent/child pointer ~ 4 bytes
date (long) ~ 8 bytes
name (non interned string avg 32 chars) ~ 64 bytes
x point (int) ~ 4 bytes
y point (int) ~ 4 bytes

Total = 92 bytes + possible memory alignment + fudge factor = 128 bytes
1000 items = 125kB
10000 items = 1.22MB

来优化基于树的读取，同时使写入更复杂。将它与顶级缓存相结合可能会给你带来性能上的好处，虽然我会在接受它之前测试它：

在评估视图时，使用内存中的任何内容来评估尽可能多的孩子。对于那些不匹配的子节点，使用闭包表和平面表之间的SQL连接以及相应的where子句来查找是否存在任何匹配的子节点。如果是这样，您将在结果列表中显示该节点。

希望这一切都有意义，似乎它可以满足您的需求。

Answer 2

我听了Soonil并尝试了“封闭表”。我添加了下表：

RDBMS structure called a Closure Table

如果像我一样，你以前从未使用过那个模型，那就是这样：

您为层次结构中的每个直接或间接关系添加一行。如果C是B的孩子，而B是A的孩子，那么你有：

################
#   Closure    #
################
# ancestor_id  #
#   item_id    #
################

然而，通过这种方案，您缺少一个重要信息：直接关系是什么？如果您只想要项目的直接孩子怎么办？

为此，您可以在闭包表中添加一个带有bool的列

ancestor    item
   B         C
   A         B
   A         C      # you add the indirect relationship   
   A         A
   B         B
   C         C      # don't forget any item is in relation with himself 

，或者您可以将列is_direct保留在parent_id表中。这就是我做的，因为它阻止我重写我以前的很多代码。

好的部分是我现在可以在一个查询中检查项目是否与日期或地理文本匹配。

E.G，如果我正在浏览项目编号4中包含的所有项目，并且只想获得匹配或包含与日期D匹配的子项的项目：

item

所以我可以扔掉所有的

SELECT ti.parent_id, ti.id, ti.title 
FROM item AS di                                  # item to filter with the date
              JOIN closure AS c                  # closure table
                  ON (di.id = c.item_id) 
              JOIN item AS ti 
                  ON (c.ancestor_id = ti.id)     # top item to display
WHERE di.date = D                                # here you filter by date   
AND ti.parent_id = 4                             # here you ensure you got only the top items

表。我还有很多工作要做一个UPDATE / DELETE / CREATE，但是一切都是集中的，大多数是程序性的，而不是递归的。很酷。

唯一的痛苦是我必须递归地向其所有祖先添加一个项目。但是获得祖先是一个查询镜头，所以这是非常合理的。当然封闭表占用了很多空间，但在我的情况下我只是不在乎。如果你正在寻找穿孔，别忘了索引它...

喜欢这个SQL技巧，非常感谢！第一眼看起来有点棘手，但是一旦完成它就会很明显。

Answer 3

这可能是offtopic但是..你考虑过使用序列化吗？

Google协议缓冲区可用于以非常有效的方式（时间和空间）序列化数据，然后您必须创建合适的树结构（查看任何CS书籍）以帮助进行搜索。

我提到了协议缓冲区，因为它们可能是Android上的Google库。

只是一个想法。

Answer 4

AFAICT你可以在SQLite中使用分层查询（google为“CONNECT BY”“START WITH”）...