3 ms·

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 n

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 https://en.wikipedia.org/wiki/Linear_hashing 2: https://antonz.org/json-virtual-columns/ https://antonz.org/json-virtual-columns/

tonymet 2y ago
why use b trees if the keys are out of order?
- emmanueloga_ 2y ago
  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#INDEXES-TYPES-HASH https://www.postgresql.org/docs/current/indexes-types.html#I... 2: https://w6113.github.io/files/papers/btreesurvey-graefe.pdf https://w6113.github.io/files/papers/btreesurvey-graefe.pdf
  - tonymet 2y ago
    very nice thanks

tonymet 2y ago

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

emmanueloga_ 2y ago
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#INDEXES-TYPES-HASH https://www.postgresql.org/docs/current/indexes-types.html#I... 2: https://w6113.github.io/files/papers/btreesurvey-graefe.pdf https://w6113.github.io/files/papers/btreesurvey-graefe.pdf
- tonymet 2y ago
  very nice thanks