> On the topic of how important it is for B-trees to be "orderly": https://news.ycombinator.com/item?id=34404641 https://news.ycombinator.com/item?id=34404641

> On the topic of how important it is for B-trees to be "orderly": https://news.ycombinator.com/item?id=34404641 https://news.ycombinator.com/item?id=34404641 I don't think this is the same phenomenon at all, if anything that looks like an implementation problem rather than something that's somehow inherent in B-trees. Depending on how you construct the tree, it's however still possible to end up with something that's very fragmented and inefficient, but you can always construct a dense b-tree with a space complexity of O(N/(B-1)). To see why you can just lay out the data in a list and manually create the index layers. Each layer will be bounded by N/B, N/B², N/B³, ... (and the sum of 1/B^n over all n is 1/(B-1) ) Considering an actual tree, for N=10, B=3 1 2 3 4 5 6 7 8 9 10 data <3 | <6| <9 | <10 index 1 <6 |<10 | index 2 <10 root Looking at this, I think it should be apparent that if you change this ordered sequence 1-10 to ten UUIDs ordered in the same way, there would be no change in the structure of the tree. It would be a bit bigger on disk because UUIDs are bigger than integers, and you may end up with an additional data layer because of that (because you want to align with the disk block size). One reason you might see a difference even when the implementation makes the appropriate assumptions is that B-trees can do very clever things with somewhat sequential data when it comes to joins, where you can get linear nearly runtimes for the operation. But as mentioned, this only works with relatively ordered data.