2쪽
Problem ◼ Relation: Employee (ID, Name, Dept, …) ◼ 10 M tuples ◼ (Filter) Query: SELECT * FROM Employee WHERE Name = “Bob”
3쪽
Solution #1: Full Table Scan ◼ Storage: ◼ Employee relation stored in contiguous blocks ◼ Query plan: ◼ Scan the entire relation, output tuples with Name = “Bob” ◼ Cost: ◼ Size of each record = 100 bytes ◼ Size of relation = 10 M x 100 = 1 GB ◼ Time @ 20 MB/s ≈ 1 Minute 3
5쪽
Solution #2 ◼ Cost: ◼ Size of a block: 1024 bytes ◼ Number of records per block: 1024 / 100 = 10 ◼ Total number of blocks: 10 M / 10 = 1 M ◼ Blocks accessed by binary search: 20 ◼ Total time: 20 ms x 20 = 400 ms 5
6쪽
Solution #2: Issues ◼ Filters on different attributes: SELECT * FROM Employee WHERE Dept = “Sales” ◼ Inserts and Deletes 6
7쪽
Indexes ◼ Data structures that efficiently evaluate a class of filter predicates over a relation ◼ Class of filter predicates: ◼ Single or multi-attributes (index-key attributes) ◼ Range and/or equality predicates ◼ (Usually) independent of physical storage of relation: ◼ Multiple indexes per relation 7
8쪽
Indexes ◼ Disk resident ◼ Large to fit in memory ◼ Persistent ◼ Updated when indexed relation updated ◼ Relation updates costlier ◼ Query cheaper 8
9쪽
Problem ◼ Relation: Employee (ID, Name, Dept, …) ◼ (Filter) Query: SELECT * FROM Employee WHERE Name = “Bob” Single-Attribute Index on Name that supports equality predicates
10쪽
Roadmap ◼ Motivation ◼ Single-Attribute Indexes: Overview ◼ Order-based Indexes ◼ B-Trees ◼ Hash-based Indexes (May cover in future) ◼ Extensible Hashing ◼ Linear Hashing ◼ Multi-Attribute Indexes (Chapter 14 GMUW, May cover in future) 10
12쪽
Single Attribute Index: General Construction A B a a b 1 1 1 a a b 2 2 2 A = val A > low a a b A < high i i i an an bn
13쪽
Exceptions ◼ Sparse Indexes ◼ Require specific physical layout of relation ◼ Example: Relation sorted on indexed attribute ◼ More efficient 13
14쪽
Single Attribute Index: General Construction Textbook: Dense Index A B a a b 1 1 1 a a b 2 2 2 A = val A > low a a b A < high i i i an an bn 14
15쪽
Single Attribute Index: General Construction How do we organize a (attribute, pointer) pairs? 1 a 2 A = val Idea: Use dictionary A > low a data structures A < high i Issue: Disk resident? an
16쪽
Roadmap ◼ Motivation ◼ Single-Attribute Indexes: Overview ◼ Order-based Indexes ◼ B-Trees ◼ Hash-based Indexes ◼ Extensible Hashing ◼ Linear Hashing ◼ Multi-Attribute Indexes 16
17쪽
B-Trees ◼ Adaptation of search tree data structure ◼ 2-3 trees ◼ Supports range predicates (and equality) 17
19쪽
Use Binary Search Tree Directly? ◼ Store records of type <key, left-ptr, right-ptr, data-ptr> ◼ Remember position of root ◼ Question: will this work? ◼ Yes ◼ But we can do better! 19
20쪽
Use Binary Search Tree Directly? ◼ Number of keys: 1 M ◼ Number of levels: log (2^20) = 20 ◼ Total cost index lookup: 20 random disk I/O ◼ 20 x 20 ms = 400 ms B-Tree: less than 3 random disk I/O 20
앞 20페이지만 표시됩니다. 전체를 보려면 자료를 다운로드하세요.
댓글 (0)
댓글이 없습니다. 첫 댓글을 남겨보세요!