Learned Indexes for a Google-scale Disk-based Database

In theory, you can treat the objects as i.i.d. giving them a uniform prior. In practice, of course only the inputs are inputs and if you were to take that into account then you could avoid collisions, but as you say, you can't really know that ahead of time. Unless you can, such as when there is structure to the inputs or some other source of non-uniformity that you can account for. The topic of learned indexes is worth investigating if you're interested: https://arxiv.org/abs/1712.01208 https://arxiv.org/abs/2012.12501

Also, Learned Indexes Structures: The Case for Learned Index Structures: https://arxiv.org/abs/1712.01208 Learned Indexes for a Google-scale Disk-based Database: https://arxiv.org/abs/2012.12501 And Noms/Dolt Prolly Trees: How to Chunk Your Database into a Merkle Tree: https://dolthub.com/blog/2022-06-27-prolly-chunker/

> It seems wildly impracticable to productionize at the moment (excepting Google, perhaps). There were a couple related papers [1, 2] from Google on learning to index a few years ago. In fact, I'm a little surprised they weren't cited. [1]: https://dl.acm.org/doi/pdf/10.1145/3183713.3196909 [2]: https://arxiv.org/pdf/2012.12501.pdf