One interesting feature that was added in the latest drop is the support for accessing OrderedSet and OrderedBag by integer index. Recall that OrderedSet and OrderedBag maintain all the items in order, where order is defined by an IComparer or Comparison. When you could always iterate over the items in order, you can now get at any item by its integer index in the order. This operation takes time O(log N). You can also go this other way; you get do an IndexOf operation on an item to get its index in O(log N) time also.

The implementation of this is primary in the RedBlackTree class, and it's a little bit interesting and tricky. Each node in the tree stores the number of items in that sub-tree. As items as added or deleted, the counts are updated. One annoying part has to do with adds and deletes that don't complete as expected. For example, consider that operation of deleting an item. As we go down the tree searching for the item to delete, we update the counts in the nodes to reflect the deletion. However, if the item to delete is not found, we have to restore those counts back to where they were. This means that we have to keep a record of what counts were updated, so that they can be restored.