Data structure for indexed searches of subsets

I'm working on a c# jquery implementation and am trying to figure out an efficient algorithm for locating elements in a subset of the entire DOM (e.g. a subselector). At present I am creating an index of common selectors: class, id, and tag when the DOM is built.

The basic data structure is as one would expect, a tree of Elements which contain IEnumerable<Element> Children and a Parent. This is simple when searching the whole domain using a Dictonary<string,HashSet<Element>> to store the index.

I have not been able to get my head around the most effective way to search subsets of elements using an index. I use the term "subset" to refer to the starting set from which a subsequent selector in a chain will be run against. The following are methods I've thought of:

1. Retrieve matches from entire DOM for a subquery, and eliminate those that are not part of the subset. This requires traversing up the parents of each match until the root is found (and it is eliminated) or a member of the subset is found (and it is a child, hence included)
2. Maintain the index separately for each element.
3. Maintain a set of parents for each element (to make #1 fast by eliminating traversal)
4. Rebuild the entire index for each subquery.
5. Just search manually except for primary selectors.

The cost of each possible technique depends greatly on the exact operation being done. #1 is probably pretty good most of the time, since most of the time when you do a sub-select, you're targeting specific elements. The number of iterations required would be the number of results * the average depth of each element.

The 2nd method would be by far the fastest for selecting, but at the expense of storage requirements that increase exponentially with depth, and difficult index maintenance. I've pretty much eliminated this.

The 3rd method has a fairly bad memory footprint (though much better than #2) - it may be reasonable, but in addition to the storage requirements, adding and removing elements becomes substantially more expensive and complicated.

The 4rd method requires traversing the entire selection anyway so it seems pointless since most subqueries are only going to be run once. It would only be beneficial if a subequery was expected to be repeated. (Alternatively, I could just do this while traversing a subset anyway - except some selectors don't require searching the whole subdomain, e.g. ID and position selectors).

The 5th method will be fine for limited subsets, but much worse than the 1st method for subsets that are much of the DOM.

Any thoughts or other ideas about how best to accomplish this? I could do some hybrid of #1 and #4 by guessing which is more efficient given the size of the subset being searched vs. the size of the DOM but this is pretty fuzzy and I'd rather find some universal solution. Right now I am just using #4 (only full-DOM queries use the index) which is fine, but really bad if you decided to do something like $('body').Find('#id')

Disclaimer: This is early optimization. I don't have a bottleneck that needs solving, but as an academic problem I can't stop thinking about it...

Solution

Here's the implementation for the data structure as proposed by the answer. Is working perfectly as a near drop-in replacement for a dictionary.

interface IRangeSortedDictionary<TValue>: IDictionary<string, TValue>
{
    IEnumerable<string> GetRangeKeys(string subKey);
    IEnumerable<TValue> GetRange(string subKey);

}
public class RangeSortedDictionary<TValue> : IRangeSortedDictionary<TValue>
{
    protected SortedSet<string> Keys = new SortedSet<string>();
    protected Dictionary<string,TValue> Index = 
        new Dictionary<string,TValue>();
    public IEnumerable<string> GetRangeKeys(string subkey)
    {
        if (string.IsNullOrEmpty(subkey)) {
            yield break;
        }
        // create the next possible string match
        string lastKey = subkey.Substring(开发者_开发百科0,subkey.Length - 1) +
            Convert.ToChar(Convert.ToInt32(subkey[subkey.Length - 1]) + 1);

        foreach (var key in Keys.GetViewBetween(subkey, lastKey))
        {
            // GetViewBetween is inclusive, exclude the last key just in case
            // there's one with the next value
            if (key != lastKey)
            {
                yield return key;
            }
        }
    }

    public IEnumerable<TValue> GetRange(string subKey)
    {
        foreach (var key in GetRangeKeys(subKey))
        {
            yield return Index[key];
        }
    }
    // implement dictionary interface against internal collections
}

Code is here: http://ideone.com/UIp9R

---

If you suspect name collisions will be uncommon, it may be fast enough to just walk up the tree.

If collisions are common though, it might be faster to use a data structure that excels at ordered prefix searches, such as a tree. Your various subsets make up the prefix. Your index keys would then include both selectors and total paths.

For the DOM:

<path>
  <to>
    <element id="someid" class="someclass" someattribute="1"/>
  </to>
</path>

You would have the following index keys:

<element>/path/to/element
#someid>/path/to/element
.someclass>/path/to/element
@someattribute>/path/to/element

Now if you search these keys based on prefix, you can limit the query to any subset you want:

<element>           ; finds all <element>, regardless of path
.someclass>         ; finds all .someclass, regardless of path
.someclass>/path    ; finds all .someclass that exist in the subset /path
.someclass>/path/to ; finds all .someclass that exist in the subset /path/to
#id>/body           ; finds all #id that exist in the subset /body

A tree can find the lower bound (the first element >= to your search value) in O(log n), and because it is ordered from there you simply iterate until you come to a key that no longer matches the prefix. It will be very fast!

.NET doesn't have a suitable tree structure (it has SortedDictionary but that unfortunately doesn't expose the required LowerBound method), so you'll need to either write your own or use an existing third party one. The excellent C5 Generic Collection Library features trees with suitable Range methods.