Why does L&Y Blink Tree need lock coupling?

From: Oliver Yang <olilent2ctw(at)gmail(dot)com>
To: pgsql-hackers(at)lists(dot)postgresql(dot)org
Subject: Why does L&Y Blink Tree need lock coupling?
Date: 2022-12-12 01:38:31
Message-ID: CALJbhHPiudj4usf6JF7wuCB81fB7SbNAeyG616k+m9G0vffrYw@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hi,

The README in nbtree mentions that L&Y algorithm must couple
locks when moving right during ascent for insertion. However,
it's hard to see why that's necessary. Since L&Y mostly
discussed concurrent insertions and searches, what can go wrong
if inserters only acquire one lock at a time?

The Lanin&ShaSha paper cited in README also agrees that B-link
structure allows inserts and searches to lock only one node at a
time although it's not apparent in L&Y itself.

Thanks,

Hong

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2022-12-12 01:48:15 Re: Checksum errors in pg_stat_database
Previous Message Michael Paquier 2022-12-12 01:08:08 Re: Checksum errors in pg_stat_database