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