Are you just reading from this data structure? If so I wouldn't do any locking or threading, I'd just use asyncio to serve up read requests to the data and it should scale quite well. Multithreading/processing is best for CPU limited workloads but this sounds like you're really just IO-bound (limited by the very high IO of reading from that data structure in memory).
If you're allowing writes to the shared data structure... I'd ask myself am I using the right tool for the job. A proper database server like postgres will handle concurrent writers much, much better than you could code up hastily. And it will handle failures, backups, storage, security, configuration, etc. far better than an ad hoc solution.
Reading from memory is really not IO. Perhaps you're suggesting doing something like mmapping a file to memory, putting the data structure in that memory, and then using asyncio on the file to serve things, but this would only work if you can compute byte ranges inside the file to serve ahead of time, in which case there are much simpler solutions anyway. Most likely, when receiving a query they need to actually search through the datastructure based on the query, and it's very likely that this is the bottleneck, not just reading some memory.
If you're allowing writes to the shared data structure... I'd ask myself am I using the right tool for the job. A proper database server like postgres will handle concurrent writers much, much better than you could code up hastily. And it will handle failures, backups, storage, security, configuration, etc. far better than an ad hoc solution.