Disclaimer up front: I somewhat agree with the performance sentiment towards databases, however I feel that index performance is a different thing, because it g

Disclaimer up front: I somewhat agree with the performance sentiment towards databases, however I feel that index performance is a different thing, because it gives you a larger budget for features further up the chain that make a meaningful non-performance difference for users, e.g. dynamic skew estimation and adaptation saving you from manual performance tuning. To make an additional performance point about my use-case, the work I linked is not competing with on-disk databases but with in-memory datastructures like nested hash-maps and I would argue the points from the article that you linked in that scenario, but with the scales adjusted appropriately (think ns and us instead of us and ms). To answer the question, prolly trees have a deterministic structure based on the chunking properties of their hash function. So their deterministic structure is a result of using a hash to identify nodes, and only implicitly defined over the contained keys (by rolling the hash over the leafs). Tries on the other hand, by virtue of being prefix trees, have a structure that is deterministic and directly based on the keys that they contain. This also allows you to compute a hash for each node (determined by they key range it represents) but because hashing is now orthogonal to the structure, you can choose tradeoffs more flexibly. You can for example use an incremental hash function [1], which in my case is SipHash for the leaves and xor as a combiner (Note the importance of using a keyed hash function like SipHash when XOR is used as a combiner, see the XHASH attack in [1].) So whenever a child is updated the new node hash can be maintained as `node.hash = (node.hash xor old_child.hash) xor new_child.hash)`. The original Nom author actually considered PATRICA Tries and HAMTs, but dismissed unhashed prefix-tries due to bad performance. I didn't run into this yet in my use-case however, and I suspect that the overhead of string interning, indirection vs direct pointers, and more expensive hash-functions, will always outweigh in the in-memory case. I'm still very interested in using prolly trees in the on-disk case, hence my question about latency :D 1: https://cseweb.ucsd.edu//~Mihir/papers/inchash.pdf https://cseweb.ucsd.edu//~Mihir/papers/inchash.pdf 2: https://github.com/attic-labs/noms/blob/master/doc/intro.md#some-properties-of-prolly-trees https://github.com/attic-labs/noms/blob/master/doc/intro.md#... BTW can you point me to where the "unicit" term originates from? a quick google search only ever shows it used in your writings :D