This is the first commercial RDBMS documentation, from 1981, clearly saying that you can expect 25% free space on average in a B-Tree. And during 30 years, many DBAs made money rebuilding indexes on Sunday because they were "fragmented" 🤣 #RTFM
Conversation
Replying to
I believe that somebody proved that space utilization of ln(2) is expected steady state back in 1978. So space utilization of just under 70% (or free space that's just over 30%) is expected with random insertions and deletions.
1
2
To be fair to those DBAs, this kind of analysis is made somewhat harder by important special cases. Indexes on identity columns (the typical serial PK case) are simply a different thing. Space utilization of 90% or greater is realistically attainable, and very common.
Replying to
Yes, and it is also a balance on space (and read performance) vs concurrency (and writes)
1
1
Replying to
One truly surprising thing about B-Tree space utilization is that not merging together half empty nodes arguably has very little impact on space utilization:
1