数据库课件lec5TreeIndexes幻灯片.ppt

* * 2 * * 3 * * 4 * * 6 * * 5 * * 7 * * 7 * 9 * 10 * 10 * * * 6 * * 10 * * * * 13 * * 12 * * 14 * * 13 * * 15 * * 16 * * 17 * * 18 * * 20 * * 21 * * 10 * * 22 * * 23 * * 24 Tree-Structured Indexes Jianlin Feng School of Software SUN YAT-SEN UNIVERSITY courtesy of Joe Hellerstein for some slides Review: Files, Pages, Records Abstraction of stored data is “files” with “pages” of “records”. Records live on pages Physical Record ID (RID) = page#, slot# Records can have fixed length or variable length. Files can be unordered (heap), sorted, or kind of sorted (i.e., “clustered”) on a search key. Indexes can be used to speed up many kinds of accesses. (i.e., “access paths”) Tree-Structured Indexes: Introduction Selections of form: field op constant Equality selections (op is =) Either “tree” or “hash” indexes help here. Range selections (op is one of , , =, =, BETWEEN) “Hash” indexes don’t work for these. More complex selections (e.g. spatial containment) There are fancier trees that can do this… Tree-structured indexing techniques support both range selections and equality selections. ISAM: static structure; early index technology. B+ tree: dynamic, adjusts gracefully under inserts and deletes. Range Searches ``Find all students with gpa 3.0’’ If data is in sorted file, do binary search to find first such student, then scan to find others. Cost of binary search in a database can be quite high. Why??? Simple idea: Create an `index’ file. Can do binary search on (smaller) index file! Page 1 Page 2 Page N Page 3 Data File k2 kN k1 Index File ISAM Index file may still be quite large. But we can apply the idea repeatedly! Leaf pages contain data entries. index entry Non-leaf Pages Pages Primary pages Leaf P 0 K 1 P 1 K 2 P 2 K m P m Overflow page Example ISAM Tree Index entries: search key value, page id, they direct search for data entries in leaves. Example where each node can hold 2 entries; 10* 15* 20* 27* 33* 37* 40* 46* 51* 55* 63* 97* 20 33 51 63 40 Ro