Hacker News Reader

Comment by tonymet | Hacker News Reader

I thought the point of nosql was O(1) GET and UPDATE operations

I think you are thinking "hashmaps", not nosql. There are some ways of persisting hash maps to disk [1], but the workhorse of most ACID DBs (including popular nosql DBs like mongo) are B-Trees, which have O(log n) complexity for all operations.

In any case when working with JSON columns in SQL it is useful to index the documents internal fields, which the OP doesn't talk about. Found a nice example in this blog post [2].

1: https://en.wikipedia.org/wiki/Linear_hashing

2: https://antonz.org/json-virtual-columns/

why use b trees if the keys are out of order?

DBs default to B-Trees even for synthetic primary keys because range queries are almost always necessary, for instance, if you want to paginate records. Some DBs also include a hash map index in addition to B-Trees, for instance Postgres [1], but still use B-Trees for primary keys. Sqlite3 doesn't support Hash indexes.

There's a very short chapter in "Modern B-Trees Techniques" [2] that compare B-Trees with Hash indexes:

* Durability schemes are simple and robust for b-trees, not so for hash maps.

* Ordering has advantages for concurrency control by means of key range locking.

* "Very few database implementation teams find hash indexes among the opportunities or features with a high ratio of benefit and effort, in particular if B-tree indexes are required in any case in order to support range queries and ordered scans."

1: https://www.postgresql.org/docs/current/indexes-types.html#I...

2: https://w6113.github.io/files/papers/btreesurvey-graefe.pdf

very nice thanks

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.

> I thought the point of nosql was O(1) GET and UPDATE operations

Tha was never the case. It would be silly to assume that given ultimately your GET and UPDATE operations are inter-process requests which involve serialization/deserializarion, and most of the time even require at least a network call.

network, encode/decode are still constant in terms of the dataset size. Still O(1).

O(1) doesn't mean "instant" it means "does not grow with the dataset"

Reply on news.ycombinator.com