4 ms·

It means the balancing is content-dependent, and is normally balanced, but certain edge-case inputs may result in sub-optimal behaviour.

• zombot 1y ago
  What is probabilistic about that? It sounds deterministic.
  • mcherm 1y ago
    The specific behavior of the hash function (including the salt you chose). Choosing a different hash function (or a different salt) would result in a different breakdown into chunks. In principle, if your data were specially crafted to exploit the specific hash function (and salt) you could get an aberrant case like 1 million entries in a single b-tree node or a million b-tree nodes with just one entry. But unless you intentionally exploit the hash function the chance of this is vanishingly small.
  • moomin 1y ago
    It's a term of art. We say the same thing about quicksort being "usually" O(n log n)
  • judofyr 1y ago
    The opposite of probabilistic is not deterministic in this context. This is not about «drawing a random number», but rather that balancing is dependent on the input data. «With high probability» here means «majority of the possible input data leads to a balanced structure». If it was not probabilistic then the balancing would be guaranteed in all cases. This typically means that it somehow stores balancing information somewhere so that it can detect when something is unbalanced and repair it. In this data structure we’re just hashing the content without really caring about the current balance and then it turns out that for most inputs it will be fine.
  • stonemetal12 1y ago
    Like quicksort is O(N log N) on average but can degrade to O(N^2) in the worse case. The tree is balanced on average, but can degrade to not close to balanced in the worst case.