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