Comment by batmansmk

By GET, do you mean “get all fields of the unique item with id=x”? Oltp (sql), mongo or cassandra are working similarly for this and have the same complexity. Even worse, the same operation on the same storage can have very different performance profile independently of the cluster size, making o(n) complexity a very secondary discussion. All technologies offer more or less the same data structures and algorithms at such a basic level. You have to dig into replication, disk layout, transactionality, constraints, … to start to see differences.