如果您的答案与 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
###################

问题

我必须根据地理上下文和日期过滤项目。如果项目都在同一级别，这将是一件容易的工作，但诀窍在于它是递归的。例如:

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 项。

地理环境也是如此，但更难，因为:

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

当然，强制匹配会导致软件运行缓慢，用户体验非常差。

注意:我不需要显示一棵树。我显示从树中过滤的数据列表。我们必须只看到顶部元素的平面列表。挑战是根据所有子层次结构决定是否显示每个元素。

我是如何尝试解决的

我想我可以通过使用更多的表来缓存平面数据来缓解这个问题:

###################
# 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 /设置/创建/删除方法 将不得不管理缓存的日期。 这将是一个麻烦的代码 编写和维护。五深 级别项目将触发一个过程 将递归地命中五个 parent 。

• 数据库的大小可以 变得巨大。五个深度级别 项目存储缓存数据为五个 parent 。不知道有没有关系 因为这是一个单用户应用程序 手动输入。我不认为任何人 将插入超过 1000 个项目 深度超过 10 级。

现在好消息是我们从 金字塔底部到顶部，不是 另一种方式，所以它没有 看起来很可怕。我什么时候会 必须处理父项 删掉，又是一个美好 头疼，但我把它留给另一个 问题;-).

现在我的问题

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

可选:

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

由于我在 Android 平台上工作，我有以下限制:

• Java 是唯一可用的语言， 而不是整个标准库。

• SQLite 是唯一可用的 DBMS。

• 性能和内存很重要 问题。如果你不得不选择， 电池生命周期，因此 性能优先。

• Exotics 外部库可能无法 将被使用。

P.S:我深入研究了 SO 并发现了一些有趣的信息(特别是 What is the most efficient/elegant way to parse a flat table into a tree?)。这是一个提示，但不是解决问题的方法。

最佳答案

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

在这个分析中，我对 Android/Dalvik 做了一些一般性假设，我不太了解，所以希望它是准确的 :) 请记住 G1 有 192MB 的内存。此外，您上面的假设是最多约 1000 个项目。

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

注意:我意识到虽然一个 child 只能有一个指针，但一个 parent 可以有多个 child 。但是，parent->child 指针的个数是 (elements - 1)，所以 parent->child 指针的平均成本是 (elements - 1)/elements ~ 1 个元素或 4 个字节。这假设子结构不分配未使用的内存，例如 LinkedList(与 ArrayList 相对)

2) 我的 Nerd 说这是一个分析 B+ 树的有趣地方，但我认为这对你目前想要的东西来说太过分了:)然而，无论你结束什么解决方案在采用时，如果您没有将所有内容都保存在内存中，您肯定会希望尽可能多地在内存中缓存树的顶层。这可能会大大减少磁盘 Activity 量。

3) 如果您不想占用所有内存，另一种可能的解决方案如下。 Bill Karwin 建议一个相当优雅的 RDBMS structure called a Closure Table用于优化基于树的读取，同时使写入更加复杂。将其与顶级缓存相结合可能会给您带来性能优势，尽管我会在接受我的 promise 之前对此进行测试:

在评估一个 View 时，使用你内存中的任何东西来评估尽可能多的 child 。对于那些不匹配的子项，使用闭包表和平面表之间的 SQL 连接以及适当的 where 子句来查明是否有任何匹配的子项。如果是这样，您将在结果列表中显示该节点。

希望这一切都有意义，并且看起来它能满足您的需求。

关于java - 使用 Java 和 SQLite 的递归数据处理性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/716857/