CS计算机代考程序代写 database chain data structure 2021/4/28 Page Internals

2021/4/28 Page Internals
Page Internals
Pages
Page Formats Page Formats Storage Utilisation Overows
>>
COMP9315 21T1 ♢ Page Internals ♢ [0/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
1/20

2021/4/28 Page Internals
❖ Pages
Database applications view data as:
a collection of records (tuples)
records can be accessed via a TupleId/RecordId/RID TupleId = (PageID + TupIndex)
The disk and buffer manager provide the following view: data is a sequence of xed-size pages (aka “blocks”) pages can be (random) accessed via a PageID
each page contains zero or more tuple values
Page format = how space/tuples are organised within a page
COMP9315 21T1 ♢ Page Internals ♢ [1/18]
∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
2/20

2021/4/28 Page Internals
❖ Pages (cont)
Data les consist of pages containing tuples:
<< ∧ >>
Each data le (in PostgreSQL) is related to one table.
COMP9315 21T1 ♢ Page Internals ♢ [2/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
3/20

2021/4/28 Page Internals
<< ∧ >>
❖ Page Formats
Ultimately, a Page is simply an array of bytes (byte[]).
We want to interpret/manipulate it as a collection of Records (tuples).
Tuples are addressed by a record ID (rid = (PageId,TupIndex))
Typical operations on Pages:
request_page(pid) … get page via its PageId get_record(rid) … get record via its TupleId
rid = insert_record(pid,rec)…addnewrecord update_record(rid,rec) … update value of record delete_record(rid) … remove record from page
COMP9315 21T1 ♢ Page Internals ♢ [3/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
4/20

2021/4/28 Page Internals
<< ∧ >>
❖ Page Formats (cont)
Page format = tuples + data structures allowing tuples to be
found
Characteristics of Page formats:
recordsizevariability (xed,variable)
how free space within Page is managed whether some data is stored outside Page
does Page have an associated overow chain?
are large data values stored elsewhere? (e.g. TOAST) can one tuple span multiple Pages?
Implementation of Page operations critically depends on format.
COMP9315 21T1 ♢ Page Internals ♢ [4/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
5/20

2021/4/28 Page Internals
❖ Page Formats (cont)
For xed-length records, use record slots.
insert: place new record in rst available slot
delete: two possibilities for handling free record slots:
<< ∧ >>
COMP9315 21T1 ♢ Page Internals ♢ [5/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
6/20

2021/4/28 Page Internals
❖ Page Formats
For variable-length records, must use slot directory. Possibilities for handling free-space within block:
compacted (one region of free space) fragmented (distributed free space)
In practice, a combination is useful:
normally fragmented (cheap to maintain) compacted when needed (e.g. record won’t t)
Important aspect of using slot directory
location of tuple within page can change, tuple index does not change
COMP9315 21T1 ♢ Page Internals ♢ [6/18]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
7/20

2021/4/28 Page Internals
❖ Page Formats (cont) Compacted free space:
<< ∧ >>
Note: “pointers” are implemented as word offsets within block.
COMP9315 21T1 ♢ Page Internals ♢ [7/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
8/20

2021/4/28 Page Internals
❖ Page Formats (cont) Fragmented free space:
<< ∧ >>
COMP9315 21T1 ♢ Page Internals ♢ [8/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
9/20

2021/4/28 Page Internals
❖ Page Formats (cont)
Initial page state (compacted free space) …
<< ∧ >>
COMP9315 21T1 ♢ Page Internals ♢ [9/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
10/20

2021/4/28 Page Internals
❖ Page Formats (cont)
Before inserting record 7 (compacted free space) …
<< ∧ >>
COMP9315 21T1 ♢ Page Internals ♢ [10/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
11/20

2021/4/28 Page Internals
❖ Page Formats (cont)
After inserting record 7 (80 bytes) …
<< ∧ >>
COMP9315 21T1 ♢ Page Internals ♢ [11/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
12/20

2021/4/28 Page Internals
❖ Page Formats (cont)
Initial page state (fragmented free space) …
<< ∧ >>
COMP9315 21T1 ♢ Page Internals ♢ [12/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
13/20

2021/4/28 Page Internals
❖ Page Formats (cont)
Before inserting record 7 (fragmented free space) …
<< ∧ >>
COMP9315 21T1 ♢ Page Internals ♢ [13/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
14/20

2021/4/28 Page Internals
❖ Page Formats (cont)
After inserting record 7 (80 bytes) …
<< ∧ >>
COMP9315 21T1 ♢ Page Internals ♢ [14/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
15/20

2021/4/28 Page Internals
❖ Storage Utilisation
How many records can t in a page? (denoted C = capacity) Depends on:
page size … typical values: 1KB, 2KB, 4KB, 8KB
record size … typical values: 64B, 200B, app-dependent page header data … typically: 4B – 32B
slot directory … depends on how many records
We typically consider average record size (R)
Given C, HeaderSize + C*SlotSize + C*R ≤ PageSize
COMP9315 21T1 ♢ Page Internals ♢ [15/18]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
16/20

2021/4/28 Page Internals
<< ∧ >>
❖ Overows
Sometimes, it may not be possible to insert a record into a
page:
1. no free-space fragment large enough 2. overall free-space is not large enough 3. the record is larger than the page
4. no more free directory slots in page
For case (1), can rst try to compact free-space within the page.
If still insufcient space, we need an alternative solution …
COMP9315 21T1 ♢ Page Internals ♢ [16/18]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
17/20

2021/4/28 Page Internals
❖ Overows (cont)
File organisation determines how cases (2)..(4) are handled. If records may be inserted anywhere that there is free space
cases (2) and (4) can be handled by making a new page case (3) requires either spanned records or “overow le”
If le organisation determines record placement (e.g. hashed le)
cases (2) and (4) require an “overow page” case (3) requires an “overow le”
With overow pages, rid structure may need modifying (rel,page,ov,rec)
COMP9315 21T1 ♢ Page Internals ♢ [17/18]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html
18/20

2021/4/28 Page Internals
❖ Overows (cont)
Overow les for very large records and BLOBs:
<< ∧ Record-based handling of overows: We discuss overow pages in more detail when covering Hash Files. COMP9315 21T1 ♢ Page Internals ♢ [18/18] https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html 19/20 2021/4/28 Page Internals Produced: 23 Feb 2021 https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/pages/slides.html 20/20