On 09.11.2013 18:49, Heikki Linnakangas wrote:
We could just punt if more than X pages would need to be changed. That would mean that we never delete pages at the top (h - X) levels of the tree. In practice that should be fine if X is high enough. As a data point, GIN list page deletion holds 16 pages locked at once (GIN_NDELETE_AT_ONCE). Normally, a 16-level deep B-tree is pretty huge. As another data point, in the worst case the keys are so wide that only 2 keys fit on each B-tree page. With that assumption, the tree can be at most 32 levels deep if you just insert into it with no deletions, since MaxBlockNumber ~= 2^32 (I may be off by one in either direction, not sure). Deletions make it more complicated, but I would be pretty surprised if you can construct a B-tree tallers than, say 40 levels.
On further thought, it's worse than that. To delete a page, you need to lock the left and right siblings, so you need 3 pages locked per each level you delete...
- Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
