CS计算机代考程序代写 data structure database chain >>

>>
Page Internals

• Pages
• Page Formats
• Page Formats
• Storage Utilisation
• Overflows
COMP9315 21T1 ♢ Page Internals ♢ [0/18]
∧ >>
❖ 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 fixed-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]
<< ∧ >>
❖ Pages (cont)


Data files consist of pages containing tuples:






Each data file (in PostgreSQL) is related to one table.
COMP9315 21T1 ♢ Page Internals ♢ [2/18]
<< ∧ >>
❖ 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) … add new record
• update_record(rid,rec) … update value of record
• delete_record(rid) … remove record from page
COMP9315 21T1 ♢ Page Internals ♢ [3/18]
<< ∧ >>
❖ Page Formats (cont)

Page format = tuples + data structures allowing tuples to be found
Characteristics of Page formats:
• record size variability   (fixed, variable)
• how free space within Page is managed
• whether some data is stored outside Page
◦ does Page have an associated overflow 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]
<< ∧ >>
❖ Page Formats (cont)

For fixed-length records, use record slots.
• insert: place new record in first available slot
• delete: two possibilities for handling free record slots:



COMP9315 21T1 ♢ Page Internals ♢ [5/18]
<< ∧ >>
❖ 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 fit)

Important aspect of using slot directory
• location of tuple within page can change, tuple index does not change
COMP9315 21T1 ♢ Page Internals ♢ [6/18]
<< ∧ >>
❖ Page Formats (cont)

Compacted free space:  



Note: “pointers” are implemented as word offsets within block.
COMP9315 21T1 ♢ Page Internals ♢ [7/18]
<< ∧ >>
❖ Page Formats (cont)

Fragmented free space:  




COMP9315 21T1 ♢ Page Internals ♢ [8/18]
<< ∧ >>
❖ Page Formats (cont)

Initial page state (compacted free space) …



COMP9315 21T1 ♢ Page Internals ♢ [9/18]
<< ∧ >>
❖ Page Formats (cont)

Before inserting record 7 (compacted free space) …



COMP9315 21T1 ♢ Page Internals ♢ [10/18]
<< ∧ >>
❖ Page Formats (cont)

After inserting record 7 (80 bytes) …



COMP9315 21T1 ♢ Page Internals ♢ [11/18]
<< ∧ >>
❖ Page Formats (cont)

Initial page state (fragmented free space) …



COMP9315 21T1 ♢ Page Internals ♢ [12/18]
<< ∧ >>
❖ Page Formats (cont)

Before inserting record 7 (fragmented free space) …



COMP9315 21T1 ♢ Page Internals ♢ [13/18]
<< ∧ >>
❖ Page Formats (cont)

After inserting record 7 (80 bytes) …



COMP9315 21T1 ♢ Page Internals ♢ [14/18]
<< ∧ >>
❖ Storage Utilisation

How many records can fit 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]
<< ∧ >>
❖ Overflows

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 first try to compact free-space within the page.
If still insufficient space, we need an alternative solution …
COMP9315 21T1 ♢ Page Internals ♢ [16/18]
<< ∧ >>
❖ Overflows (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 “overflow file”
If file organisation determines record placement (e.g. hashed file)
• cases (2) and (4) require an “overflow page”
• case (3) requires an “overflow file”
With overflow pages, rid structure may need modifying (rel,page,ovfl,rec)
COMP9315 21T1 ♢ Page Internals ♢ [17/18]
<< ∧ ❖ Overflows (cont) Overflow files for very large records and BLOBs:  Record-based handling of overflows:  We discuss overflow pages in more detail when covering Hash Files. COMP9315 21T1 ♢ Page Internals ♢ [18/18] Produced: 23 Feb 2021