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

Commit49b86fb

Browse files
committed
Add a few paragraphs to B-tree README explaining L&Y algorithm.
This gives an overview of what Lehman & Yao's paper is all about, so thatyou can understand the rest of the README without having to read the paper.Per discussion with Peter Geoghegan and others.
1 parent0bd624d commit49b86fb

File tree

1 file changed

+19
-2
lines changed
  • src/backend/access/nbtree

1 file changed

+19
-2
lines changed

‎src/backend/access/nbtree/README

Lines changed: 19 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,8 +11,25 @@ use a simplified version of the deletion logic described in Lanin and
1111
Shasha (V. Lanin and D. Shasha, A Symmetric Concurrent B-Tree Algorithm,
1212
Proceedings of 1986 Fall Joint Computer Conference, pp 380-389).
1313

14-
The Lehman and Yao Algorithm and Insertions
15-
-------------------------------------------
14+
The basic Lehman & Yao Algorithm
15+
--------------------------------
16+
17+
Compared to a classic B-tree, L&Y adds a right-link pointer to each page,
18+
to the page's right sibling. It also adds a "high key" to each page, which
19+
is an upper bound on the keys that are allowed on that page. These two
20+
additions make it possible detect a concurrent page split, which allows the
21+
tree to be searched without holding any read locks (except to keep a single
22+
page from being modified while reading it).
23+
24+
When a search follows a downlink to a child page, it compares the page's
25+
high key with the search key. If the search key is greater than the high
26+
key, the page must've been split concurrently, and you must follow the
27+
right-link to find the new page containing the key range you're looking
28+
for. This might need to be repeated, if the page has been split more than
29+
once.
30+
31+
Differences to the Lehman & Yao algorithm
32+
-----------------------------------------
1633

1734
We have made the following changes in order to incorporate the L&Y algorithm
1835
into Postgres:

0 commit comments

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