The first big difference is that key-value stores require the user to have the entire key for lookup, and can only be looked up by the key. Contrast that with relational databases which can typically be looked up by partial values of any column. This means a key-value store can create a hash of that key and use that hash to determine a precise node and disk location where the record is stored. Relational databases have a much more involved process to locate and retrieve a record, because of inherent extra complexity.
This single key also makes possible a single ordering on disk. Key-value stores typically keep a memory cache, an append-only commit log, then occasionally write out a more permanent compacted and sorted storage to disk. Relational databases don't have a single ordering that makes sense, so they can't take advantage of this optimization.
Most key-value stores also offer the ability to tune the consistency level, so if you have 3 replicas of each record, you can accept a write as complete after only 2 nodes have reported complete, for example, or even 1, if you like to live on the edge and the data isn't critical. All 3 replicas will be written eventually, but the client doesn't wait for it. This is called eventual consistency. Most relational databases maintain absolute consistency at all times, which keeps your data somewhat safer, but also costs speed.
Last but not least, since key-value stores can only be looked up by their keys, users end up trading storage space for speed. Where relational database users might do a join that is relatively slow to execute at query time, key-value users will have written redundant tables in parallel at write time, and can query just as fast as any other single-table query. For example, a relational join of a players
and location
table would end up as a query using a (player, location)
tuple for a key, with completely redundant records to a table containing just the player
key.
In summary, key-value stores accept limitations like requiring full keys for lookup, lack of joins, eventual consistency, and need for extra storage in exchange for greater speed.