Good snapshottable data structure for an in-memory index
Use any kind of persistent/immutable (i.e., functional) tree-based data structure.  The key is getting the locking right, as @Raphael pointed out in the comments.

The nice thing about functional/persistent tree-based data structures, is that you get "snapshots" for free.  Let's suppose you use a treap (randomized binary search tree) for your data structure.  Here's an example of one written in Go: https://github.com/steveyen/gtreap.  The author describes it thusly:


  By immutable, any updates/deletes to a treap will return a new treap which can share internal nodes with the previous treap. All nodes in this implementation are read-only after their creation. This allows concurrent readers to operate safely with concurrent writers as modifications only create new data structures and never modify existing data structures. This is a simple approach to achieving MVCC or multi-version concurrency control.


At any point in time the "current" state of the tree is represented by a pointer to the root of the tree.  Insertions are non-mutating.  Instead an insertion keeps the previous version of the tree completely intact, creates $O(\log n)$ new nodes for the path from the root to the correct insertion point, with pointers back to the nodes of the previous version that can be shared.

You use a lock to protect the pointer to the root.  Since the data structure is immutable reads can be done concurrently, and you can save pointers to old snapshots.  A read is:

lock
tmp = ptr_to_root
unlock
value = search(tmp, &lt;value to search for&gt;)
return value


Even though the search may take a while, you only hold the lock while copying the pointer, so the searches can happen concurrently.

A write is:

lock
old_ptr_to_root = ptr_to_root
ptr_to_root = insert(old_ptr_to_root, &lt;new key/value pair&gt;)
unlock


In this version, writes do need to hold the lock during the entire process of creating the new version of the tree.  You can improve read performance (at the cost of sometimes having the write transaction fail) by changing the write to something like this:

top:
  lock
  old_ptr_to_root = ptr_to_root
  unlock
  new_ptr_to_root = insert(old_ptr_to_root, &lt;new key/value pair&gt;)
  lock
  if (ptr_to_root == old_ptr_to_root)   # make sure no other write happened in the interim
    ptr_to_root = new_ptr_to_root
    unlock
  else                                  # transaction fails, try again
    unlock
    goto top


You may be able to do even slightly better (make it "lock free") if your programming language has atomic variables with an atomic compare-and-swap operation.  (For example by using C++11's atomic&lt;T*&gt;.)