Short version: In a tree (non-binary) with many levels of children, where each node can have multiple leaves, what is the best way to tally leaves that meet a certain condition given a node?
Long, convoluted version: Say you have Folders, which can contain more Folders. In production, my system has about 15 layers of folders at the deepest. Each folder may have documents.
When a user navigates to a folder, they need to know how many documents are in that folder, total. They also need to know how many of those documents have been "flagged". Documents can be flagged if, after a certain time period, they have not been updated. This is determined based on history entries - take the last history entry for the folder, if it's bigger than X, then it's flagged.
Right now I'm iterating over all folders > subfolders > etc > children to check the history entry and tally recursively. This is getting pretty slow now so I need a new approach.
I've come up with two options but want to know if there's a better approach, or which one of these is best.
option 1: Whenever adding a document or removing a document, iterate up the parent graph and increment / decrement a "DocumentCount" property that's stored in the Folder entity. This means that adding / removing take a minimal performance hit. But the problem here is that I actually need to count total number of documents, as well as total number of documents that are flagged (by checking history entries), so that means that I'll need another field and another process to call when this status changes. This introduces even more complexity as checking whether or not something is flagged is a method call, not a property.
option 2: Have a timer job run through and update the "documentCount" and "unopenedDocumentCount" properties of each folder in the system, would be lots of CPU cycles and seems wasteful.
option 3: Just thought of this - maybe iterating over every document and seeing if the document is a direct or distant child of the target node before evaluating would be better than iterating via recursion. I feel like this would be better for nodes high-up in the tree, but iterating over every child for a low-level node would be ridiculous. Hmmm...
I'm tempted to implement option 1.. what other options are there?