Is it possible to implement a dictionary with efficient access according to insertion order?
To summarize, this is what you require:


a dictionary that 
offers find, add and delete in $O(\log n)$ time and also
GetByIndex, KeyByIndex and IndexByKey in $O(\log n)$ time, where the index is determined by insertion order.


The first part is easy: use any balanced search tree. Say we use AVL trees.

For the second, we can use a second tree but use an increasing counter as key. With a small change to the data structure, we can find the $i$th element in $O(\log n)$ time (rank selection). Thus, we don't have to change any indices; the tree structure maintains the order for us.

We can further link the two AVL trees back and forth.

Assuming we have an implementation AVL which provides efficient select and rank (zero-based) and has a field for crosslinks, this would be rough pseudocode:

class IndexedDictionary {
  dataTree  = new AVL()
  indexTree = new AVL()
  nextId = 0

  add(key, data) {
    dataNode  = dataTree.add(key, data)
    indexNode = indexTree.add(nextId, data)
    dataNode.crosslink = indexNode
    indexNode.crosslink = dataNode
    nextId += 1
  }

  delete(key) {
    i = index(key)
    dataTree.delete(key)
    indexTree.delete(indexTree.select(i).key)
  }

  find(key) {
    return dataTree.find(key).value
  }

  get(index) {
    return indexTree.select(index).value
  }

  key(index) {
    return indexTree.select(index).crosslink.key
  }

  index(key) {
    return indexTree.rank(dataNode.find(key).crosslink.key)
  }
}


Of course, delete(index) can be implemented similarly to delete(key). Delete can be implemented faster if you add an operation delete-ith to AVL, and have AVL-delete return the removed node.