程序代写代做代考 Excel database chain cache Microsoft PowerPoint - 16- Indexing-p2

Microsoft PowerPoint – 16- Indexing-p2

Indexing:
B+ Tree &

Hash Tables
Doris Xin, Abdu Alawini

University of Illinois at Urbana-Champaign

CS411: Database Systems

October 24, 2018

Announcements

• HW 3: Due by Friday 10/26 (23:59)
•Sign up for PT1 midterm demos: Due by Friday 10/26

(23:59)
https://wiki.illinois.edu/wiki/display/cs411sfa18/Project+Track+1
+Midterm+Demo+Signup

• Midterm review session: Friday 10/26 (4:00-4:50) SC 1404
• To suggest topics to discuss in the review session, please fill this

form: https://goo.gl/forms/5fDcm80cDjmtMJ0H3

•Please fill the early course feedback form:
https://goo.gl/forms/SC4BYcrDy8dai8PE2

•Midterm: 10/29 in class 11-12:15 pm
2

Today’s lecture

•Indexing
• Continue with B+ Trees
• Hash Tables

What is the best part of the class so far?

What is the least useful part of the
course so far?

What would you change to make the
course even better?

B+ Trees (Recap)

•Multi-level index on a specific search key
•Nodes contain keys and pointers

• Internal nodes: point to other nodes
• Leaf nodes: point to data records; last pointer to the next leaf node

20 60

10 15 18 20 30 50

15 18 20 30 50

B+ Trees (Recap con’t)

•Each node can contain up to n keys;
• All nodes have the same capacity (n max keys)
• Degree d = n/2  the minimum # of keys per node

(assume n is even for simplicity)
• Each node has between [d, 2d] keys at all times
• Except root node, which can have only one key.

• In practice, each node has its own file block
• For a 4KB block, we can accommodate up to 340 keys (d=170).
• In practice, d = 100, 66.5% fill-in factor  133 keys
• Visiting one node = one disk read (latency ~ 105-107 ns)
• First 3 levels of can be cached in main memory (latency ~ 100 ns) to

reduce disk reads
8

an artificial
requirement to
make B+ Trees
“balanced”

B+ Trees (Recap con’t)

•Do B+ Trees always help?
• No. e.g., an array of sorted integers.

•Types of queries to answer with a B+ Tree:
• Exact key value, e.g., SELECT name FROM people WHERE age=20
• Range queries, e.g., SELECT name FROM people WHERE age>=20

and age<=70 9 © 2018 A. Alawini & A. Parameswaran 1 0 id = 1, name = “Kyle”, age = 15 id = 3, name = “Bob”, age = 20 id = 10, name = “Ivan”, age = 22 id = 12, name = “Diana”, age = 19 id = 13, name = “Ed”, age = 20 id = 15, name = “Lucy”, age = 19 id = 27, name = “George”, age = 21 id = 30, name = “Helen”, age = 23 id = 33, name = “Cathy”, age = 18 id = 35, name = “Jennifer”, age = 22 id = 38, name = “Alice”, age = 21 id = 70, name = “Fred”, age = 18 1 3 10 12 13 15 27 30 33 35 38 70 dense (entry for every record) d = 2 n = 4 B+ Tree search key = id © 2018 A. Alawini & A. Parameswaran 1 1 id = 1, name = “Alice”, age = 15 id = 3, name = “Bob”, age = 20 id = 10, name = “Carl”, age = 22 id = 12, name = “Diana”, age = 19 id = 13, name = “Ed”, age = 20 id = 15, name = “Fred”, age = 19 id = 27, name = “Ginger”, age = 21 id = 30, name = “Helen”, age = 23 id = 33, name = “Ivan”, age = 18 id = 35, name = “Jennifer”, age = 22 id = 38, name = “Kyle”, age = 21 id = 70, name = “Louise”, age = 18 1 3 10 12 13 15 27 30 33 35 38 70 12 30 80 82 86 35 dense (entry for every record) d = 2 n = 4 B+ Tree search key = id © 2018 A. Alawini & A. Parameswaran 1 2 id = 1, name = “Alice”, age = 15 id = 3, name = “Bob”, age = 20 id = 10, name = “Carl”, age = 22 id = 12, name = “Diana”, age = 19 id = 13, name = “Ed”, age = 20 id = 15, name = “Fred”, age = 19 id = 27, name = “Ginger”, age = 21 id = 30, name = “Helen”, age = 23 id = 33, name = “Ivan”, age = 18 id = 35, name = “Jennifer”, age = 22 id = 38, name = “Kyle”, age = 21 id = 70, name = “Louise”, age = 18 15 18 18 19 19 2 0 2 0 21 21 22 22 23 dense (entry for every record) d = 2 n = 4 B+ Tree search key = age 19 21 24 25 22 © 2018 A. Alawini & A. Parameswaran Think-Pair Share Exercise 13 Min capacity of a data entry page is 1 entry; Min capacity of an index page is 2 pointers/1 key value. Leaf nodes (data entry pages) point to data pages; each pointer represents a record ID (RID). Write the key value index entries for the root and the intermediate nodes in the tree above. © 2018 A. Alawini & A. Parameswaran Handling data changes in B+ Trees 14 © 2018 A. Alawini & A. Parameswaran 15 Insertion in a B+ Tree 80 20 60 100 120 140 10 15 18 20 30 40 50 60 65 80 85 90 10 15 18 20 30 40 50 60 65 80 85 90 Insert K=19 Assume d=2. DATA BLOCKS © 2018 A. Alawini & A. Parameswaran Insertion in a B+ Tree 16 80 20 60 100 120 140 10 15 18 19 20 30 40 50 60 65 80 85 90 10 15 18 20 30 40 50 60 65 80 85 9019 After insertion © 2018 A. Alawini & A. Parameswaran Insertion in a B+ Tree 17 80 20 60 100 120 140 10 15 18 19 20 30 40 50 60 65 80 85 90 10 15 18 20 30 40 50 60 65 80 85 9019 Now insert 25 © 2018 A. Alawini & A. Parameswaran Insertion in a B+ Tree 18 80 20 60 100 120 140 10 15 18 19 20 25 30 40 50 60 65 80 85 90 10 15 18 20 25 30 40 60 65 80 85 9019 After insertion 50 © 2018 A. Alawini & A. Parameswaran Insertion in a B+ Tree 19 80 20 60 100 120 140 10 15 18 19 20 25 30 40 50 60 65 80 85 90 10 15 18 20 25 30 40 60 65 80 85 9019 But now have to split ! 50 © 2018 A. Alawini & A. Parameswaran Insertion in a B+ Tree 20 80 20 30 60 100 120 140 10 15 18 19 20 25 60 65 80 85 90 10 15 18 20 25 30 40 60 65 80 85 9019 After the split 50 30 40 50 © 2018 A. Alawini & A. Parameswaran Deletion from a B+ Tree 21 80 20 30 60 100 120 140 10 15 18 19 20 25 60 65 80 85 90 10 15 18 20 25 30 40 60 65 80 85 9019 Delete 30 50 30 40 50 © 2018 A. Alawini & A. Parameswaran Deletion from a B+ Tree 22 80 20 30 60 100 120 140 10 15 18 19 20 25 60 65 80 85 90 10 15 18 20 25 40 60 65 80 85 9019 After deleting 30 50 40 50 May change to 40, or not © 2018 A. Alawini & A. Parameswaran Deletion from a B+ Tree 23 80 20 30 60 100 120 140 10 15 18 19 20 25 60 65 80 85 90 10 15 18 20 25 40 60 65 80 85 9019 Now delete 25 50 40 50 © 2018 A. Alawini & A. Parameswaran Deletion from a B+ Tree 24 80 20 30 60 100 120 140 10 15 18 19 20 60 65 80 85 90 10 15 18 20 40 60 65 80 85 9019 After deleting 25 Need to rebalance Rotate 50 40 50 Rotation in general can involve either sibling, but here only the left sibling can help © 2018 A. Alawini & A. Parameswaran 19 20 Deletion from a B+ Tree 25 80 20 30 60 100 120 140 10 15 18 60 65 80 85 90 10 15 18 20 40 60 65 80 85 9019 50 40 50 © 2018 A. Alawini & A. Parameswaran Deletion from a B+ Tree 26 80 19 30 60 100 120 140 10 15 18 19 20 60 65 80 85 90 10 15 18 20 40 60 65 80 85 9019 50 40 50 © 2018 A. Alawini & A. Parameswaran Deletion from a B+ Tree 27 80 19 30 60 100 120 140 10 15 18 19 20 60 65 80 85 90 10 15 18 20 40 60 65 80 85 9019 Now delete 40 50 40 50 © 2018 A. Alawini & A. Parameswaran Deletion from a B+ Tree 28 80 19 30 60 100 120 140 10 15 18 19 20 60 65 80 85 90 10 15 18 20 60 65 80 85 9019 After deleting 40 Rotation not possible 50 50 Need to merge nodes © 2018 A. Alawini & A. Parameswaran Deletion from a B+ Tree 29 80 19 60 100 120 140 10 15 18 19 20 50 60 65 80 85 90 10 15 18 20 60 65 80 85 9019 Final tree 50 © 2018 A. Alawini & A. Parameswaran Advantages of B+Trees •Balanced  Uniform space utilization • Predictable organization • Predictable time (logarithmic); unbalanced can be linear in worst case •Good for range queries 30 Can we do better? © 2018 A. Alawini & A. Parameswaran Outline •Indexing B+ Trees • Hash Tables 31 © 2018 A. Alawini & A. Parameswaran 32 Hash Tables © 2018 A. Alawini & A. Parameswaran 33 Hash Tables •Secondary storage hash tables are much like main memory ones •Recall basics: •There are n buckets •A hash function f(k) maps a key k to {0, 1, …, n-1} •Store in bucket f(k) a pointer to record with key k •Secondary storage: bucket = block •Store in bucket f(k) any record with key k •use overflow blocks when needed © 2018 A. Alawini & A. Parameswaran 34 •Assume 1 bucket (block) stores 2 records •h(e)=0 •h(b)=h(f)=1 •h(g)=2 •h(a)=h(c)=3 Hash Table Example e b f g a c 0 1 2 3 © 2018 A. Alawini & A. Parameswaran 35 •Search for a: •Compute h(a)=3 •Read bucket (block) 3 •1 disk access Searching in a Hash Table e b f g a c 0 1 2 3 Main memory may have an array of pointers (to buckets) accessible by bucket number. © 2018 A. Alawini & A. Parameswaran 36 •Place in right bucket (block), if space •E.g. h(d)=2 Insertion in Hash Table e b f g d a c 0 1 2 3 © 2018 A. Alawini & A. Parameswaran 37 •Create overflow block, if no space •E.g. h(k)=1 •More over- flow blocks may be needed Insertion in Hash Table e b f g d a c 0 1 2 3 k © 2018 A. Alawini & A. Parameswaran 38 Hash Table Performance •Fixed number of buckets •Excellent, if no overflow blocks •Degrades considerably when there are many overflow blocks. •Might need to go through a chain of overflow blocks Can fix this by allowing the number of buckets to grow © 2018 A. Alawini & A. Parameswaran 39 Extensible Hash Table • Array of pointers to blocks instead of array of blocks • Size of array is allowed to grow. 2x size when it grows • Don’t need a block per bucket. Sparse buckets share a block • Hash function returns k-bit integers (e.g., k=32) • Only use the first i << k bits to determine bucket • Number of buckets = 2i • Bit counter on each block indicates how much are used for that block 0(010) 1(011) i = 1 1 10 1 BUCKETS DATA BLOCKS Bit counter © 2018 A. Alawini & A. Parameswaran 40 Insertion in Extensible Hash Table •Insert 1110 0(010) 1(011) 1(110) i=1 1 1 0 1 BUCKETS DATA BLOCKS © 2018 A. Alawini & A. Parameswaran 41 Insertion in Extensible Hash Table • Now insert 1010 • Need to split block and extend bucket array • i becomes 2: done in two steps 0(010) 1(011) 1(110), 1(010) i=1 1 1 0 1 BUCKETS DATA BLOCKS © 2018 A. Alawini & A. Parameswaran 42 Insertion in Extensible Hash Table Step 1: Extend the buckets 0(010) 1(011) 1(110) i=1 1 1 0 1 BUCKETS DATA BLOCKS 0(010) 10(11) 11(10) i=2 1 1 00 01 10 11 BUCKETS DATA BLOCKS © 2018 A. Alawini & A. Parameswaran 43 Insertion in Extensible Hash Table Step 2: Now try to insert 1010 0(010) 10(11) 10(10) i=2 1 2 00 01 10 11 11(10) 2 BUCKETS DATA BLOCKS © 2018 A. Alawini & A. Parameswaran 44 Insertion in Extensible Hash Table Done 0(010) 10(11) 10(10) i=2 1 2 00 01 10 11 11(10) 2 BUCKETS DATA BLOCKS © 2018 A. Alawini & A. Parameswaran 45 Insertion in Extensible Hash Table • Now insert 0000: where would it go? Then 0101? • Need to split block, but not bucket array 0(010) 10(11) 10(10) i=2 1 2 00 01 10 11 11(10) 2 BUCKETS DATA BLOCKS © 2018 A. Alawini & A. Parameswaran 46 Insertion in Extensible Hash Table • Now insert 0000: where would it go? Then 0101? • Need to split block, but not bucket array 0(010) 0(000), 0(101) 10(11) 10(10) i=2 1 2 00 01 10 11 11(10) 2 BUCKETS DATA BLOCKS © 2018 A. Alawini & A. Parameswaran 47 Insertion in Extensible Hash Table • Now insert 0000: where would it go? Then 0101? • Need to split block, but not bucket array 10(11) 10(10) i=2 2 00 01 10 11 11(10) 2 BUCKETS DATA BLOCKS 00(10) 00(00) 2 01(01) 2 © 2018 A. Alawini & A. Parameswaran 48 Performance: Extensible Hash Table • No overflow blocks: access always one read for distinct keys • BUT: • Extensions can be costly and disruptive • After an extension bucket table may no longer fit in memory • Imagine three records whose keys share the first 20 bits. These three records cannot be in same block (assume two records per block). But a block split would require setting i = 20, i.e., accommodating for 2^20 = 1 million buckets, even though there may be only a few hundred records. © 2018 A. Alawini & A. Parameswaran 49 Linear Hash Table • Idea 1: add only one bucket at a time Problem: n = no longer a power of 2 • Let i be # bits necessary to address n buckets. • i = ceil(log2 n) • After computing h(k), use last i bits: • If last i bits represent a number >= n, change msb from 1 to 0 (get a number

< n) • Idea 2: allow overflow blocks (not expensive to overflow) • Convention: Read from the right (as opposed to the left) © 2018 A. Alawini & A. Parameswaran 50 Linear Hash Table Example • N=3 <= 22 = 4 • Therefore, only buckets until 10 • When inserting 0111, 11 is flipped => 01

(01)00

(10)10

i = 2

n = 3

r = 4

00
01
10

(01)01

(01)11 BIT FLIP

Linear Hash Table Example

• Insert 1001:

(01)00

(10)10

00
01
10

(01)01

(01)11

i = 2

n = 3

r = 4

Linear Hash Table Example

• Insert 1001: overflow blocks…

(01)00

(10)10

00
01
10

(01)01

(10)01

(01)11

i = 2

n = 3

r = 5

Linear Hash Tables

• Extend n  n+1 when average number of records per bucket exceeds
(say) 80% of total number of records per block

• e.g., r/n <= 0.8 * 2 = 1.6 (for block size = 2) • Until then, use overflow blocks (cheaper than adding buckets) r/n = 5/3 = 1.67 > 1.6
Time to add a bucket

(01)00

(10)10

00
01
10

(01)01

(10)01

(01)11

i = 2

n = 3

r = 5

Linear Hash Table Extension

• From n=3 to n=4

• Only need to touch
one block (which one ?)

(01)00

(10)10

00
01
10

(01)01

(10)01

(01)11

00
01
10
11

i = 2

n = 3

r = 5

i = 2

n = 4

r = 5

(01)11

(01)00

(10)10

(01)01

(10)01

(01)11

Linear Hash Table Extension

• From n=3 to n=4 finished

(01)01

(10)01

(01)11

00
01
10 (10)10

(01)00

i = 2

n = 4

r = 5

r/n = 5/4 = 1.25 < 1.6 ✔ © 2018 A. Alawini & A. Parameswaran 56 Summary • B+ Trees (search, insertion, deletion) • Good for point and range queries • Log time lookup, insertion and deletion because of balanced tree • Hash Tables (search, insertion) • Static hash tables: one I/O lookup, unless long chain of overflow • Extensible hash tables: one I/O lookup, extension can take long • Linear hash tables: ~ one I/O lookup, cheaper extension •No panacea; dependent on data and use case © 2018 A. Alawini & A. Parameswaran 57 Index 2.0 • Learn the best index from the data and queries logs • Machine Learning to the rescue! • Recall, an index is a function • Machine learning are good at learning functions from data • What’s your cool idea for a better index?

Related Posts