使用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和日期过滤项目.如果项目都在同一级别,那将是一件容易的事,但诀窍在于它是递归的.EG:

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日"过滤,我们不仅必须看到节点中直接包含的项目与日期匹配,而且我们必须看到包含与日期匹配的项目的项目.

EG:我们在"第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外部库可能无法使用.

PS:我挖到了SO并发现了一些有趣的信息(特别是什么是将平面表解析成树的最有效/优雅的方法？).这是一个提示,但不是问题解决者.

Answer 1

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

在这个分析中,我正在做一些关于Android/Dalvik的一般性假设我真的不太了解,所以希望它有点准确:)记住G1有192MB的RAM.此外,您的上述假设最多约为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

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

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

3)如果您不想全部记忆,另一种可能的解决方案可能如下.Bill Karwin提出了一种相当优雅的RDBMS结构,称为Closure Table,用于优化基于树的读取,同时使写入更复杂.将它与顶级缓存相结合可能会给你带来性能上的好处,虽然我会在接受它之前测试它:

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

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