If you just need a key-value data concurrent data structure it should be much faster and scale better to have a hash map instead of something that is keeping a sorted order.
So just use a DBMS, but if you don't want, perhaps this ordered concurrent map.
You said you were using it for a "key-value store". If all you need is a key value lookup, all you need is a hash map.
When it comes to concurrency the difference is even more pronounced because hash maps can have lots of concurrent IO due to working on different parts of memory that are mostly independent of each other while a sorted data structure is going to have to move things around, which means more atomic swapping, which means more chances for collisions or race conditions where other threads are going to have to retry their compare and swaps or back off and try parts of their operation again.