Re: Free Space Map data structure

On Wed, Apr 9, 2008 at 12:22 AM, Heikki Linnakangas
<heikki(at)enterprisedb(dot)com> wrote:

>
> Well, if you add the higher levels, we're no longer talking about O(1), but
> O(log n) (for a pretty steep logarithm), just like my proposal.
>

For updates, I would still call it O(1) because the number of levels is limited
and a very small number.

>
> It's actually not that orthogonal. You describe it as a hierarchical
> bitmap, but it's essentially the same idea as the binary heap/tree, just
> with way more than 2 children per parent.
>

Yes, I agree.

Btw, I agree with Tom's point about the lock contention on the higher levels
for FSM updates. What we can do is during normal operations, FSM pages
are updated with a SHARE lock - so the information can best be considered
only as hint. Hopefully, if we are only doing bit flipping, we won't go wrong
often. And periodically, VACUUM would correct any mistakes in FSM info.

Thanks,
Pavan

--
Pavan Deolasee
EnterpriseDB http://www.enterprisedb.com