第 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
评论 (0)
暂无评论。快来抢沙发吧！