We currently iterate over the entire shard when searching for a key. We could so a binary search instead to speed it up.