CS计算机代考程序代写 chain database concurrency Tree-Structured Indexes

Example ISAM Tree
Each node can hold 2 entries; no need for `next-
leaf-page’pointers. (Why?) Root
40
51
63
20
33
10*
15*
20*
27*
33*
37*
40*
46*
51*
55*
63*
97*

Inserting 23*
Root
40
Index Pages
20
33
51
63
Primary Leaf Pages
Overflow Pages
10*
15*
20*
27*
33*
37*
40*
46*
51*
55*
63*
97*
23*

Inserting 48*
Root
40
Index Pages
20
33
51
63
Primary Leaf Pages
Overflow Pages
10*
15*
20*
27*
33*
37*
40*
46*
51*
55*
63*
97*
48*
23*

Inserting 41*
Root
40
Index Pages
20
33
51
63
Primary Leaf Pages
Overflow Pages
10*
15*
20*
27*
33*
37*
40*
46*
51*
55*
63*
97*
48*
41*
23*

Inserting 42*
Root
40
Index Pages
20
33
51
63
Primary Leaf Pages
Overflow Pages
10*
15*
20*
27*
33*
37*
40*
46*
51*
55*
63*
97*
48*
41*
23*
42*

Then Deleting 42*, 51*, 97*,55*
Root
40
Index Pages
20
33
51
63
Primary Leaf Pages
Overflow Pages
10*
15*
20*
27*
33*
37*
40*
46*
51*
55*
63*
97*
48*
41*
23*
42*

… After Deleting 42*, 51*, 97*, 55*
Root
40
51
63
20
33
10*
15*
20*
27*
33*
37*
40*
46*
63*
48*
41*
23*
☛ Note that 51* appears in index levels, but not in leaf!

B+ Tree: Most Widely Used Index § Insert/delete at log F N cost; keep tree height-
balanced. (F = fanout, N = # leaf pages)
§ Minimum 50% occupancy (except for root). Each
node contains d <= m <= 2d entries. § The parameter d is called the order of the tree. § Supports equality and range-searches efficiently. Index Entries (Direct search) Data Entries ("Sequence set") Example B+ Tree Search begins at root, and key comparisons direct it to a leaf. Search for 5*, 15*, all data entries >= 24* …
Root
13
17
24
30
2*
3*
5*
7*
14*
16*
19*
20*
22*
24*
27*
29*
33*
34*
38*
39*
☛ Based on the search for 15*, we know it is not in the tree!

B+ Trees in Practice Typical order: 100. Typical fill-factor: 67%.
– average fanout = 133
Typical capacities:
– Height 4: 1334 = 312,900,700 records – Height 3: 1333 = 2,352,637 records
Can often hold top levels in buffer pool: – Level1= 1page = 8Kbytes
– Level2= 133pages= 1Mbyte
– Level 3 = 17,689 pages = 133 MBytes

Inserting a Data Entry into a B+ Tree § Find correct leaf L.
§ Put data entry onto L.
– IfLhasenoughspace,done!
– Else, must split L (into L and a new node L2) • Redistribute entries evenly, copy up middle key. • Insert index entry pointing to L2 into parent of L.
§ This can happen recursively
– To split index node, redistribute entries evenly, but
push up middle key. (Contrast with leaf splits.)
§ Splits “grow” tree; root split increases height.
– Treegrowth:getswideroroneleveltallerattop.

Inserting 8*
Root
13
17
24
30
2*
3*
5*
7*
14*
16*
19*
20*
22*
24*
27*
29*
33*
34*
38*
39*
Node 5 is copied up.
17 is pushed up
5
17
2*
3*
5*
7*
8*
5
13
24
30

After Inserting 8*
Root
17
5
13
24
30
2*
3*
5*
7*
8*
14*
16*
19* 20*
22*
24*
27*
29*
33*
34*
38*
39*
vIn this example, we can avoid split by re-distributing entries; however, this is usually not done in practice.
§ Redistributing I/O costs is not smaller than those of splitting.
§ It has a chance that redistributing does not work; thus costs for exploring redistribution are wasted.

Deleting a Data Entry from a B+ Tree
§ Start at root, find leaf L where entry belongs.
§ Remove the entry.
§ If L is at least half-full, done!
§ IfLhasonlyd-1entries,
§ Try to re-distribute, borrowing from sibling (adjacent node with
same parent as L).
§ If re-distribution fails, merge L and sibling.
§ If merge occurred, must delete entry (pointing to L or sibling) from parent of L.
§ Merge could propagate to root, decreasing height.

Deleting 19*
Root
17
5
13
24
30
2*
3*
5*
7*
8*
14*
16*
19* 20*
22*
24*
27*
29*
33*
34*
38*
39*

Deleting 20*
Root
17
5
13
24
30
2*
3*
5*
7*
8*
14*
16*
20*
22*
24*
27*
29*
33*
34*
38*
39*

After Deleting 20* …
Root
17
5
13
27
30
2*
3*
5*
7*
8*
14*
16*
22* 24*
27*
29*
33*
34*
38*
39*
Deleting 20* is done with re-distribution. Notice how middle key is copied up.

Deleting 24* …
Root
17
5
13
27
30
2*
3*
5*
7*
8*
14*
16*
22* 24*
27*
29*
33*
34*
38*
39*
30
22*
27*
29*
33*
34*
38*
39*

Root
After Deleting 24*
5
13
17
30
2*
3*
5*
7*
8*
14*
16*
22*
27*
29*
33*
34*
38*
39*

Example of Non-leaf Re-distribution
Root
22
30
5
13
17
20
2*
3*
5*
7*
8*
14*
16*
17* 18*
20*
21*
22* 27* 29*
33* 34* 38*
39*
Root
17
20
22
30
5
13
3*
5*
7*
8*
14*
16*
17* 18*
20*
21*
22*
27* 29*
33*
34*
38*
39*

Prefix Key Compression § Important to increase fan-out. (Why?)
§ Key values in index entries only `direct traffic’; can often compress them.
§ E.g., If we have adjacent index entries with search key values Dannon Yogurt, David Smith and Devarakonda Murthy, we can abbreviate David Smith to Dav. (The other keys can be compressed too …)
§ Is this correct? Not quite! What if there is a data entry Davey Jones? (Can only compress David Smith to Davi)
§ In general, while compressing, must leave each index entry greater than every key value (in any subtree) to its left.
§ Insert/delete must be suitably modified.
Dannon Yogurt
Davey Jones
David Smith
……

Bulk Loading of a B+ Tree
§ If we have a large collection of records, and we want to create a B+ tree on some field, doing so by repeatedly inserting records is very slow.
§ Bulk Loading can be done much more efficiently.
§ Initialization: Sort all data entries, insert pointer to
first (leaf) page in a new (root) page.
Root
Sorted pages of data entries; not yet in B+ tree
6*
9*
10*
11*
12*
13*
20*
22*
23*
31*
35*
36*
38*
41*
44*
3*
4*

Bulk Loading (Contd.)
Root
10
20
• Index entries for leaf pages always entered into right-most index page just above leaf level. When this fills up, it splits. (Split may go up right-most path to the root.)
• Much faster than repeated inserts, especially when one considers locking!
Data entry pages not yet in B+ tree
6
12
23
35
3*
4*
6*
9*
10* 11*
12* 13*
20*22*
23* 31*
35*36*
38*41*
44*
20
Root
10
Data entry pages not yet in B+ tree
6
38
12
23
35
3*
4*
6*
9*
10*
11*
12* 13*
23* 31*
20* 22*
35* 36*
38* 41*
44*

Summary of Bulk Loading
Option 1: multiple inserts. – Slow.
– Does not give sequential storage of leaves.
Option 2: Bulk Loading
– Has advantages for concurrency control.
– Fewer I/Os during build.
– Leaves will be stored sequentially (and linked, of course).
– Can control “fill factor” on pages.

A Note on `Order’
Order (d) concept replaced by physical space criterion in practice (`at least half-full’).
– Indexpagescantypicallyholdmanymoreentriesthan leaf pages.
– Variablesizedrecordsandsearchkeysmeandiffernt nodes will contain different numbers of entries.
– Even with fixed length fields, multiple records with the same search key value (duplicates) can lead to variable-sized data entries (if we use Alternative (3)).

Summary
Tree-structured indexes are ideal for range-searches, also good for equality searches.
ISAM is a static structure.
– Onlyleafpagesmodified;overflowpagesneeded.
– Overflowchainscandegradeperformanceunlesssize of data set and data distribution stay constant.
B+ tree is a dynamic structure.
– Inserts/deletes leave tree height-balanced; log F N cost. – Highfanout(F)meansdepthrarelymorethan3or4.
– Almostalwaysbetterthanmaintainingasortedfile.

Summary (Contd.) – Typically,67%occupancyonaverage.
– Usually preferable to ISAM, modulo locking considerations; adjusts to growth gracefully.
– If data entries are data records, splits can change rids!
§ Key compression increases fanout, reduces height.
§ Bulk loading can be much faster than repeated inserts for creating a B+ tree on a large data set.
§ Most widely used index in database management systems because of its versatility. One of the most optimized components of a DBMS.