O(log n) tree search vs. O(1) hash lookup is not the reason for any scalability differences that might exist between RDBMS and key-value stores. RDBMSs with has

O(log n) tree search vs. O(1) hash lookup is not the reason for any scalability differences that might exist between RDBMS and key-value stores. RDBMSs with hash indexes are commonplace, and allow O(1) lookups and a b+-tree lookup over a few million rows only does a few I/Os (the fanout in a typical disk-based tree index is on the order of 100, and the nodes in the first level or two of the tree are likely to be cached). Any differences in scalability has more to do with architectural differences (easier to do horizontal partitioning with key-value stores, no need/expectation of ACID transactions, no need to parse + optimize queries at runtime, no need for a complex query executor, etc.) But I agree that a SQL RDBMS allows much more flexible ad-hoc queries than a key-value store does.