Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit624686a

Browse files
Adjust "root of to-be-deleted subtree" function.
Restructure the function that locates the root of the to-be-deletedsubtree during nbtree page deletion. Handle the conditions that makepage deletion unsafe in a slightly more uniform way, and acknowledge thefact that the behavior with incomplete splits on internal pages isdifferent (as pointed out in the nbtree README as of commit35bc0ec).Also invent new terminology that avoids ambiguity around which pages areabout to be deleted. Consistently use the term "to-be-deleted subtree",not the ambiguous term "branch".We were calling the subtree parent page the "top parent page", but thatwas quite misleading. The top parent page usually refers to a pageunlinked from its siblings and marked deleted (during the second stageof page deletion). There was one kind of top parent page that we merelyremoved a downlink from, and another kind of top parent page that weactually marked deleted. Eliminate the ambiguity by inventing a newterm ("subtree parent page") that refers to the former kind of pageonly.
1 parenta8be536 commit624686a

File tree

5 files changed

+278
-215
lines changed

5 files changed

+278
-215
lines changed

‎src/backend/access/nbtree/README

Lines changed: 10 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -223,9 +223,10 @@ right to make this happen --- a scan moving in the opposite direction
223223
might miss the items if so.) Also, we *never* delete the rightmost page
224224
on a tree level (this restriction simplifies the traversal algorithms, as
225225
explained below). Page deletion always begins from an empty leaf page. An
226-
internal page can only be deleted as part of a branch leading to a leaf
227-
page, where each internal page has only one child and that child is also to
228-
be deleted.
226+
internal page can only be deleted as part of deleting an entire subtree.
227+
This is always a "skinny" subtree consisting of a "chain" of internal pages
228+
plus a single leaf page. There is one page on each level of the subtree,
229+
and each level/page covers the same key space.
229230

230231
Deleting a leaf page is a two-stage process. In the first stage, the page
231232
is unlinked from its parent, and marked as half-dead. The parent page must
@@ -243,7 +244,12 @@ it, but it's still linked to its siblings.
243244

244245
(Note: Lanin and Shasha prefer to make the key space move left, but their
245246
argument for doing so hinges on not having left-links, which we have
246-
anyway. So we simplify the algorithm by moving the key space right.)
247+
anyway. So we simplify the algorithm by moving the key space right. This
248+
is only possible because we don't match on a separator key when ascending
249+
the tree during a page split, unlike Lehman and Yao/Lanin and Shasha -- it
250+
doesn't matter if the downlink is re-found in a pivot tuple whose separator
251+
key does not match the one encountered when inserter initially descended
252+
the tree.)
247253

248254
To preserve consistency on the parent level, we cannot merge the key space
249255
of a page into its right sibling unless the right sibling is a child of

‎src/backend/access/nbtree/nbtinsert.c

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2278,7 +2278,8 @@ _bt_finish_split(Relation rel, Buffer lbuf, BTStack stack)
22782278
*stack. For example, the checkingunique _bt_doinsert() case may
22792279
*have to step right when there are many physical duplicates, and its
22802280
*scantid forces an insertion to the right of the "first page the
2281-
*value could be on".
2281+
*value could be on". (This is also relied on by all of our callers
2282+
*when dealing with !heapkeyspace indexes.)
22822283
*
22832284
*Returns write-locked parent page buffer, or InvalidBuffer if pivot
22842285
*tuple not found (should not happen). Adjusts bts_blkno &

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp