CS计算机代考程序代写 concurrency 2021/4/28 B-trees

2021/4/28 B-trees
B-trees
B-Trees
B-Tree Depth
Selection with B-Trees Insertion into B-Trees Example: B-tree Insertion B-Tree Insertion Cost B-trees in PostgreSQL
>>
COMP9315 21T1 ♢ B-trees ♢ [0/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
1/17

2021/4/28 B-trees
❖ B-Trees
B-trees are multi-way search trees with the properties:
they are updated so as to remain balanced each node has at least (n-1)/2 entries in it each tree node occupies an entire disk page
B-tree insertion and deletion methods
are moderately complicated to describe can be implemented very efciently
Advantages of B-trees over general multi-way search trees: better storage utilisation (around 2/3 full)
better worst case performance (shallower)
∧ >>
COMP9315 21T1 ♢ B-trees ♢ [1/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
2/17

2021/4/28 B-trees
❖ B-Trees (cont) ExampleB-tree(depth=3,n=3) (actuallyB+tree)
<< ∧ >>
(Note: in DBs, nodes are pages ⇒ large branching factor, e.g. n=500)
COMP9315 21T1 ♢ B-trees ♢ [2/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
3/17

2021/4/28 B-trees
❖ B-Tree Depth
Depth depends on effective branching factor (i.e. how full nodes are). Simulation studies show typical B-tree nodes are 69% full.
Gives load Li = 0.69 × ci and depth of tree ~ ceil( logLi r ).
Example: ci=128, Li=88
<< ∧ >>
Level
#nodes
#keys
root
1
88
1
89
7832
2
7921
697048
3
704969
62037272
Note: ci is generally larger than 128 for a real B-tree.
COMP9315 21T1 ♢ B-trees ♢ [3/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
4/17

2021/4/28 B-trees
❖ Selection with B-Trees For one queries:
Node find(k,tree) {
return search(k, root_of(tree))
}
Node search(k, node) {
// get the page of the node
if (is_leaf(node)) return node
keys = array of nk key values in node
pages = array of nk+1 ptrs to child nodes
if (k <= keys[0]) return search(k, pages[0]) else if (keys[i] < k <= keys[i+1]) return search(k, pages[i+1]) else if (k > keys[nk-1])
return search(k, pages[nk])
}
<< ∧ >>
COMP9315 21T1 ♢ B-trees ♢ [4/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
5/17

2021/4/28 B-trees
❖ Selection with B-Trees (cont) Simplied description of search …
N = B-tree root node
while (N is not a leaf node) N = scanToFindChild(N,K)
tid = scanToFindEntry(N,K)
access tuple T using tid
Costone = (D + 1)r
<< ∧ >>
COMP9315 21T1 ♢ B-trees ♢ [5/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
6/17

2021/4/28 B-trees
❖ Selection with B-Trees (cont)
For range queries (assume sorted on index attribute):
search index to find leaf node for Lo
for each leaf node entry until Hi found
add pageOf(tid) to Pages to be scanned
scan Pages looking for matching tuples
Costrange = (D + bi + bq)r
<< ∧ >>
COMP9315 21T1 ♢ B-trees ♢ [6/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
7/17

2021/4/28 B-trees
❖ Insertion into B-Trees Overview of the method:
1. nd leaf node and position in node where new key belongs 2. if node is not full, insert entry into appropriate position
3. if node is full …
promote middle element to parent splitnodeintotwohalf-fullnodes (middle) insert new key into appropriate half-full node
4. if parent full, split and promote upwards
5. if reach root, and root is full, make new root upwards
Note: if duplicates not allowed and key exists, may stop after step 1.
<< ∧ >>
COMP9315 21T1 ♢ B-trees ♢ [7/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
8/17

2021/4/28 B-trees
❖ Example: B-tree Insertion Starting from this tree:
<< ∧ >>
insertthefollowingkeysinthegivenorder 12 15 30 10
COMP9315 21T1 ♢ B-trees ♢ [8/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
9/17

2021/4/28 B-trees
❖ Example: B-tree Insertion (cont)
<< ∧ >>
COMP9315 21T1 ♢ B-trees ♢ [9/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
10/17

2021/4/28 B-trees
❖ Example: B-tree Insertion (cont)
<< ∧ >>
COMP9315 21T1 ♢ B-trees ♢ [10/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
11/17

2021/4/28 B-trees
❖ B-Tree Insertion Cost
Insertion cost = CosttreeSearch + CosttreeInsert + CostdataInsert Best case: write one page (most of time)
traverse from root to leaf
read/write data page, write updated leaf
Costinsert = Dr+1w+1r+1w
Common case: 3 node writes (rearrange 2 leaves + parent)
traverse from root to leaf, holding nodes in buffer read/write data page
update/write leaf, parent and sibling
Costinsert = Dr+3w+1r+1w
<< ∧ >>
COMP9315 21T1 ♢ B-trees ♢ [11/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
12/17

2021/4/28 B-trees
<< ∧ >>
❖ B-Tree Insertion Cost (cont)
Worst case: propagate to root Costinsert = Dr + D.3w + 1r + 1w
traverse from root to leaf read/write data page
update/write leaf, parent and sibling repeat previous step D-1 times
COMP9315 21T1 ♢ B-trees ♢ [12/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
13/17

2021/4/28 B-trees
<< ∧ >>
❖ B-trees in PostgreSQL
PostgreSQL implements ≅ Lehman/Yao-style B-trees
variant that works effectively in high-concurrency environments.
B-tree implementation: backend/access/nbtree README … comprehensive description of methods nbtree.c … interface functions (for iterators) nbtsearch.c … traverse index to nd key value nbtinsert.c … add new entry to B-tree index
Notes:
stores all instances of equal keys (dense index)
avoids splitting by scanning right if key = max(key) in page
common insert case: new key is max(key) overall; handled efciently
COMP9315 21T1 ♢ B-trees ♢ [13/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
14/17

2021/4/28 B-trees
❖ B-trees in PostgreSQL (cont) Changes for PostgreSQL v12
indexes smaller
for composite keys, only store rst attribute
index entries are smaller, so ci larger, so tree shallower
include TID in index key
duplicate index entries are stored in “table order”
makes scanning table les to collect results more efcient
To explore indexes in more detail:
\di+ IndexName
select * from bt_page_items(IndexName,BlockNo)
<< ∧ >>
COMP9315 21T1 ♢ B-trees ♢ [14/15]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html
15/17

2021/4/28 B-trees
❖ B-trees in PostgreSQL (cont) Interface functions for B-trees
// build Btree index on relation
Datum btbuild(rel,index,…)
// insert index entry into Btree
Datum btinsert(rel,key,tupleid,index,…)
// start scan on Btree index
Datum btbeginscan(rel,key,scandesc,…)
// get next tuple in a scan
Datum btgettuple(scandesc,scandir,…)
// close down a scan
Datum btendscan(scandesc)
<< ∧ COMP9315 21T1 ♢ B-trees ♢ [15/15] https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html 16/17 2021/4/28 B-trees Produced: 24 Mar 2021 https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/b-trees/slides.html 17/17