Lookup isn't a problem, the cache using the internal tcl hash functionality.
I'm sure its a bucket hash, but done well bucket hashes perform very well, and it's used everywhere in Tcl so I assume a lot of attention's been paid to making it very fast.
Look into the db-* caching I added back in 5.2 or so, originally developed for greenpeace. It's a bit more straightforward to use for simple caching from the database.
I use it exclusively these days.
What *is* slowish is deleting anything from ns_cache, because you have to loop through entries. But deletion is much, much less frequent that referencing the information, more or less by definition (don't cache things that aren't referenced frequently!)