Now Reading
how the append-only btree works

how the append-only btree works

2023-12-29 08:38:26


how the append-only btree works

Take into account this 3-level b+tree. There are two ranges of department pages
(the foundation is a department web page), and 5 leaf pages. Information and keys are
saved within the leaf pages.

Leaf chaining, ie hyperlinks between leaf pages for simple sequential
entry, isn’t supported as it will require the entire tree to
be rewritten on every replace.



The pages are saved sequentially within the database file. Growing
web page numbers means rising file offsets. The meta web page consists of
a pointer to the foundation web page, a SHA1 hash, and statistics counters.

When the file is opened it’s scanned backwards web page by web page to
discover a legitimate meta web page, and thus the foundation of the tree.



When updating a worth in leaf web page 8, as a substitute of adjusting the
web page in-place, an entire new web page is appended to the file (right here as
web page 12). As a result of the situation of the web page is modified, every dad or mum
web page must be up to date to level to the brand new places.

Leaf web page 7 isn’t affected. A brand new root web page is created
as a replica of the earlier root web page, solely the pointer to department
web page 6 is up to date to level to department web page 11.

Any cursor nonetheless having a pointer to root web page 9 can traverse the
tree unaffected by the change. It’ll see a constant snapshot
of the database. Dashed pages and pointers within the diagram are
nonetheless there within the file, they’re simply not the final model.



See Also

Within the file, pages are written sequentially by appending new pages
to the file. Already written pages are by no means modified.

After every new era of the tree is written, there’s a meta
web page pointing to the brand new root.



Altering one web page (leaf web page 8) resulted in 4 new pages being
appended to the file. This wastes disk area, however writing consecutive
pages to disk is extra environment friendly than writing random places.
And there’s no want for a transaction log, as a result of the
database file is the transaction log
.

Source Link

What's Your Reaction?
Excited
0
Happy
0
In Love
0
Not Sure
0
Silly
0
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top