qwertie
Accessing an index in O(log n) time?
This library is incredibly robust! I was surprised to find, though, that I don't seem to have any way to access elements by their sorted-order index without invoking ToArray (which iterates over the entire tree to build an array.) Is this possible with the current implementation? Or a feature planned for any point in the future?
In the past I've created B+ trees in C# with such functionality, but I don't currently have plans to add it to this one.
I should say, there was recently a feature added to embed the total size in each internal node, which is nice because that feature is a prerequisite that would make it possible to look up the Nth pair in log(size) time.
So this is something doable by forking the project & writing a function to search downwards through the size() properties of each child, but not possible in the current project at base? Just clarifying! I haven't read through the entire implementation, just want to be sure i'm on the right track.
Or I guess you could just get key [i] of _root.keys, and do a typical tree search for that key's pair...
A PR for this would be accepted if it includes tests. You would do a scan in each internal node to find which child must contain item [i], then recurse to find item [i - offset] in children[c] where offset is the sum of sizes of children[0...c-1].