Real implementations of B-Trees (i.e. B+Trees) don't preserve the traditional guarantee about nodes being half full. However, space utilization is still a big a

Real implementations of B-Trees (i.e. B+Trees) don't preserve the traditional guarantee about nodes being half full. However, space utilization is still a big advantage. You can't do efficient retail deletes with hash indexes in the presence of duplicates because it isn't possible to append a unique-ifier (e.g. table TID) to the key, for exactly the same reason as it isn't generally possible to support multi-column indexes. In the case of Postgres hash indexes, it doesn't matter as much because VACUUM doesn't currently do retail deletions in any case. Postgres B-Tree indexes should support retail deletion at some point in the future, but that hasn't happened yet. Also, deleting whole B-Tree pages (removing them from the tree entirely) can be thought of (and implemented) as an operation that is symmetric to page splits. Page deletion is especially complicated at the best of times, because it's particularly hard to reason about race conditions (Postgres has many layers of indirection to get this to work). I can't imagine anything that would work as well, but with hash indexes.